【数据结构】顺序栈和链栈（带图详解）_链栈的进栈和出栈操作,分别画图表示其过程步骤

在计算机科学中，栈是一种基本的数据结构，用于存储和管理数据。它的特点是后进先出（Last-In-First-Out，简称LIFO）的顺序。在本文中，我们介绍概念、用途、基本操作和实现细节。

1.什么是栈？

栈是一种线性数据结构，它的元素按照特定的顺序进行插入和删除操作。栈的插入操作称为入栈（push），删除操作称为出栈（pop）。栈可以看作是一种具有限制访问的线性表，只能在表的一端进行插入和删除操作，称为栈顶（top）, 而另一端则称为栈底（bottom）。

1.1 栈的用途

栈在计算机科学中有着广泛的应用。以下是一些常见的栈的用途：

1. 函数调用：计算机使用栈来跟踪函数调用和返回过程。当一个函数被调用时，它的局部变量和返回地址等信息被推入栈中，当函数执行结束后，这些信息被弹出栈。
2. 表达式求值：栈可以用于解析和求值表达式，包括中缀表达式转换为后缀表达式和计算后缀表达式的值。
3. 内存管理：栈在内存管理中起着重要的作用，用于管理函数调用和局部变量的内存分配。
4. 浏览器历史记录：栈可以用于实现浏览器的历史记录功能，当用户浏览网页时，每个访问的URL被推入栈中，用户可以通过后退按钮依次访问之前的网页。
5. 撤销操作：栈可以被用于实现撤销操作，每次操作的状态被推入栈中，用户可以通过撤销操作逐步恢复到之前的状态。

2.栈的结构与基本操作

栈的两种结构

1.栈的顺序存储(数组实现)：

• 通过数组来实现栈时，通常需要一个指针来标记栈顶的位置。栈的插入操作（入栈）就是将元素添加到数组[top+1]的位置，然后将栈顶指针top++。删除操作（出栈）就是从数组[top]位置删除元素，然后将栈顶指针top–。

• 数组实现的栈在访问元素上具有很高的效率，因为可以直接通过下标来访问。但是它的缺点是容量固定，插入和删除操作可能需要移动大量元素。

• 在使用数组实现栈时，需要注意栈的溢出问题。即当栈空间已满时，继续进行入栈操作会导致栈溢出。

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int capacity;
	int top;   // 初始为0，表示栈顶位置下一个位置下标
}ST;
1
2
3
4
5
6
7

2.链式存储结构(链表实现)：

• 通过链表来实现栈时，每个节点包含数据元素和一个指向下一个节点的指针。栈顶指针指向链表的头部。

• 链表实现的栈不需要事先指定最大容量，插入和删除元素的效率比较高，因为不需要移动元素。但是访问指定位置的元素的效率比数组实现要低。

• 链表实现的栈不需要事先指定最大容量，插入和删除元素的效率比较高，因为不需要移动元素。但是访问指定位置的元素的效率比数组实现要低。

typedef int STDataType;
typedef struct StackNode
{
struct StackNode* next; // 下一个节点的指针
STDataType data; // 节点存储的数据
} STNode;

typedef struct Stack
{
STNode* top; // 栈顶指针
} ST;
1
2
3
4
5
6
7
8
9
10
11

栈支持以下几种基本操作：

1. 入栈（push）：将元素插入到栈顶。
2. 出栈（pop）：从栈顶删除元素，并返回被删除的元素。
3. 栈顶元素（top）：返回栈顶的元素，但不对栈进行修改。
4. 判空（isEmpty）：检查栈是否为空，如果为空则返回真，否则返回假。
5. 判满（isFull）：检查栈是否已满，如果已满则返回真，否则返回假。

3.栈的实现细节

3.1 顺序栈

3.1.1 栈的初始化

用于初始化栈，将栈的数组成员置空，栈顶索引为0，栈的容量为0。然后动态申请一块大小为4的内存空间作为栈的数组，如果申请失败则输出错误信息并退出程序

