数据结构-栈和队列详解_栈和队列数据结构

本篇主要介绍了栈和队列这两种数据结构，了解他们的原理和区别，并且会讲解如何用C语言实现他们的主要接口

栈

什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
我来画个图大伙感受一下

上图就是数据进栈和出栈的过程，根据栈的概念，如果我们想要依次在栈里插入a1，a2，a3三个数据，那么只能从栈顶插入，插入完成后栈内数据的存储如图所示，先插入的数据在栈底，后插入的数据在栈顶，在我们想要删除元素时，也只能从开始栈顶删除，所以只能先删除a3，这时a2就成为了新的栈顶，然后再根据栈的规律进行我们想要的操作。
刚刚我们向栈里插入数据的操作就叫做压栈，进栈或入栈。入数据在栈顶。
栈的删除操作叫做出栈。出数据也在栈顶。

栈的实现

栈的实现一般可以使用数组或链表，下面我画两个图来直看一下这数组和链表是这么实现栈的。
首先是数组：

使用数组时，我们把数组的一侧作为栈底，另一侧当作栈顶，然后记录下栈顶的下标，插入和删除数据在栈顶操作就可以了
链表：

使用链表我们就需要每个节点有两个成员，一个存储数据，一个指向前一个节点以用来把栈连接起来。插入和删除数据只需要在栈顶链接新节点或销毁节点即可。
下面我们以数组为例实现一个栈。
为了让栈的大小可以扩大，我们需要动态开辟一个数组，根据上面的图我们可以知道，一个栈我们需要有数组，栈顶的下标和栈的容量三个元素，所以我们先创建一个结构体类型

typedef int STDataType;
struct Stack
{
	STDataType* a;
	int top;
	int capacity;
};
typedef struct Stack Stack;
1
2
3
4
5
6
7
8

用typedef重命名类型，以便于我们切换栈中元素的类型（老套路了）。
然后重命名结构体类型为Stack。
下面我们就来实现一下栈的接口。

初始化接口

初始化一个栈

void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = (STDataType*)malloc(4 * sizeof(STDataType));
	pst->top = 0;
	pst->capacity = 4;
}
1
2
3
4
5
6
7

首先给数组开辟可以存4个数据的空间（大小随意），然后把容量置为开辟的空间的大小，因为现在没有数据，所以栈顶就是数组第一个元素的位置，下标为0。

销毁接口

因为我们的数组是动态开辟的，所以使用完后要对栈进行销毁

void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
}
1
2
3
4
5
6

释放数组的空间，把容量和栈顶下标都置为0

入栈

向栈中插入一个数据

void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//结束程序
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.首先我们要判断数组是否已经满了，如果满了，那我们就要对数组进行增容，我们还是以二倍的大小来增容（增加二倍的原因是为了避免过分频繁的增容造成性能消耗与增容太大的空间造成空间浪费，详情请见数据结构-动态顺序表的实现–检查是否增容接口）如果增容失败就打印一下失败的原因（方便程序出现bug我们调试），然后退出程序。成功就改变和容量。
2.把数组下标为top的元素置为指定值，然后top向后移动一位。

出栈

删除一个栈里的数据

void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}
1
2
3
4
5
6

1.先声明一下栈不为空，这里的判断栈是否为空的接口我们后面会实现，这里先使用它，并不影响，只要我们后面写了那个接口就行。
2.把栈顶的指针向前移动一位就好（这时下标为top的元素为我们原本栈顶的元素，但是我们认为栈顶的数据就是top前面的那一位，所以只要我们移动了top的位置，那么下标为top的元素的值是多少对我们来说就不重要了，所以我们不需要实际的删除那个数据）。

获取栈顶元素

返回栈顶的元素

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
1
2
3
4
5
6

1.声明栈不为空。
2.返回top前一个位置的元素。

检测栈是否为空

bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}
1
2
3
4
5

如果top=0，那么栈为空，不为零则栈不为空。

获取栈的元素个数

int StackSize(Stack* pst)
{
	assert(pst);
	return pst->top;
}

1
2
3
4
5
6

