定义

在静态内存当中分配的叫做栈，在动态内存中分配的叫做堆。

---

---

**红色椭圆圈当中的就是在栈中分配的，蓝色下划线的就是在堆里分配的。**栈和堆表示的是分配数据的一种方式。静态局部变量是通过压栈和出栈来分配内存的，而动态变量是通过堆排序的方式来分配内存。

所以，栈是一种可以实现“先进后出”的存储结构，栈类似于箱子（有底）。

分类

静态栈

以数组为最基本的内核。

动态栈

不连续，其内核是链表（不允许尾部插入尾部删除）。最常用的是动态栈。

算法

压栈和出栈。
push&pop

#include <iostream>
#include <cmalloc>
#include <cstdlib>

using namespace std;

typedef struct Node
{
	int data;
	struct Node * pNext;
}NODE, *PNODE;

typedef struct Stack
{
	PNODE pTop;//栈顶
	PNODE pBottom;//栈底
}STACK, *PSTACK;

//因为栈也是链表演化过来的，对于栈来说，其栈底就相当于链表的头结点，栈底上方一个元素就是第一个有效节点。

//初始化
void init(PSTACK);
void push(PSTACK, int);
void traverse(PSTACK);
bool pop(PSTACK, int);


int main(void){
	STACK S;
	//这样就生成一个栈了，里面有两个元素，一个pTop一个pBottom。
	init(&S);
	//初始化就是使得pTop以及pBottom指向同一个头结点，（链表）即可生成一个空栈。
	//注意的是，压栈的时候无需指定位置，因为只能放在栈顶。
	push(&S, 1);//压栈后，这个结点就相当于pBottom了，之后它指向下方的头结点
	push(&S, 2);//pTop需要根据压栈而随时变化。
	traverse(&S);//遍历
	pop(&S, &val);
	
	return 0;
}

//初始化，造空栈
void init (PSTACK pS)
{	//现在就是要使得pTop以及pBottom都指向一个没有实际含义的，也就是pBottom下一个的结点，类似链表当中的头结点。
	pS->pTop = (PNODE)malloc(sizeof(NODE));
	if (pS->pTop == nullptr)
	{
		cout << "动态内存分配失败！" << endl;
		return -1;
	}
	else
	{
		pS->pBottom = pS->pTop;
		pS->pTop->pNext = nullptr;//把pBottom指向的下一个结点的指针域清空，这里的pTop换成pBottom是一样的，因为现在这两个都指向了pBottom的下一个结点。
	}
}

//压栈
void push(PSTACK pS, int val)
{
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	pNew->pNext = pS->pTop;//每次压栈都放到栈顶的上方，这里只能写pTop。
	pS->pTop = pNew;//这样新的节点就是栈顶了，每次压栈，新的节点都是栈顶。	
}

//遍历
void traverse(PSTACK)
{
	//定义指针p，永远指向栈顶元素。
	PNODE p = pS->pTop;
	while(p != pS->pBottom)
	{
		cout << p->data << '\n' << endl;
		p = p->pNext;
	}
	return;
}

//判断是否为空栈
bool empty(PSTACK pS)
{
	if(pS->pTop == pS->pBottom)
		return true;
	else
		return false;
}

//把pS嗦指向的栈出栈一次，并把出栈的元素存入pVal形参所指向的变量中，如果出栈失败，返回false，出栈成功返回true。
bool pop(PSTACK pS, int *pVal)
{
	if (empty(pS))//pS本身就是S的地址
		return false;
	else
	{
		PNODE r = pS->pTop;
		*pVal = r->data;
		pS->pTop = r->pNext;
		free(r);
		r = nullptr;
		return true;
	}
}

void clear()
//清空，一个一个释放
//定义两个指针，一个p一个q，q指向p的下一个元素
//如果把p给free掉，那么q还是能指向下一个元素，这时候只要把q赋值给p，然后q再向下移一个，只要p指向的不是bottom，都能成立。
{
	if (empty(pS))
	{
		return;
	}
	else
	{
		PNODE p = pS->pTop;
		PNODE q = nullptr;
		while (p != pS->pBottom)
		{	
			q = p->pNext;
			free(p);
			p = q;
		}
		pS->pTop = pS->pBottom;
	}
}
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

初始化后的栈：

push的操作

判断栈是否为空，则看pTop与pBottom是否相等。

应用

• 函数调用
• 中断
• 表达式求值
• 内存分配
• 缓冲处理
• 迷宫