void StackInit(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL

// 初始化栈数据成员
ps->a = NULL; // 栈的数组成员为空
ps->top = 0; // 栈顶索引为 0
ps->capacity = 0; // 栈的容量为 0

// 重新分配空间，容量为 4
ps->a = (STDatatype*)malloc(sizeof(STDatatype)*4);
if (ps->a == NULL) // 如果分配失败，给出错误提示并退出程序
{
	perror("malloc fail");
	exit(-1);
}

// 更新栈数据成员
ps->top = 0; // 栈顶索引为 0
ps->capacity = 4; // 栈的容量为 4
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.1.2 元素入栈

将元素x入栈。如果栈已满（即栈的元素个数等于栈的容量），则重新分配一块大小为原来两倍的内存空间，并将原有的数据复制进来。然后将新元素放入栈顶（栈顶索引加一），更新栈顶索引

void StackPush(ST* ps, STDatatype x)
{
assert(ps); // 断言：ps 不为 NULL

// 如果栈满，需要重新分配更大的数组空间
if (ps->top == ps->capacity) 
{
	// 重新分配空间，并将原有数据复制进去
	STDatatype* tmp = (STDatatype*)realloc(ps->a, ps->capacity * 2 * sizeof(STDatatype));
	if (tmp == NULL) // 如果分配失败，给出错误提示并退出程序
	{
		perror("realloc fail");
		exit(-1);
	}

	// 重新分配空间成功后，更新栈数据成员
	ps->a = tmp;
	ps->capacity *= 2;
}

// 将新元素放入栈顶，更新栈顶索引
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
19
20
21
22
23
24

3.1.3 元素出栈

将栈顶元素出栈。如果栈为空（栈的元素个数为0），则不进行操作。否则，将栈顶索引减一，即将栈顶元素出栈。

void StackPop(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL
assert(!StackEmpty(ps)); // 断言：栈不为空

ps->top--; // 栈顶索引减一相当于将栈顶元素出栈
}
1
2
3
4
5
6
7

3.1.4 获取栈顶元素

获取栈顶元素的值。如果栈为空（栈的元素个数为0），则不进行操作。否则，返回栈顶元素的值（即栈顶索引减一对应的数组元素）

STDatatype StackTop(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL
assert(!StackEmpty(ps)); // 断言：栈不为空

return ps->a[ps->top - 1]; // 返回栈顶元素
}
1
2
3
4
5
6
7

3.1.5 判断栈是否为空

bool StackEmpty(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL

// 如果栈顶索引为 0，代表栈为空，否则不为空
return ps->top == 0;
}
1
2
3
4
5
6
7

3.1.6 获取栈的元素数量

int StackSize(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL
return ps->top; // 返回栈的元素数量，即栈顶索引
}
1
2
3
4
5

3.1.7 获取栈的元素数量

// 销毁栈
void StackDestroy(ST* ps)
{
assert(ps); // 断言：ps 不为 NULL
free(ps->a); // 释放动态分配的栈数组
ps->a = NULL; // 栈数组成员为空
ps->top = ps->capacity = 0; // 栈顶索引和栈的容量都为 0
}
1
2
3
4
5
6
7
8

3.2 链栈

栈是一种后进先出（LIFO）的数据结构，我们可以将其视为一个容器，可以在栈顶上面进行插入和删除操作，并且只能访问栈顶的元素。

typedef int STDataType;

typedef struct StackNode
{
    struct StackNode* next; // 下一个节点的指针
    STDataType data; // 节点存储的数据
} STNode;

typedef struct Stack
{
    STNode* top; // 栈顶指针
} ST;
1
2
3
4
5
6
7
8
9
10
11
12

3.2.1 初始化栈

void StackInit(ST* ps)
{
    ps->top = NULL; // 初始化栈顶指针为NULL
}
1
2
3
4

3.2.2 销毁栈

void StackDestroy(ST* ps)
{
    STNode* cur = ps->top;
    while (cur != NULL)
    {
        STNode* next = cur->next;
        free(cur);
        cur = next;
    }
    ps->top = NULL; // 销毁栈后，将栈顶指针置空
}
1
2
3
4
5
6
7
8
9
10
11

3.2.3 创建新的节点

STNode* BuyStackNode(STDataType x)
{
    STNode* pnode = (STNode*)malloc(sizeof(STNode));
    if (pnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    pnode->data = x; // 初始化节点的数据
    pnode->next = NULL; // 初始化节点的下一个指针为NULL

    return pnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2.3 将元素压入栈中

首先创建一个新的节点用于存储要压入的元素；其次将新节点连接到当前栈顶后面；最后将栈顶指针更新为新节点指针，使新节点成为新的栈顶元素。整个过程需要注意内存管理和各种边界条件。

void StackPush(ST* ps, STDataType x)
{
    STNode* newnode = BuyStackNode(x); // 创建新的节点
    newnode->next = ps->top; // 将新节点的下一个指针指向当前栈顶节点
    ps->top = newnode; // 更新栈顶指针为新的节点
}
1
2
3
4
5
6

3.2.4 将栈顶元素弹出

将栈顶指针向前移动一位以及更新栈顶指针。在执行出栈操作之前，应该检查链栈是否为空，以防止出现错误或异常。

void StackPop(ST* ps)
{
    if (ps->top == NULL)
    {
        return;
    }
    STNode* next = ps->top->next; // 获取当前栈顶节点的下一个节点指针
    free(ps->top); // 释放当前栈顶节点
    ps->top = next; // 更新栈顶指针为下一个节点
}
1
2
3
4
5
6
7
8
9
10

3.2.5 获取栈顶元素的值

STDataType StackTop(ST* ps)
{
    if (ps->top == NULL)
    {
        return -1;
    }
    return ps->top->data; // 返回栈顶节点的数据值
}
1
2
3
4
5
6
7
8

3.2.6 判断栈是否为空

bool StackEmpty(ST* ps)
{
    return ps->top == NULL; // 判断栈是否为空，根据栈顶指针是否为NULL
}
1
2
3
4

3.2.7 获取栈的大小

int StackSize(ST* ps)
{
    int count = 0;
    STNode* pcur = ps->top;
    while (pcur != NULL)
    {
        ++count;
        pcur = pcur->next;
    }
    return count; // 遍历栈，统计节点数量即为栈的大小
}
1
2
3
4
5
6
7
8
9
10
11

总结

栈是计算机科学中非常重要的数据结构，它具有简单且高效的特点。我们深入了解了栈的概念、用途、基本操作和实现细节。通过掌握栈的原理和应用，我们可以更好地理解和使用它，从而在解决实际问题时发挥其优势。