下标top的值就代表了栈中有效数据的个数。

栈的全部代码

Stack.h

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int STDataType;
struct Stack
{
	STDataType* a;
	int top;
	int capacity;
};

typedef struct Stack Stack;

void StackInit(Stack* pst);

void StackDestory(Stack* pst);
//性质决定了在栈顶进出
void StackPush(Stack* pst, STDataType x);

void StackPop(Stack* pst);

STDataType StackTop(Stack* pst);

bool StackEmpty(Stack* pst);

int StackSize(Stack* pst);
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

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void StackInit(Stack* pst)
{
	assert(pst);
	//pst->a = NULL;
	//pst->top = 0;
	//pst->capacity = 0;
	pst->a = (STDataType*)malloc(4 * sizeof(STDataType));
	pst->top = 0;
	pst->capacity = 4;
}

void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->capacity = pst->top = 0;
}

void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//结束程序
		}
		pst->a = tmp;
		pst->capacity *= 2;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

void StackPop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	pst->top--;
}

STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}

bool StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0;
}

int StackSize(Stack* 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
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

队列

队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
我们还是画个图来观察一下队列的结构：

在队尾插入数据，在队头删除数据

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队时我们就需要把数组后面的元素都向前移动一位来覆盖第一个元素以实现删除队头元素的目的，效率比较低。
我们再看一张图来感受一下数组是如何实现队列的：

这个队列是由节点组成的，每个节点包含数据和指针两个元素，数据即用来存放数据，指针用来指向队尾方向的节点以实现把队列连接起来的任务。
而队列本身又是由一个指向队头的指针和一个指向队尾的指针组成，所以我们在创建队列的结构体类型时需要先创建一个链表的类型，再创建一个队列的类型如下图。

typedef int QDataType;
//单链表构成的队列
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
//指向队列头尾的两个指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13

下面就是队列的一些主要接口的实现。

初始化接口

初始化一个队列

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
1
2
3
4
5

因为是初始化一个队列，所以队列里并没有元素，所以队头和队尾都是空。

销毁接口

销毁一个队列

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

因为链表中每个节点都是动态开辟的，所以销毁链表时我们要从队头开始，挨个释放每一个节点，如何把队头和队尾的指针置空。

入队接口

根据队列的性质，入队即在队尾插入数据。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.首先我们要先创建一个节点，如何判断是否创建成功。
2.把节点的值赋为指定值，先让它指向空。
3.判断队列中是否有节点，如果这时队列中没有节点，那么队列的尾指针就应该是指向空的，这时刚刚创建出来的节点就是队头，同时也是队尾，两个指针同时指向它。
4.如果队列不为空，那么队尾的节点就指向新节点，如何新节点作为队尾。

出队接口

根据队列的性质，出队即从队头删除数据

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.我们又用到了老方法，先用判断是否为空的接口声明队列不为空（后面会实现该接口）。
2.如果我们的队列只有一个节点，那么删除后就变成了一个空队列，那我们就是否这个节点，然后让两个指针指向空。
3.如果队列有两个及以上的节点，那么我们就释放队头的节点，然后让队头后面的节点做队头即可。

获取队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
1
2
3
4
5
6

非常简单，直接通过指针拿到队头的元素，需要注意的是要对空队列进行一下声明，否则会造成对空指针的引用。

获取队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
1
2
3
4
5
6

与上面类似，只是这次是用队尾的指针。

判断是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
1
2
3
4
5

如果一个队列为空，那么它的头指针肯定是空，因为头指针是指向队列的头的，所以可以通过头指针判断队列是否为空。

返回队列大小

返回一个队列含有的节点个数

int QueueSize(Queue* pq)
{
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11

从队头开始，依次向后遍历，每遍历一个节点就让大小加一，直到遍历到队尾。

队列的全部代码

Queue.h

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int QDataType;
//单链表构成的队列
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
//指向队列头尾的两个指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);

void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType x);

void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

int QueueSize(Queue* pq);
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

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

int QueueSize(Queue* pq)
{
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
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

以上就是本篇的全部内容。