数据结构之栈、队列和数组

2026-02-12

数据结构之栈、队列和数组

第三章_栈、队列和数组

本章介绍的两种数据结构栈和队列在逻辑结构上都属于线性结构，只不过是操作受限的线性表。

3.1 栈

3.1.1 栈的基本概念

栈（stack） 是仅允许在一端进行插入和删除操作的线性表。

在写C语言时，函数销毁创建本质就是依赖于栈这一数据结构。特点是后进先出（Last In First Out，LIFO） 下面介绍栈的三个基本属性以及示意图：

栈顶（Top）： 允许进行插入和删除操作的这一端。
栈底（Bottom）： 固定不变，不允许进行插入和删除操作的这一端。
空栈： 不含任何元素的栈。

栈示意图

3.1.2 栈的基本操作

采用严蔚敏版的命名规范：

InitStack(&S)：初始化一个空栈S。
DestroyStack(&S)：销毁栈S，释放其存储空间。
Pop(&S,x)：入栈操作，若栈未满，则x成为新的栈顶元素。
Push(&S,x)：出栈操作，若栈非空，则弹出栈顶元素，并通过x返回该值。
GetTop(S,&x)：读取栈顶元素但不出栈，若栈非空，则通过x返回值。
StackEmpty(S)：判断栈是否为空，为空返回True，否则返回False。

3.1.3 栈的数学性质

栈的数学性质： 当n个不同的元素按固定次序入栈时，可能的出栈序列的总数为 1/(n+1)Cⁿ_2n，该数列也被称为卡特兰数。（做题时很好用）

3.1.4 顺序栈

3.1.3.1 顺序栈的定义

采用顺序存储的栈称为顺序栈，它利用一组连续的存储单元存放从栈顶到栈底的数据元素，并附设一个整型指针（top） 指向当前栈顶元素位置。

与线性表类似，栈也有两种基本的存储方式：顺序存储和链式存储。

3.1.3.2 顺序栈的实现和基本操作

下面介绍顺序栈。基于top指针的指向方式，栈其实存在两种操作方式：1. top 表示当前栈顶元素的下标，2. top 表示“下一个可存放元素的位置”。由于和《数据结构之绪论与线性表》中的代码大致都相同，也很简单，这里直接用代码说明顺序栈的实现和基本操作。

1. top 表示当前栈顶元素的下标: 注意top指针在这种情况下初始化为 -1。在做题时，S.data[++top]; 等代码的 ++top 和 top++，两种情况表示不同，一定理解记忆是哪种情况。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

# define MaxSize 50
typedef struct {
	Elemtype data[MaxSize];
	int top;
 }SqStack;

void InitStack(SqStack& S) {
	S.top = -1; //注意这里初始化为-1
}

bool StackEmpty(SqStack &S) {
	if (S.top == -1) {
		return true;
	}
	return false;
}

bool Push(SqStack &S, Elemtype x) {
	if (S.top == MaxSize - 1) {  //栈满，不能插入
		return false;
	}

	//下面两行等价于S.data[++top]=x; 做题时注意区分
	S.top++;
	S.data[S.top] = x;

	return true;
}

bool Pop(SqStack& S, Elemtype &x) {
	if (S.top == -1) {  //栈为空，无法删除
		return false;
	}

	x = S.data[S.top--];
	return true;
}

bool GetTop(SqStack &S, Elemtype &e) {
	if (S.top == -1) {  //栈为空，无法读取
		return false;
	}
	e = S.data[S.top];
	return true;
}

2. top 表示“下一个可存放元素的位置” 注意一开始 top 指针置为 0

# define MaxSize 50
typedef struct {
	Elemtype data[MaxSize];
	int top;
 }SqStack;

void InitStack(SqStack& S) {
	S.top = 0; //注意这里初始化为-1
}

bool StackEmpty(SqStack &S) {
	if (S.top == 0) {
		return true;
	}
	return false;
}

bool Push(SqStack &S, Elemtype x) {
	if (S.top == MaxSize) {  //栈满，不能插入
		return false;
	}

	//下面两行等价于S.data[top++]=x; 
	S.data[S.top] = x;
	S.top++;

	return true;
}

bool Pop(SqStack& S, Elemtype &x) {
	if (S.top == 0) {  //栈为空，无法删除
		return false;
	}

	x = S.data[--S.top];
	return true;
}

