【数据结构】栈详解

---

对栈的理解

栈的特点：先进后出。

• 入栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈，出数据也在栈顶。

我们可以看出羽毛球桶，先放进去的羽毛球后拿出来，后放进去的羽毛球先拿出来，为了更好的理解进栈和出栈，笔者这里用简图表示一下

意思就是说，栈你如果要拿出一个，就是先拿出来后放进去的，要拿出来以前放进去的，就必须把后面放进去的全部拿出来才行

栈的实现 - 基于哪种常见类型演变而来的

我们先分析一下可能基于的对象，即

• 顺序表
• 链表

首先，我们可以看看双向链表，

双向链表固然是三者中最方便的，但是却逾越了栈的需求，通过双向链表，可以连接到前一个对象，也可以连接到后一个对象，但是栈仅需要堆最后放入对象，做出改变就行了
虽说，只要不用双向链表链向前者这一功能就行了，但是如果使用这种模式，却又不使用其功能，未免有些画蛇添足，浪费效能

再看看顺序表
首先，顺序表内存是连续的，所以可以随机访问，读取效率很高，O(1)。

物理（内存）上连续，逻辑上也连续：

顺序表的顺序存储结构，采用一组连续的内存来存储数据。

顺序表的线性关系是在内存（物理）上的相邻关系来表示数组的逻辑关系，也就是说，顺序表的连续和线性依靠的是内存的连续和线性。

因此，对于顺序表，我们可以取其精华，去其糟粕

既然这样，这样我们不妨看看两种之间的区别

所以，根据以上数组和链表的区别，我们可以思考在实现栈的时候，那种数据结构更好，因为栈只能在一端插入删除数据，插入删除数据的时候，只是在尾部进行插入删除，就不要去移动数据位置，这样我们就选择数组实现栈。

栈的基本实现

多看看注释哈！

首当其冲的就是栈的定义

//定义栈
typedef int STDataType;
//设置栈内元素的类型
typedef struct Stack
{
	STDataType* a;
	//创建装有指定元素的数组
	int top;
	//标识栈顶，便于后续操作
	int capacity;
	//栈内元素数量
}ST;//重命名结构体为ST
1
2
3
4
5
6
7
8
9
10
11
12

栈定义完后，自然需要对其初始化，以及销毁

// 初始化和销毁
void STInit(ST* pst)
{
	//断言，不多说了
	assert(pst);
	pst->a = NULL;
	
	// top指向栈顶数据的下一个位置
	pst->top = 0;

	// top指向栈顶数据
	//pst->top = -1;

	初始化数量
	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	//直接释放整个数组
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
	//初始化时，top=0，表示指向栈顶的下一个元素
}
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

入栈 和 出栈

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	// 扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		//因为我们在栈的初始化的时候，我们没有申请数组大小，所以我们在插入数据在进行判断是否数据已经存满的时候，我们要去考虑数据个数为0的情况。
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

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

取栈顶元素、判空 及 获取数据个数
这里的大多数操作与链表无异

// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

注意：

• 有的时候我们在使用的时候可能会不使用标准函数，及笔者上面所写的方法，但是这就好比正版有盗版的区分，
• 我们可以直接通过top–，使得栈顶元素消失，
• 也可以通过a[top-1]来获得栈顶元素
• 但是这是在我们知道内部函数运转规律且十分清楚的情况下，但凡有一丝与我们设想的不同，就可能导致运行失败，这样是大家都不想看到的，所以，为了是程序正常运行，大家还是尽量使用已经封装好的函数方法吧

栈实现总体代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int SLDataType;
 
typedef struct Stack{
	SLDataType* a;
	int top;
	int capacity;
}Stack;
 
//对栈进行初始化
void StackInit(Stack* ptr);
 
//对栈进行销毁
void StackDestroy(Stack* ptr);
 
//在栈顶插入元素
void StackPush(Stack* ptr, SLDataType x);
 
//获取栈顶元素
SLDataType StackTop(Stack* ptr);
 
//对栈进行判断，如果为空，返回true，否则返回false
bool StackEmpty(Stack* ptr);
 
//获取栈里面的元素个数
int StackSize(Stack* ptr);
 
void StackPop(Stack* ptr);
 
//栈的初始化
void StackInit(Stack* ptr)
{
	assert(ptr);
	ptr->a = NULL;
	ptr->capacity = ptr->top = 0;
}
 
//销毁栈
void StackDestroy(Stack* ptr)
{
	assert(ptr);
	free(ptr->a);
	ptr->a = NULL;
	ptr->capacity = ptr->top = 0;	//初始化时，top=0，表示指向栈顶的下一个元素
}
 
//在栈顶插入元素
void StackPush(Stack* ptr, SLDataType x)
{
	assert(ptr);
	if (ptr->top == ptr->capacity)
	{
		int newcapacity = ptr->capacity == 0 ? 4 : ptr->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ptr->a, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ptr->a = tmp;
		ptr->capacity = newcapacity;
	}
	ptr->a[ptr->top++] = x;
}
 
//取栈顶元素
SLDataType StackTop(Stack* ptr)
{
	assert(ptr);
	assert(!StackEmpty(ptr));
	return ptr->a[ptr->top - 1];
}
 
//栈判空
bool StackEmpty(Stack* ptr)
{
	assert(ptr);
	return ptr->top == 0;
}
 
//销毁栈顶元素
void StackPop(Stack* ptr)
{
	assert(ptr);
	assert(!StackEmpty(ptr));
 
	ptr->top--;
}
 
//获取栈里面元素个数
int StackSize(Stack* ptr)
{
	assert(ptr);
 
	return ptr->top;
}
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