数据结构----栈

一丶概念

             只能在一端举行插入和删除利用的线性表（又称为堆栈），举行插入和删除利用的一端称为栈顶，另一端称为栈底   

  二丶特点

        先辈后出 FILO first in last out
        后进先出 LIFO last in first out
三丶顺序栈

        逻辑结构：线性结构
     存储结构：顺序存储
     利用：入栈、出栈  1.创建一个空的栈

   

   2.入栈

      

    3.出栈

                

         

1. #include <stdio.h>
2. #include <stdlib.h>
3. typedef int datatype;
4. typedef struct seqstack
5. {
6.     int maxlen;     // 数组中元素总个数
7.     datatype *data; // 指向数组的指针
8.     int top;        // 栈顶元素的下表
9. } seqstack_t;
10. seqstack_t *CreateEplist(int len)//创建一个空表
11. {
12.     seqstack_t *p = (seqstack_t *)malloc(sizeof(seqstack_t));//先对结构体指针开辟堆区空间
13.     if (NULL == p)//判错
14.     {
15.         printf("Create err");
16.         return NULL;
17.     }
18.     p->maxlen = len;
19.     p->top = -1;//初始化结构体
20.     p->data = (int *)malloc(sizeof(int) * len);//对指向数组的指针开辟堆区空间
21.     if (NULL == p->data)//判错
22.     {
23.         printf("DATA err");
24.         return NULL;
25.     }
26.     return p;
27. }
28. int Isfull(seqstack_t *p)//判断结构体是否为满
29. {
30.     return p->top + 1 == p->maxlen;
31. }
32. int IsEmpty(seqstack_t *p)//判断结构体是否为空
33. {
34.     return p->top == -1;
35. }
36. int Pushdata(seqstack_t *p, int data)//输入数据，入栈
37. {
38.     if (Isfull(p))
39.     {
40.         printf("Seqstack is full");
41.         return -1;
42.     }
43.     p->top++;
44.     p->data[p->top] = data;
45.     return 0;
46. }
47. int show(seqstack_t *p)//输出数据，出栈
48. {
49.     if (IsEmpty(p))
50.     {
51.         printf("Seqstack is empty");
52.         return -1;
53.     }
54.     while (!IsEmpty(p))
55.     {
56.         p->top--;
57.         printf("%d ",p->data[p->top + 1]);
58.     }
59.     printf("\n");
60. }
61. void Clearlist(seqstack_t *p)//清空栈
62. {
63.     p->top = -1;
64. }
65. int main(int argc, char const *argv[])
66. {
67.     seqstack_t *p = CreateEplist(10);
68.     Pushdata(p, 1);
69.     Pushdata(p, 2);
70.     Pushdata(p, 3);
71.     Pushdata(p, 4);
72.     Pushdata(p, 5);
73.     show(p);
74.     printf("%d\n", p->top);
75.     printf("%d\n", p->maxlen);
76.     return 0;
77. }

复制代码

   练习：
 
                  

1. 若进栈顺序为 1,2,3,4 一下四种情况不可能出现的出栈序列是( )

      

      A. 1,4,3,2                B. 2,3,4,1               C. 3,1,4,2              D. 3,4,2,1

      

2. 下列叙述正确的是( )

      

     A. 线性表是线性结构
     B. 栈与队列是非线性结构 //栈只能在一端举行插入和删除利用的线性表
     C. 线性链表是非线性结构
     D. 二叉树是线性结构 //树形结构 层次关系

      

3. 下列关于栈叙述正确的是( )

      

      A.在栈中只能插入数据//栈只能在一端举行插入和删除利用的线性表，插入和删除端称为栈顶 ，另一端是栈底
      B.在栈中只能删除数据
      C.栈是先辈先出的线性表
      D.栈是先辈后出的线性表

                四丶链式栈

           逻辑结构：线性结构      

        存储结构：链式存储
        利用：入栈、出栈

     

1. #include <stdio.h>
2. #include <stdlib.h>
3. typedef int datatype;//重定义数据类型
4. typedef struct seqlist
5. {
6.     datatype data;//数据域
7.     struct seqlist *next;//指针域
8. } seqlist_t;
9. void CreateList(seqlist_t **p)//创建一个空表
10. {
11.     *p = NULL;
12. }
13. int Isempty(seqlist_t *p)//判断链表是否为空
14. {
15.     return p == NULL;
16. }
17. int Pushlist(seqlist_t **p_top, int data)//进栈，由于需要一直让p_top指向栈的最顶端，所以需要传二级指针
18. {
19.     seqlist_t *p_new = (seqlist_t *)malloc(sizeof(seqlist_t));//开辟一个新的堆区空间
20.     if (NULL == p_new)//开辟失败报错
21.     {
22.         printf("push err");
23.         return -1;
24.     }
25.     p_new->data = data;//数据域等于数据
26.     p_new->next = *p_top;//指针域等于原来的栈顶
27.     *p_top = p_new;//更新栈顶
28.     return 0;
29. }
30. int Popdata(seqlist_t **p_top)//出栈
31. {
32.     if (Isempty(*p_top))//判断栈是否为空
33.     {
34.         printf("pushdata err\n");
35.         return -1;
36.     }
37.     seqlist_t *p_new = NULL;
38.     while (!Isempty(*p_top))//循环判断条件
39.     {
40.         p_new=*p_top;//保存地址
41.         printf("%d ", p_new->data);//出栈
42.         *p_top=p_new->next;//让p_top指向下一个地址
43.         free(p_new);//释放空间
44.         p_new=NULL;
45.     }
46.     printf("\n");
47. }
48. int Lenlinklist(seqlist_t *p)//求栈的长度
49. {
50.     int len=0;
51.     while(p)
52.     {
53.         p=p->next;
54.         len++;
55.     }
56.     printf("栈的长度为%d\n",len);
57. }
58. void ClearList(seqlist_t **p_top)//清空栈
59. {
60.     while(*p_top)
61.     {
62.         seqlist_t *q_del=*p_top;
63.         *p_top=(*p_top)->next;
64.         free(q_del);
65.         q_del=NULL;
66.     }
67. }
68. void GettopList(seqlist_t *p)//求栈顶的数据
69. {
70.     if(!Isempty(p))
71.     printf("栈顶的数据为%d\n",p->data);
72. }
73. int main(int argc, char const *argv[])
74. {
75.     seqlist_t *p_top;
76.     CreateList(&p_top);
77.     Pushlist(&p_top,1);
78.     Pushlist(&p_top,2);
79.     Pushlist(&p_top,3);
80.     Pushlist(&p_top,4);
81.     Pushlist(&p_top,5);
82.     Lenlinklist(p_top);
83.     GettopList(p_top);
84.     Popdata(&p_top);
85.     ClearList(&p_top);
86.     Popdata(&p_top);
87.     return 0;
88. }

复制代码

          总结：

   

顺序栈和链式栈的区别是什么？

   

     (1)存储结构不同，顺序栈相称于数组，连续的，链式栈 链表非连续的
     (2)顺序栈的长度受限制，而链栈不会

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。