bool GetTop(SqStack &S, Elemtype &e) {
	if (S.top == 0) {  //栈为空，无法读取
		return false;
	}
	e = S.data[S.top - 1];
	return true;
}

3.1.3.3 共享栈

为了提高空间的使用效率，利用栈底位置相对固定的特性，可以让两个顺序栈共享同一段一维数组空间，将两个站的栈底分别置于数组两端，栈顶向中间延伸，代码较为简单，不做详解，结构如图所示： 栈满条件为 top0 + 1 = top1 共享栈

3.1.5 链栈

使用链式存储的栈称为链栈，其优点是便于动态分配存储空间，不存在栈满溢出的问题。通常使用单链表实现链栈，并且规定所有的操作均在链表的表头进行。

链栈的实现和在《数据结构之绪论与线性表》讲述的单链表一模一样，所谓进出栈就是插入和删除头结点，当然也存在两种初始化方式（带和不带头结点），推荐使用不带头结点的初始化方式。

3.2 队列

3.2.1 队列的基本概念

队列（Queue） 简称队，仅允许在表的一段进行插入，而在另一端进行删除。

队列也是一种操作受限的线性表，符合现实中日常排队的规则，特点是先进先出（First In First Out，FIFO）,下面介绍栈的三个基本属性以及示意图：

队头： 允许删除的一端，也称队首。
队尾： 允许插入的一端。
空队列： 不含任何元素的队列。

队列示意图

3.2.2 队列的基本操作

采用严蔚敏版的命名规范：

InitQueue(&Q)：初始化一个空队列Q。
EnQueue(&Q,x)：入队操作，若队列未满，将x加入队尾。
DeQueue(&Q,x)：出队操作，若队列非空，删除队首元素，并通过x返回该值。
GetHead(Q,&x)：读取队首元素但不出队，若队非空，则通过x返回值。
QueueEmpty(Q)：判断队列是否为空，为空返回True，否则返回False。

3.2.3 顺序队列

顺序队列仅在尾指针指向下一个可存储位置的情况下进行讨论。

3.2.3.1 普通顺序队列

顾名思义，顺序队列即为使用顺序结构（数组）实现的队列，其初始化代码如下：

# define MaxSize 50
typedef struct {
	ElemType data[MaxSize];
	int front, rear; //队首指针和队尾指针
}SqQueue;

可以看见是定义了两个指针来进行出队和入队操作：

初始状态：Q.front == Q.rear == 0。
入队操作：队列未满时，Q.data[Q.rear] = x; Q.rear++;
出队操作：队列非空时，x = Q.data[Q.front]; Q.front++;

普通顺序队列 假溢出现象： 值得注意的是不能用 Q.rear == MaxSize 来表示队满情况，比如由上图(c)出队操作可知，元素出队后，前面明明有空闲空间却因为代码逻辑而不能够再进行利用，这时候如果再入队元素，则会出现 “上溢”，然而这种溢出并非真正的溢出，数组中有空闲空间，于是这种溢出称为假溢出。

3.2.3.1 循环队列

为了解决普通顺序队列的假溢出问题，引入了循环队列：将顺序空间在逻辑上组织为环状结构，通过取模运算实现。循环队列操作：

初始状态：Q.front == Q.rear == 0。
队首指针进1：Q.front = (Q.front + 1) % MaxSize
队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize
队列长度： (Q.rear + Q.front + MaxSize) % Maxsize（数论知识可证明）

前面说过在普通顺序队列里不能用 Q.rear == MaxSize 来表示队满情况，在循环队列里同样不能这样判断，判断队满有如下三种方式：

牺牲一个存储单元： 以 (Q.rear + 1) % MaxSize == Q.front来判断是否队满，为什么要牺牲一个存储单元这么进行判断呢，因为 Q.rear == Q.front 被用来进行判空操作了。
增设Size成员： 用一个Size成员来记录队列中的元素个数，队满条件： Q.Size == MaxSize，队空条件： Q.Size == 0。
增设tag标志位： 当前操作是出队操作将tag=0，当前操作是入队操作将tag=1。Q.rear == Q.front 时若是 tag = 1，即为队满；若是 tag = 0，即为队空。

循环队列操作（牺牲一个存储单元法）：

// （1）初始化
void InitQueue(SqQueue &Q) {
    // 初始化队首、队尾指针
    Q.rear = Q.front = 0;
}

