数据结构从入门到精通——栈

---

前言

栈，作为一种后进先出（LIFO）的数据结构，在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而，如果我们跳出传统思维的束缚，会发现栈的用途远不止于此。

在现代软件开发中，栈的概念被广泛应用在内存管理、并发控制等多个领域。以内存管理为例，每个线程都有自己的栈空间，用于存储局部变量和函数调用信息。这种隔离保证了线程之间的数据安全，避免了数据混乱和意外覆盖。

同样，在并发控制中，栈也发挥着不可替代的作用。通过维护一个任务栈，系统可以合理地调度和分配计算资源，确保任务按照特定的顺序执行，从而避免了并发访问导致的数据不一致问题。

不仅如此，栈的思想还可以被借鉴到生活的方方面面。想象一下，如果我们将日常生活比作一个栈，那么每一天的生活就是一个新的元素被推入栈中。而当我们结束一天的生活，这个元素就会被从栈中弹出，成为我们宝贵的回忆。这种后进先出的特性使得我们能够更好地珍惜当下，因为每一个现在都会成为过去，而每一个过去都是无法替代的。

在这个意义上，栈不仅仅是一种数据结构，更是一种生活态度。它提醒我们珍惜每一个当下，因为每一个现在都会成为我们未来回忆的一部分。同时，它也告诉我们，在面对困难和挑战时，要敢于迎难而上，因为只有这样，我们才能不断成长和进步。

---

一、栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

Push是入栈

Pop是出栈

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;
 
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
 STDataType* _a;
 int _top; // 栈顶
 int _capacity; // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps); 
// 入栈 
void StackPush(Stack* ps, STDataType data); 
// 出栈 
void StackPop(Stack* ps); 
// 获取栈顶元素 
STDataType StackTop(Stack* ps); 
// 获取栈中有效元素个数 
int StackSize(Stack* ps); 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps); 
// 销毁栈 
void StackDestroy(Stack* ps); 
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

1.3栈的面试题

1. 括号匹配问题

2. 一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。
   A. 12345ABCDE
   B. EDCBA54321
   C. ABCDE12345
   D. 54321EDCBA

3. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
   A 1,4,3,2
   B 2,3,4,1
   C 3,1,4,2
   D 3,4,2,1

答案：B C

二、栈的具体实现代码

栈的初始化

void STInit(ST* ps);//栈的初始化
1

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;//或者ps->top = -1;具体区别在于先++还是后++
}
1
2
3
4
5
6
7

栈的初始化是数据结构中栈操作的第一步，它涉及为栈分配内存空间并设置其初始状态。栈是一种后进先出（LIFO）的数据结构，这意味着最后一个被放入栈中的元素将是第一个被取出的元素。

在进行栈的初始化时，我们需要考虑几个关键步骤。首先，我们需要为栈定义一个合适的数据结构，这通常是一个数组或链表。数组实现的栈在内存中使用连续空间，而链表实现的栈则更为灵活，但可能会占用更多的内存。

接下来，我们需要为栈分配内存空间。对于数组实现的栈，这通常意味着创建一个固定大小的数组来存储栈元素。对于链表实现的栈，我们需要创建一个空的链表节点作为栈顶。

在分配了内存空间之后，我们需要设置栈的初始状态。这通常意味着将栈顶指针或引用设置为一个表示栈为空的状态。对于数组实现的栈，这通常是数组的第一个位置或最后一个位置的索引。对于链表实现的栈，这通常是一个指向空链表节点的指针。

完成栈的初始化后，我们就可以开始执行栈的基本操作，如入栈（push）、出栈（pop）、查看栈顶元素（top）以及判断栈是否为空（is_empty）等。这些操作需要确保遵循栈的后进先出原则。

栈的销毁

void STDestroy(ST* ps);//栈的销毁
1

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
1
2
3
4
5
6
7
8

栈的销毁是栈生命周期中的最后一个阶段，它标志着栈内所有数据元素的释放和栈结构本身的解除。在进行栈的销毁之前，必须确保栈中没有任何数据元素，否则可能会导致数据丢失或内存泄漏。

栈的销毁过程通常包括以下几个步骤：

首先，需要遍历栈内的所有元素，并将它们逐一释放。这通常涉及到调用每个元素的析构函数（如果是C++等支持面向对象编程的语言）或相应的清理函数（如果是C等过程式编程语言），以确保每个元素在被销毁前能够正确地完成其生命周期内的所有任务，如关闭文件、释放内存等。

其次，需要销毁栈本身的数据结构。这通常意味着释放栈所占用的内存空间。在大多数编程语言中，这可以通过调用类似于free（C语言）或delete（C++）这样的内存管理函数来完成。一旦栈的数据结构被销毁，它就不再是一个有效的栈，不能再执行入栈、出栈等操作。

最后，为了确保栈确实已经被销毁，可以在销毁后进行一些检查操作。例如，可以尝试对栈执行一些操作，如入栈或出栈，并检查是否会引发错误或异常。如果程序能够正确地检测到栈已经被销毁，并采取相应的错误处理措施，那么这就可以作为栈销毁过程完成的一个标志。

