1.什么是栈

首先栈是一种特殊的线性表。那它的特殊性表现在哪里呢？栈是限定在表的一端进行插入和删除运算的线性表，因此，栈也称为后进先出(LIFO)的线性表。

它有很多应用场景，比如食堂中的一叠盘子，我们只能从顶端一个一个地取。

2.栈的存储结构

3.栈的常见操作和代码实现

1，初始化

实现思路：用指定大小的length实例化一个SeqStack<T>，然后使top指针指向-1。

2，进栈

实现思路：将top指针加1，然后将新结点插入到top指针指向的位置。

3，出栈

实现思路：消灭top指向的结点，并使top指针减1。

4，获取栈顶元素

实现思路：与出栈相似，只是不改变栈的状态而已。

5，判断是否栈空

实现思路：如果top指针是否等于-1，如果是则返为空栈。

6，判断是否栈满

实现思路：检查top指针的值是否等于数组的长度，如果是则为栈满。

数组实现栈：

 1 #include <stdio.h>
 2 
 3 #define OK     0
 4 #define ERROR -1
 5 #define MAXSIZE 10
 6 
 7 typedef int Status;
 8 typedef int ElemType;
 9 
10 typedef struct
11 {
12     ElemType data[MAXSIZE];
13     int top;    //栈顶指针
14 }SeqStack;    //顺序栈结构
15 
16 Status Init(SeqStack *seqStack)
17 {
18     seqStack->top = -1;
19     return OK;
20 }
21 
22 Status Push(SeqStack *seqStack,ElemType e)
23 {
24     if(IsFull(seqStack))
25         return ERROR;
26     seqStack->data[++seqStack->top] = e;
27     return OK;
28 }
29 
30 Status Pop(SeqStack *seqStack,ElemType *e)
31 {
32     if(IsEmpty(seqStack))
33         return ERROR;
34 
35     *e = seqStack->data[seqStack->top];
36     seqStack->top--;
37 
38     return OK;
39 }
40 
41 Status GetTop(SeqStack *seqStack,ElemType *e)
42 {
43     if(IsEmpty(seqStack))
44         return ERROR;
45 
46     *e = seqStack->data[seqStack->top];
47 }
48 
49 int GetLength(SeqStack *seqStack)
50 {
51     return seqStack->top+1;
52 }
53 
54 Status IsEmpty(SeqStack *seqStack)
55 {
56     return seqStack->top == -1;
57 }
58 
59 Status IsFull(SeqStack *seqStack)
60 {
61     return seqStack->top == MAXSIZE -1;
62 }
63 
64 DisPlay(SeqStack *seqStack)
65 {
66     int i;
67     printf("æ ˆ*********
");
68     for(i=seqStack->top;i>=0;i--)
69         printf("%d
",seqStack->data[i]);
70     printf("***********
");
71 }
72 
73 int main(void)
74 {
75     SeqStack seqStack;
76     int j;
77     ElemType e;
78 
79     if(Init(&seqStack) == -1)
80         printf("Init Error");
81     printf("Init Success
");
82 
83     printf("è¿›æ ˆ
");
84     for(j=1;j<5;j++)
85         Push(&seqStack,j);
86     DisPlay(&seqStack);
87 
88     printf("èŽ•å–æ ˆé¡¶å…ƒç´ 
");
89     GetTop(&seqStack,&e);
90     printf("%d
",e);
91 
92     return 0;
93 }

运行结果

链表实现栈：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define OK     0
 5 #define ERROR -1
 6 
 7 typedef int Status;
 8 typedef int ElemType;
 9 typedef struct list
10 {
11     ElemType data;
12     struct list *next;
13 }List;
14 
15 typedef struct stack
16 {
17     List* top;
18 }Stack;
19 
20 void Init(Stack *stack)
21 {
22     stack->top = NULL;
23 }
24 
25 void Push(Stack *stack,ElemType e)
26 {
27     printf("Push %d
",e);
28     List *p = (List*)malloc(sizeof(List));
29     p->data = e;
30     p->next = stack->top;
31     stack->top = p;
32 }
33 
34 Status Pop(Stack *stack)
35 {
36     List *p;
37     if(stack->top == NULL)
38     {
39         printf("Stack is empty
");
40         return ERROR;
41     }
42     p = stack->top;
43     printf("Pop %d
",p->data);
44     stack->top = stack->top->next;
45     free(p);
46     return OK;
47 }
48 
49 int main(void)
50 {
51     int i=0;
52     Stack *s = (Stack*)malloc(sizeof(Stack));
53     Init(s);
54     for(i=0;i<5;i++)
55         Push(s,i);
56     for(i=0;i<6;i++)
57         Pop(s);
58 
59     return 0;
60 }

运行结果