// （2）判队空
bool QueueEmpty(SqQueue Q) {
    // 队空条件
    if (Q.rear == Q.front)
        return true;
    else
        return false;
}

// （3）入队
bool EnQueue(SqQueue &Q, ElemType x) {
    // 队满则报错
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = x;
    // 队尾指针加 1 取模
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

// （4）出队
bool DeQueue(SqQueue &Q, ElemType &x) {
    // 队空则报错
    if (Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

3.2.4 链式队列

链式队列顾名思义采用链表对队列进行实现，与链栈这种单指针管理模式更优相比，采用双指针的管理模式对链式队列的实现更加方便。双指针管理模式、不带头结点的单链表在《考研视角下的C语言(下)》中有详细提及，采用双指针管理模式、带头节点单链表实现链式队列的代码如下：

//链式队列的定义
typedef struct LinkNode {
	Elemtype data;
	struct LinkNode *next;
}LinkNode;

typedef struct {
	LinkNode *front, *rear;
}LinkQueue;

//链式队列的初始化
void InitQueue(LinkQueue& Q) {
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //建立头结点
	Q.front->next = NULL;  //初始化为空
}

//判队空
bool EmptyQueue(LinkQueue Q) {
	if (Q.front == Q.rear) {
		return true;
	}
	return false;
}

//入队
void EnQueue(LinkQueue& Q, Elemtype x) {
	LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));
	NewNode->data = x;
	NewNode->next = NULL;
	Q.rear->next = NewNode;
	Q.rear = NewNode;
}

//出队
bool DeQueue(LinkQueue& Q, Elemtype& x) {
	if (EmptyQueue(Q)) {  //判空
		return false;
	}
	LinkNode* p = Q.front->next;
	x = p->data;
	Q.front->next = p->next;
	if (p == Q.rear) {
		Q.rear = Q.front;  //若队伍中只有一个节点，两指针都指向头节点
	}
	free(p);
	return true;
}

3.2.5 双端队列

双端队列是一种允许在两端都进行插入和删除操作的线性表，双端队列的两端是平等的，为了便于理解，可将左端视为前端，右端视为后端。

细心观察不难得出,在输入输出不受限的双端队列中,几乎可以模仿前面讲过的栈、队列、共享栈的所有操作。在考研中双端队列最常考的题型就是 “判断输入输出的合法性” 举例如下：

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

如果我在IDE中有这样如下一段代码，对于括号该如何进行匹配？

void test() {
    int a[10][10];
    int x = 10*(20*(1+1)-(3-2));
    printf("加油！奥利给！");
}

显而易见，在编译器层面，正是使用栈这一数据结构来进行括号的匹配：若是匹配到左括号就压栈，若是匹配到合适的右括号就出栈，最后判断栈中是否为空来判断整段代码是否匹配成功。其逻辑示意图如下：栈在括号匹配中的应用

了解括号匹配的原理之后，我们还需了解如何在代码层面上实现括号匹配操作，代码如下，在考研中可以直接使用命名规范的函数作答但建议进行简要说明。

#include <stdbool.h>
#define MaxSize 10  // 定义栈中元素的最大个数
// 栈的结构体定义
typedef struct {
    char data[MaxSize];  // 静态数组存放栈中元素
    int top;             // 栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack &S);
// 判断栈是否为空
bool StackEmpty(SqStack S);
// 新元素入栈
bool Push(SqStack &S, char x);
// 栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x);

// 括号匹配检查函数
bool bracketCheck(char str[], int length) {
    SqStack S;
    InitStack(S);  // 初始化一个栈

    for (int i = 0; i < length; i++) {
        // 扫描到左括号，入栈
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]);
        } else {
            // 扫描到右括号，且当前栈空
            if (StackEmpty(S))
                return false;  // 匹配失败

            char topElem;
            Pop(S, topElem);  // 栈顶元素出栈

            // 检查括号是否匹配
            if (str[i] == ')' && topElem != '(')
                return false;
            if (str[i] == ']' && topElem != '[')
                return false;
            if (str[i] == '}' && topElem != '{')
                return false;
        }
    }
    // 检索完全部括号后，栈空说明匹配成功
    return StackEmpty(S);
}

3.3.2 栈在表达式求值中的应用

利用栈实现表达式的运算这种思想在计算机中是十分重要的，尤其是在CPU中（计算机组成原理内容）。注意：本节所描述的“左优先原则”和“右优先原则”以及“左右操作数”均为民间叫法，在考研简答题时不建议使用。