总的来说，栈的销毁是一个非常重要的过程，它确保了栈在不再需要时能够正确地释放其占用的资源，防止了内存泄漏和其他潜在的资源管理问题。同时，通过销毁栈，也可以为其他需要使用这些资源的操作提供空间，从而提高了整个程序的效率和可靠性。

入栈

//入栈
void STPush(ST* ps,STDatatype x);
1
2

void STPush(ST* ps,STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);
		if (p == NULL)
		{
			perror("p malloc : ");
			return 0;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

“入栈”（Push）是栈（Stack）这种数据结构中的一个基本操作。栈是一种遵循后进先出（Last In First Out，简称LIFO）原则的数据结构，意味着最后放入栈中的元素将会是第一个被取出的。

“入栈”操作的具体含义是：

1. 添加元素：将一个元素添加到栈的顶部。
2. 栈顶变化：由于新元素被添加到栈顶，所以栈顶指针或引用会更新，指向这个新添加的元素。
3. 栈大小变化：栈的大小（或容量）会增加，因为多了一个元素。

例如，假设我们有一个空的栈，并且按照以下顺序执行入栈操作：

1. 入栈 A
2. 入栈 B
3. 入栈 C

那么，栈的当前状态将是 C 在顶部，B 在中间，A 在底部。如果我们现在执行出栈（Pop）操作，C 将被取出，接着是 B，最后是 A。

在实际应用中，栈常用于保存函数调用过程中的局部变量、参数和返回地址，实现递归调用，以及进行深度优先搜索等。

入栈，是每一个数据处理流程中不可或缺的一环。在信息技术的世界里，数据就如同图书馆的藏书，需要有序地存放和取用。而栈，便是这个数字世界中的一个小巧精致的藏书阁，它遵循着后进先出（LIFO）的规则，每一份数据都像是一本书，被轻轻放在栈顶，等待着被取用或者再次被存放。

每当有新的数据需要处理时，它就会被推入栈中。这个过程就像是图书馆里新到了一本畅销书，图书管理员会将它放在最显眼的位置，供读者最先取阅。同样，栈顶的数据也是最先被处理的，因为它是最后进栈的。这种有序的处理方式，保证了数据处理的效率和准确性。

然而，栈并非万能的。它的规则简单而明确，但也因此有局限性。有时候，我们需要按照不同的顺序来处理数据，这时候就需要使用到队列等其他数据结构。但无论如何，栈都是数据处理中不可或缺的一部分。

在软件开发的世界里，栈的作用更是举足轻重。函数调用、递归算法、异常处理等，都离不开栈的支持。每当一个函数被调用时，它的相关信息就会被压入调用栈中，等待函数执行完毕后弹出。这使得程序能够准确地跟踪函数的执行顺序，保证程序的正确运行。

同时，栈也是内存管理的重要手段。在编程中，我们经常需要动态地分配和释放内存。而栈就是内存分配的一种方式。它会自动管理分配给每个函数的内存空间，当函数执行完毕后，这些内存空间就会被自动释放，避免了内存泄漏等问题的发生。

总的来说，入栈是数据处理和程序运行中的关键步骤。它保证了数据的有序性和程序的正确性，是信息技术世界中不可或缺的一环。在未来的技术发展中，栈的作用将更加重要，我们也需要更加深入地理解和应用它。

出栈

//出栈
void STPop(ST* ps);
1
2

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}
1
2
3
4
5
6

当元素从栈的顶部被移除时，这个过程被称为“出栈”。栈是一种遵循后进先出（LIFO）原则的数据结构，其中新元素总是被添加到栈顶，而只有栈顶的元素可以被移除。出栈操作会减少栈的大小，并返回被移除的元素。如果栈为空，则无法进行出栈操作。

返回栈顶元素

STDatatype STTop(ST* ps);//返回栈顶元素
1

STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
1
2
3
4
5
6

返回栈中的元素个数

int STSize(ST* ps);//返回栈中的元素个数
1

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5

检测是否为空

注意：在使用VS2022编译器编译C语言需要用到布尔类型的时候，需要添加头文件#include ，添加了这个头文件才能使用布尔类型

bool STEmpty(ST* ps);//检测是否为空
1

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5

Stack.h

#pragma once
#include 
#include 
#include 
#include 
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);//栈的初始化
void STDestroy(ST* ps);//栈的销毁

//入栈
void STPush(ST* ps,STDatatype x);
//出栈
void STPop(ST* ps);
STDatatype STTop(ST* ps);//返回栈顶元素
int STSize(ST* ps);//返回栈中的元素个数
bool STEmpty(ST* ps);//检测是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Stack.c

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;//或者ps->top = -1;具体区别在于先++还是后++
}
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void STPush(ST* ps,STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDatatype* p = (STDatatype*)realloc(ps->a, sizeof(STDatatype)*newcapacity);
		if (p == NULL)
		{
			perror("p malloc : ");
			return 0;
		}
		ps->a = p;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
STDatatype STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
	assert(ps);
	return ps->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

test.c

#include"Stack.h"

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);

	int top = STTop(&s);
	printf("%d ", top);
	STPop(&s);

	STPush(&s, 4);
	STPush(&s, 5);

	while (!STEmpty(&s))
	{
		int top = STTop(&s);
		printf("%d ", top);
		STPop(&s);
	}

	STDestroy(&s);

	return 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
28

---