【数据结构】栈的存储实现

　　栈是一种运算受限的线性表。栈的规则是先进后出。栈的顺序存储跟顺序线性表类似，不过栈的top代表栈顶，而顺序线性表的last代表最后一个元素。进栈用的头插法，插入线性表用的是尾插法；

顺序栈

顺序栈的定义为：

1 typedef struct 
2 {
3     int data[MAXSIZE];
4     int top;
5 }SeqStack;

创建栈：当栈没有值时就要把top指向-1；表示一个空栈，代码如下：

1 //创建栈
2 SeqStack *create_s()
3 {
4     SeqStack *s;
5     s = (SeqStack *)malloc(sizeof(SeqStack));
6     s->top = -1;
7     return(s);
8 }

入栈：由于栈的规则是先进后出，所以在入栈的时候应该用头插法。代码如下：

 1 //入栈
 2 void insert_s(SeqStack *s, int x)
 3 {
 4     if(s->top == MAXSIZE-1)
 5     {
 6         printf("栈已满");
 7     }
 8     else
 9     {
10         s->top++;
11         s->data[s->top] = x;    
12     }
13 }

入栈的时候应该先判断此栈是否已满，否则报错；

出栈：根据先进后出的法则，出栈代码如下：

1 //出栈
2 void out_s(SeqStack *s)
3 {
4     while(s->top != -1)
5     {
6         printf("%5d",s->data[s->top]);
7         s->top--;
8     }
9 }

完整程序代码如下：

顺序栈完整代码

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 #define MAXSIZE 1024
 5 
 6 //顺序栈的定义
 7 typedef struct 
 8 {
 9     int data[MAXSIZE];
10     int top;
11 }SeqStack;
12 
13 //函数声明
14 SeqStack *create_s();
15 void insert_s(SeqStack *s, int x);
16 void out_s(SeqStack *s);
17 
18 //创建栈
19 SeqStack *create_s()
20 {
21     SeqStack *s;
22     s = (SeqStack *)malloc(sizeof(SeqStack));
23     s->top = -1;
24     return(s);
25 }
26 
27 //入栈
28 void insert_s(SeqStack *s, int x)
29 {
30     if(s->top == MAXSIZE-1)
31     {
32         printf("栈已满");
33     }
34     else
35     {
36         s->top++;
37         s->data[s->top] = x;    
38     }
39 }
40 
41 //出栈
42 void out_s(SeqStack *s)
43 {
44     while(s->top != -1)
45     {
46         printf("%5d",s->data[s->top]);
47         s->top--;
48     }
49 }
50 
51 main()
52 {
53     SeqStack *s;
54     int n,x,i;
55     s = create_s();
56     printf("请输入需要插入值的个数：");
57     scanf("%d",&n);
58     for(i = 0; i < n; i++)
59     {
60         printf("请输入第%d个数：",i + 1);
61         scanf("%d",&x);
62         insert_s(s,x);
63     }
64 
65     printf("出栈值为：\n");
66     out_s(s);
67 }

链式栈

链式栈存储结构和线性表的链接存储结构相同。链式栈定义如下：

1 typedef struct node
2 {
3     int x;
4     struct node *next;
5 }StackNode;

创建链式栈：

1 //创建链式栈
2 StackNode *create_s()
3 {
4     StackNode *s;
5     s = (StackNode *)malloc(sizeof(StackNode));
6     s->next = NULL;
7     return(s);
8 }

入栈：

 1 //入栈
 2 StackNode *insert_s(StackNode *s, int x)        //入栈的时候要返回头结点，因为是头插法，如果不返回，当出栈的时候则找不到栈顶
 3 {
 4     StackNode *p;
 5     p = (StackNode *)malloc(sizeof(StackNode));
 6     p->x = x;
 7     p->next = s;
 8     s = p;
 9     return(s);
10 }

这里需要注意的是：每次入栈之后都要返回栈顶的地址；

出栈：

 1 //出栈
 2 void out_s(StackNode *s)
 3 {
 4     StackNode *p;
 5     while(s->next !=NULL)
 6     {
 7         p = s;
 8         printf("%5d",p->x);
 9         s = s->next;
10         free(p);
11     }
12 }

出栈的时候不要忘记把栈顶free掉，释放内存空间；

完整代码如下：

链式栈完整代码

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct node
 5 {
 6     int x;
 7     struct node *next;
 8 }StackNode;
 9 
10 //函数声明
11 StackNode *create_s();
12 StackNode *insert_s(StackNode *s, int x);
13 void out_s(StackNode *s);
14 
15 
16 //创建链式栈
17 StackNode *create_s()
18 {
19     StackNode *s;
20     s = (StackNode *)malloc(sizeof(StackNode));
21     s->next = NULL;
22     return(s);
23 }
24 
25 //入栈
26 StackNode *insert_s(StackNode *s, int x)        //入栈的时候要返回头结点，因为是头插发，如果不返回，当出栈的时候则找不到栈顶
27 {
28     StackNode *p;
29     p = (StackNode *)malloc(sizeof(StackNode));
30     p->x = x;
31     p->next = s;
32     s = p;
33     return(s);
34 }
35 
36 //出栈
37 void out_s(StackNode *s)
38 {
39     StackNode *p;
40     while(s->next !=NULL)
41     {
42         p = s;
43         printf("%5d",p->x);
44         s = s->next;
45         free(p);
46     }
47 }
48 
49 main()
50 {
51     StackNode *s;
52     int n,i,x;
53     s = create_s();
54     printf("请输入要创建栈的长度：");
55     scanf("%d",&n);
56     for(i = 0; i < n; i++)
57     {
58         printf("请输入第%d个值：", i + 1);
59         scanf("%d",&x);
60         s = insert_s(s,x);
61     }
62 
63     printf("出栈的顺序为：\n");
64     out_s(s);
65 }