【数据结构】栈（数组实现）和队列（链表实现）

栈

性质&定义

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

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

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

栈可以通过数组或者链表进行实现，但我们一般通过数组进行实现。因为如果用链表实现栈，链栈的插入操作就要在链表尾部进行，其时间复杂度为O(n)，效率较低，因此通常使用数组来实现栈这种数据结构。

栈的定义以及几个相关接口

// 支持动态增长的栈
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 GetStackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool 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

定义中可以看出，一个栈的结构体中包括了储存数据的数组，栈顶序号以及容量三个元素。其接口包含栈的初始化、出入栈、获取栈顶元素、获取栈中元素个数、判断栈是否为空和栈的销毁。

初始化栈

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}
1
2
3
4
5
6

初始化将栈的数组置空，容量和栈顶序号设为0。

入栈

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		int NewCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
		STDataType* tmp = (STDataType*)realloc(ps->_a, NewCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->_capacity = NewCapacity;
		ps->_a = tmp;
	}
	
	ps->_a[ps->_top] = data;
	ps->_top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

入栈时主要考虑的问题就是栈是否还有多余的容量，因此要进行判断。若没有多余空间了则对栈进行扩容，然后重新为其分配空间，而后进行入栈操作。相比而言，有容量情况下入栈操作就很简单的，只需将a数组中top位置的值设为要插入的值，然后移动top指针即可。

出栈

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->a);
	
	ps->_top--;
}
1
2
3
4
5
6
7

出栈操作和顺序表（因为二者都是数组实现）相同，只需要改变top指针即可，同时也需要保证栈不为空。

获取栈顶元素

STDataType GetStackTop(Stack* ps)
{
	assert(ps);

	return ps->_a[ps->_top - 1];
}
1
2
3
4
5
6

代码很简单易懂，无需多言。

获取栈中有效元素个数

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top;
}
1
2
3
4
5
6

因为最开始我们将top指针设置为0，每次入栈会使其+1，出栈使其-1，因此top值就是栈中元素的个数。

判空

bool StackEmpty(Stack* ps)
{
	assert(ps);

	if (ps->_top)
		return false;
	else
		return true;
}
1
2
3
4
5
6
7
8
9

道理同上，top是否为零决定了栈是否为空。

销毁

void StackDestroy(Stack* ps)
{
	assert(ps);

	STDataType* tmp = ps->_a;
	ps->_capacity = ps->_top = 0;
	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9

将指向数组a释放，指针置空，容量和栈顶序号置0，完成销毁。

队列

性质&定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数
组头上出数据，时间复杂度为O(n)，效率较低。

队列的定义以及几个相关接口

typedef int QDataType;
typedef struct QListNode
{
	QDataType _data;
	struct QListNode* _next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
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

由于要用链表实现队列，因此我们需要分别定义每个结点和整个队列结构。结点部分包括了数据和指向下一个结点的结构体指针，队列结构包含了两个指针，分别指向队列的头和尾。
关于队列的接口有以下功能：队列初始化，出入队列，获取队列的头/尾元素，获取队列有效元素个数，判空和队列销毁。实现如下：

初始化队列

void QueueInit(Queue* q)
{
	assert(q);

	q->_front = q->_rear = NULL;
}
1
2
3
4
5
6

顾名思义，是对于队列进行操作，将队列内的头尾指针置空即可。

入队

void QueuePush(Queue* q, QDataType data)
{
	assert(q);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->_next = NULL;
		newnode->_data = data;
	}
	if (q->_front == NULL && q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
}
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

入队要从队尾入。我们先新建一个结点，将其数据和next指针设置好，而后判断当前队列是否为空，如果为空，则使两个指针都指向新结点，若队列不为空，则将尾指针的next指向新结点，而后将尾指针指向新结点，由于在新建结点时我们已经将其next域置空，因此也不用担心链表最后出现野指针的问题。

出队

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front && q->_rear);

	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* del = q->_front;
		q->_front = q->_front->_next;
		free(del);
		del = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

出队要先保证队列不为空，然后再分为两种情况。若队列中只有一个元素了，即头尾指向同一元素，那么出队后要将二者置空；若队列中有两个或更多元素，则将front当前指向的元素进行备份，使front指向下一个元素，将备份元素free，则完成了出队操作。

获取队列头部/尾部元素

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);

	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);

	return q->_rear->_data;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

返回front指针或rear指针指向的元素即可。

统计有效元素个数

int QueueSize(Queue* q)
{
	assert(q);

	int count = 0;
	QNode* cur = q->_front;
	while (cur->_next)
	{
		count++;
		cur = cur->_next;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

用指针遍历队列，再用计数器进行计数即可。

判空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
	assert(q);
	if (q->_front == q->_rear && q->_front == NULL)
		return true;
	else
		return false;
}
1
2
3
4
5
6
7
8
9

判断空的条件就是二者皆为NULL

队列销毁

void QueueDestroy(Queue* q)
{
	assert(q);

	QNode* cur = q->_front;
	while(cur)
	{ 
		QNode* del = cur;
		cur = cur->_next;
		free(del);
		del = NULL;
	}
	q->_front = q->_rear = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

将队列中的结点逐个free掉，然后将头尾指针都置空，即可完成销毁。

结语

以上就是关于栈和队列的实现方式，如有不足或遗漏之处还请大家指正，笔者感激不尽；同时也欢迎大家在评论区进行讨论，一起学习，共同进步！