本文最后更新于：41 分钟前
栈和队列
栈及其特点和应用
栈和队列顺序栈的基本操作
同顺序表和链表一样，栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构。
栈只能从表的一端存取数据，另一端是封闭的；在栈中，无论是存数据还是取数据，都必须遵循”先进后出”的原则，即最先进栈的元素最后出栈。因此，我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，栈底元素指的是位于栈最底部的元素。
进栈和出栈
基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；
栈的具体实现
栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：
顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
链栈：采用链式存储结构实现栈结构；
两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。
栈的应用
基于栈结构对数据存取采用 “先进后出” 原则的特点，它可以用于实现很多功能。
例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：
重新搜索找到页面 A；
使用浏览器的”回退”功能。浏览器会先回退到页面 B，而后再回退到页面 A。
浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。
不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。
同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。
顺序栈基本操作（入栈和出栈）
入栈
|
int push(int* a,int top,int elem){
a[++top]=elem;
return top;
}
|
代码中的 a[++top]=elem，等价于先执行 ++top，再执行 a[top]=elem。
出栈
|
int pop(int * a,int top){
if (top==-1) {
printf("空栈");
return -1;
}
printf("弹栈元素：%d\n",a[top]);
top--;
return top;
}
|
代码中的 if 语句是为了防止用户做 “栈中已无数据却还要数据出栈” 的错误操作。代码中，关于对栈中元素出栈操作的实现，只需要 top 值 -1 即可。
总结
顺序栈及对数据基本操作的 C 语言完整代码：
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
| #include <stdio.h>
//元素elem进栈
int push(int* a,int top,int elem){
a[++top]=elem;
return top;
}
//数据元素出栈
int pop(int * a,int top){
if (top==-1) {
printf("空栈");
return -1;
}
printf("弹栈元素：%d\n",a[top]);
top--;
return top;
}
int main() {
int a[100];
int top=-1;
top=push(a, top, 1);
top=push(a, top, 2);
top=push(a, top, 3);
top=push(a, top, 4);
top=pop(a, top);
top=pop(a, top);
top=pop(a, top);
top=pop(a, top);
top=pop(a, top);
return 0;
}
|
程序输出结果为：
| 弹栈元素：4
弹栈元素：3
弹栈元素：2
弹栈元素：1
空栈
|
链栈基本操作（入栈和出栈）
通常我们将链表的头部作为栈顶，尾部作为栈底，将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。
链表的头部作为栈顶，意味着：
在实现数据”入栈”操作时，需要将数据从链表的头部插入；
在实现数据”出栈”操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
链栈元素入栈
例如，将元素 1、2、3、4 依次入栈，等价于将各元素采用头插法依次添加到链表中
C语言实现代码为：
|
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
lineStack * line=(lineStack*)malloc(sizeof(lineStack));
line->data=a;
line->next=stack;
stack=line;
return stack;
}
|
链栈元素出栈
实现栈顶元素出链栈的 C 语言实现代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
lineStack * pop(lineStack * stack){
if (stack) {
lineStack * p=stack;
stack=stack->next;
printf("出栈元素：%d ",p->data);
if (stack) {
printf("新栈顶元素：%d\n",stack->data);
}else{
printf("栈已空\n");
}
free(p);
}else{
printf("栈内没有元素");
return stack;
}
return stack;
}
|
代码中通过使用 if 判断语句，避免了用户执行”栈已空却还要数据出栈”错误操作。
总结
通过采用头插法操作数据的单链表实现了链栈结构，完整的链栈及基本操作代码：
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
| #include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
lineStack * line=(lineStack*)malloc(sizeof(lineStack));
line->data=a;
line->next=stack;
stack=line;
return stack;
}
lineStack * pop(lineStack * stack){
if (stack) {
lineStack * p=stack;
stack=stack->next;
printf("弹栈元素：%d ",p->data);
if (stack) {
printf("栈顶元素：%d\n",stack->data);
}else{
printf("栈已空\n");
}
free(p);
}else{
printf("栈内没有元素");
return stack;
}
return stack;
}
int main() {
lineStack * stack=NULL;
stack=push(stack, 1);
stack=push(stack, 2);
stack=push(stack, 3);
stack=push(stack, 4);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
return 0;
}
|
程序运行结果为：
| 弹栈元素：4 栈顶元素：3
弹栈元素：3 栈顶元素：2
弹栈元素：2 栈顶元素：1
弹栈元素：1 栈已空
栈内没有元素
|
队列及其应用
队列的两端都”开口”，要求数据只能从一端进，从另一端出，通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。不仅如此，队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。
队列的实现
队列存储结构的实现有以下两种方式：
顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
队列的实际应用
实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
栈和队列不要混淆，栈结构是一端封口，特点是”先进后出”；
而队列的两端全是开口，特点是”先进先出”。
顺序队列及其操作
顺序队列，即采用顺序表模拟实现的队列结构。
由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。
当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。
此方法存在的问题
整个顺序队列在数据不断地进队出队过程中，在顺序表中的位置不断后移。
顺序队列整体后移造成的影响是：
顺序队列之前的数组存储空间将无法再被使用，造成了空间浪费；
如果顺序表申请的空间不足够大，则直接造成程序中数组 a 溢出，产生溢出错误；
为了解决以上两个问题，可以将顺序表打造成一个环状表，即环状顺序队列
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
| #include <stdio.h>
#define max 5
int enQueue(int *a,int front,int rear,int data){
if ((rear+1)%max==front) {
printf("空间已满");
return rear;
}
a[rear%max]=data;
rear++;
return rear;
}
int deQueue(int *a,int front,int rear){
if(front==rear%max) {
printf("队列为空");
return front;
}
printf("%d ",a[front]);
front=(front+1)%max;
return front;
}
int main() {
int a[max];
int front,rear;
front=rear=0;
rear=enQueue(a,front,rear, 1);
rear=enQueue(a,front,rear, 2);
rear=enQueue(a,front,rear, 3);
rear=enQueue(a,front,rear, 4);
front=deQueue(a, front, rear);
rear=enQueue(a,front,rear, 5);
front=deQueue(a, front, rear);
rear=enQueue(a,front,rear, 6);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
front=deQueue(a, front, rear);
return 0;
}
|
程序运行结果：
1 2 3 4 5 6
使用此方法需要注意的是，顺序队列在判断数组是否已满时，出现下面情况：
当队列为空时，队列的头指针等于队列的尾指针；
当数组满员时，队列的头指针等于队列的尾指针；
顺序队列的存储状态不同，但是判断条件相同。为了对其进行区分，最简单的解决办法是：牺牲掉数组中的一个存储空间，判断数组满员的条件是：尾指针的下一个位置和头指针相遇，就说明数组满了，即程序中第 5 行所示。
链式队列及基本操作
链式队列，简称”链队列”，即使用链表实现的队列存储结构。
链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为 top 和 rear）分别指向链表中队列的队头元素和队尾元素。在链式队列的初始状态，此时队列中没有存储任何数据元素，因此 top 和 rear 指针都同时指向头节点。
| /链表中的节点结构
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
QNode * initQueue(){
QNode * queue=(QNode*)malloc(sizeof(QNode));
queue->next=NULL;
return queue;
}
|
链式队列数据入队
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：
将该数据元素用节点包裹，例如新节点名称为 elem；
与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
最后移动 rear 指针指向该新节点，即 rear=elem；
| QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
rear->next=enElem;
rear=enElem;
return rear;
}
|
链式队列数据出队
当链式队列中，有数据元素需要出队时，按照 “先进先出” 的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。
链式队列中队头元素出队，需要做以下 3 步操作：
通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
将 p 节点（即要出队的队头节点）从链表中摘除；
释放节点 p，回收其所占的内存空间；
| void DeQueue(QNode * top,QNode * rear){
QNode * p=NULL;
if (top->next==NULL) {
printf("队列为空");
return ;
}
p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
|
注意，将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。
总结
链式队列入队和出队的完整代码：
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
| #include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
QNode * initQueue(){
QNode * queue=(QNode*)malloc(sizeof(QNode));
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
QNode * p = NULL;
if (top->next==NULL) {
printf("\n队列为空");
return rear;
}
p=top->next;
printf("%d ",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
int main() {
QNode * queue,*top,*rear;
queue=top=rear=initQueue();
rear=enQueue(rear, 1);
rear=enQueue(rear, 2);
rear=enQueue(rear, 3);
rear=enQueue(rear, 4);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
return 0;
}
|
程序运行结果为：
1 2 3 4
队列为空