3.3.2.1 三种表达式介绍

首先介绍三种表达式即前缀（波兰式）、后缀（逆波兰式）、中缀三种表达式，其中中缀表达式就是我们现实中常见的表达式：

3.3.2.2 三种表达式机算（手算）

手动计算前缀和后缀表达式的过程其实就是将其转为中缀表达式的过程，示例如上图标注所示，运算规则如下：

前缀表达式： 从左向右扫描表达式，每次选取一个其前已经形成两个完整操作对象的运算符， 将这两个操作对象中靠左的作为左操作数、靠右的作为右操作数，按运算规则计算后，用结果替换该运算符及其两个操作对象，重复上述过程，直到整个表达式化为一个结果。
后缀表达式： 从左向右扫描表达式，每次选取一个其后已经形成两个完整操作对象的运算符， 将这两个操作对象中靠左的作为左操作数、靠右的作为右操作数，按运算规则计算后，用结果替换该运算符及其两个操作对象，重复上述过程，直到整个表达式化为一个结果。
中缀表达式：该怎么算怎么算。

3.3.2.3 中缀表达式转后缀表达式（手算，机算）

手算： 中缀表达式转后缀表达式可有多种结果，为了能够用算法实现（算法具有确定性），使结果唯一，于是采用 左优先原则：只要左边的运算符能够先运算，就先算左边的。 示意如下图所示：

机算： 在考研中为重点，可能考查运算到某一步时，栈里的状态怎么样。中转后机算

3.3.2.4 中缀表达式转前缀表达式（手算）

同样的道理，中缀表达式转前缀表达式采用 右优先原则：只要右边的运算符能够先运算，就先算右边的。 示意如下图所示：

3.3.2.5 后缀表达式机算

回归3.3.2节的标题，栈在表达式的求值中有什么作用？实际上中缀表达式只方便人类计算，而后缀表达式和前缀表达式更加方便机器计算。使用栈对后缀表达式机算规则如下： 从左到右，依次遍历表达式字符串，遇到操作数压入栈中。遇到运算符，则依次弹出两个操作数。以第一个弹出为右操作数，第二个弹出为左操作数。 计算结果入栈，最终栈中唯一元素即为结果。

3.3.2.6 前缀表达式机算

与后缀表达式机算稍有不同，规则如下： 从右到左，依次遍历表达式字符串，遇到操作数压入栈中。遇到运算符，则依次弹出两个操作数。以第一个弹出为左操作数，第二个弹出为右操作数。 计算结果入栈，最终栈中唯一元素即为结果。

3.3.2.7 中缀表达式机算

从逻辑上来说，中缀表达式机算=“中缀表达式转后缀表达式”+“后缀表达式机算”，我认为这种具有现实意义的考点可能为考察重点。其规则如下：

3.3.3 栈在递归中的应用

系统栈用来保存每一层递归调用的函数现场（包括参数、局部变量和返回地址），从而保证函数能按“先调用、后返回”的顺序正确执行。在《考研视角下的C语言(下)》中详细提及，这里做简单说明，普通函数与递归函数的压栈示意图如下：递归概念

3.3.4 队列的应用

3.3.4.1 树的层次遍历

树的层次遍历，即一层一层的对树进行遍历，其示意图如下：实现该遍历的算法会在之后的章节中介绍，这里介绍使用队列进行树的层次遍历思想：从根节点开始，将其入队；每次出队一个节点并访问它，然后按顺序将该节点的左右孩子（若存在）入队，直到队列为空。 以上图为题，过程如下：

1  //根节点入队
2 3  
3 4 5  //2出队，插入子节点
4 5 6 7
5 6 7  //4没有子节点，出队不必插入
6 7 8 9
7 8 9
8 9 10 11
9 10 11
10 11
11
空

3.3.4.2 图的广度优先遍历

图的广度优先遍历在这里暂时不需了解概念，示意如下：与树的层次遍历思想类似：从起始顶点开始，将其入队；每出队一个顶点并访问它，将与其相邻且尚未访问（或未入队）的顶点依次入队，直到队列为空。 以上图为题，过程如下：

1 //起始节点入队
2 3  //相邻节点入队
3 4
4 5 6
5 6
6 7 8
7 8
8 
空

3.3.4.3 操作系统中的应用

时间片轮转算法：按进程到达就绪状态的先后顺序进入就绪队列，始终从队首取出最先到达的进程运行。时间片用完的进程又插入队尾。这也是只有一个CPU却能同时运行多个进程的原因。

