举一个简单的例子：在往箱子里面放衣物的时候，放在最上面的衣物总是我们最后放上去的；而当我们从箱子里取出衣物的时候，总是最先拿出上面的。这就是现实生活中的栈。
准确的讲，栈就是一种可以实现“先进后出(或者叫后进先出)”的存储结构。
学过数据结构的人都知道：栈可以用两种方式来实现，一种方法是用数组实现栈，这种栈成为静态栈；另外一种方法是用链表实现栈，这种栈叫做动态栈。
栈中通常存放着程序的局部变量等。栈通常有出栈和入栈操作。
栈的结构
空栈的结构：【其实就是栈顶和栈顶都指向一个无用的头结点】
存有结点的栈结构：【栈顶指针指向栈顶结点，栈底指针指向头结点】
栈的实现
下面是用C实现的一个栈结构的源码及详细注释：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//定义结点结构体
typedef struct Node
{
int data; //内容
struct Node * pNext; //指向下一结点的指针
} NODE, * PNODE; //NODE等价于struct Node, PNODE等价于struct Node *
//定义栈的结构体
typedef struct Stack
{
PNODE pTop; //栈顶结点
PNODE pBottom; //栈底结点
} STACK, * PSTACK; //STACK等价于struct Stack, PSTACK等价于struct Stack *
//函数声明
void initStack(PSTACK pStack); //对栈进行初始化的函数
void pushStack(PSTACK pStack, int val); //入栈的函数
bool popStack(PSTACK pStack, int * pVal);//出栈的函数，*pVal用来保存出栈的元素内容
void traverseStack(PSTACK pStack); //遍历栈的函数
bool isEmpty(PSTACK pStack); //判断栈是否为空的函数
void clearStack(PSTACK pStack); //清空栈的函数
int main(void)
{
STACK stack; //定义一个栈变量,STACK等价于struct Stack
int val; //用来保存出栈的内容
initStack(&stack); //调用栈的初始化函数
pushStack(&stack, 10); //调用入栈的函数
pushStack(&stack, 20);
pushStack(&stack, 30);
pushStack(&stack, 50);
traverseStack(&stack); //调用遍历栈的函数
//调用出栈的函数
if(popStack(&stack, &val))
printf("出栈成功，出栈的元素值为：%d\n", val);
else
printf(" 出栈失败!");
//调用清空栈的函数
clearStack(&stack);
traverseStack(&stack); //调用遍历栈的函数
system("pause");
return 0;
}
void initStack(PSTACK pStack)
{
//创建一个空结点，让pTop指向它
pStack->pTop = (PNODE)malloc(sizeof(NODE));
if(NULL != pStack->pTop)
{
//将pBottom也指向空节点
pStack->pBottom = pStack->pTop;
//清空空结点的指针域
pStack->pTop->pNext = NULL;
}
else //如果内存分配失败
{
printf("内存分配失败!程序退出!\n");
exit(-1);
}
return;
}
void pushStack(PSTACK pStack, int val)
{
//动态创建一个新结点
PNODE pNew = (PNODE)malloc(sizeof(NODE));
//设置新结点的数据域的值
pNew->data = val;
//将新结点的指针域指向之前建的空节点
pNew->pNext = pStack->pTop; //pStack->pTop不能换成pStack->pBottom
//pTop指向新的结点
pStack->pTop = pNew;
return;
}
bool popStack(PSTACK pStack, int * pVal)
{
if(isEmpty(pStack))
{
return false;
}
else
{
//先保存栈顶元素的地址，然后将pTop指向下一元素,最后释放之前栈顶元素的内存
PNODE rNode = pStack->pTop;
*pVal = rNode->data;
pStack->pTop = rNode->pNext;
free(rNode);
rNode = NULL;
return true;
}
}
void traverseStack(PSTACK pStack)
{
//将栈顶赋给一个临时结点,因为在遍历栈的时候不能销毁栈
PNODE pNode = pStack->pTop;
//循环遍历栈,直到栈底
while(pStack->pBottom != pNode )
{
printf("%d ", pNode->data);
pNode = pNode->pNext;
}
printf("\n");
return;
}
bool isEmpty(PSTACK pStack)
{
if(pStack->pTop == pStack->pBottom)
return true;
else
return false;
}
void clearStack(PSTACK pStack)
{ //栈为空，则退出该函数
if(isEmpty(pStack))
{
return;
}
else
{
//两个结点指针变量用来释放栈中元素的内存
PNODE p = pStack->pTop;
PNODE q = NULL;
//循环释放内存
while(p != pStack->pBottom)
{
q = p->pNext;
free(p);
p = q;
}
//将栈顶和栈底指向同一个指针域为空的结点
pStack->pTop = pStack->pBottom;
return;
}
}
|
栈的典型应用
生产消费模型常用栈来实现。生产者生产的东西都放入栈中，然后消费者从栈中依次取出东西，当栈顶和栈底指向都指向首结点时，生产的东西就被消耗光了。
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！