3.4 特殊矩阵的压缩存储

数组在内存中分为行优先存储和列优先存储，由编程语言决定。比如 C/C++ 为行优先存储，而MATLAB则为列优先存储。在《考研视角下的C语言(中)》中已详细介绍了一维数组和二维数组。普通矩阵直接使用二维数组初始化就行，但这里将会介绍几种特殊矩阵。

3.4.1 对称矩阵

若n阶方阵（行列数都相同），对于任何一个元素 a_i,j 都有 a_i,j 等于 a_j,i，则称该矩阵为对称矩阵。

对称矩阵自然而然能想到，我们只需存储上三角区（或下三角区）+ 主对角线元素即可，故数组的大小只需要 (n*n-n)/2 + n ，在代码层面实现只需使用一维数组，在需要访问未存储区域的元素时，写一个 “映射”函数 将二维数组下标转化为一维数组下标即可

3.4.2 三角矩阵

三角矩阵的定义如下：可以看见，三角矩阵和上方的对称矩阵大致相同，只需将上图有颜色的区域存入一维数组中，再在数组末尾存一个常数即可。

3.4.3 三对角矩阵

三对角矩阵，其定义如下：同样使用一维数组压缩存储，有两点需要注意： 知道行数 i 和列数 j ，怎么求出数组下标 k （从0开始）： a_i,j 是第 i 行第 j-i+2 个元素（只算带状区域内的），其前 i-1 行有 3*(i-1)-1 个元素（只算带状区域内的）。故 k 值为 2*i + j - 3 。 知道数组下标 K （从0开始），怎么求行数 i 和列数 j ： i = (向下取整)[(k + 1) / 3] + 1，j = k - 2*i + 3。

3.4.5 稀疏矩阵

稀疏矩阵是矩阵中非零元素个数远远小于总元素个数的矩阵

具体小多少，并没有一个具体的界限，靠经验判断。为了提高空间利用率，通常将每个非零元素的行、列、元素值合并成一个三元组(行标 i ,列标 j ,值 a_i,j)进行存储。下面介绍两种压缩方法：

3.4.5.1 数组存储

采用数组对三元组进行存储并不能够实现随机存储，因为需要一一对比，结构如下图所示：数组存储三元组

3.4.5.2 十字链表存储

一图胜千言，结构如下图所示，最常见的使用就是按行遍历和按列遍历，也非常适合频繁的插入和删除。十字链表

附言

参考文章：《数据结构之绪论与线性表》：http://mrlxl.cn/index.php/2026/02/04/test-11/ 《考研视角下的C语言(中)》：http://mrlxl.cn/index.php/2025/12/17/test-7/ 《考研视角下的C语言(下)》：http://mrlxl.cn/index.php/2026/01/24/test-9/

文档

数据结构之栈、队列和数组

数据结构之栈、队列和数组

第三章_栈、队列和数组

3.1 栈

3.1.1 栈的基本概念

3.1.2 栈的基本操作

3.1.3 栈的数学性质

3.1.4 顺序栈

3.1.3.1 顺序栈的定义

3.1.3.2 顺序栈的实现和基本操作

3.1.3.3 共享栈

3.1.5 链栈

3.2 队列

3.2.1 队列的基本概念

3.2.2 队列的基本操作

3.2.3 顺序队列

3.2.3.1 普通顺序队列

3.2.3.1 循环队列

3.2.4 链式队列

3.2.5 双端队列

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

3.3.2 栈在表达式求值中的应用

3.3.2.1 三种表达式介绍

3.3.2.2 三种表达式机算（手算）

3.3.2.3 中缀表达式转后缀表达式（手算，机算）

3.3.2.4 中缀表达式转前缀表达式（手算）

3.3.2.5 后缀表达式机算

3.3.2.6 前缀表达式机算

3.3.2.7 中缀表达式机算

3.3.3 栈在递归中的应用

3.3.4 队列的应用

3.3.4.1 树的层次遍历

3.3.4.2 图的广度优先遍历

3.3.4.3 操作系统中的应用

3.4 特殊矩阵的压缩存储

3.4.1 对称矩阵

3.4.2 三角矩阵

3.4.3 三对角矩阵

3.4.5 稀疏矩阵

3.4.5.1 数组存储

3.4.5.2 十字链表存储

附言

大纲