【初阶数据结构】先来后到的秩序：栈和队列

栈的概念及结构

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

数组可以用来实现栈，但这并不意味着栈的本质就是数组。数组是一种连续存储元素的数据结构，使用数组实现栈时，利用数组的索引来模拟栈的操作

typedef int STDataType;

typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

栈接口实现

栈初始化

void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc mail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0; //top是栈顶元素的下一个位置
	//ps->top = 1; //top是栈顶元素位置
}

如果 top 为 0，top 指向的是下一个可以插入元素的位置。入栈操作时，直接将元素放入 top 位置，然后将 top 的值加 1；出栈操作时，先将 top 的值减 1，然后返回 top 位置的元素

如果 top 为 1，top 指向的就是插入元素的位置

栈销毁

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

很常规的栈销毁操作，记得指针要释放后置空

栈顶删除

void STPop(ST* ps)
{
	assert(ps);
	assert(STEmpty(ps));
	ps->top--;
}

栈顶指针减 1，相当于移除栈顶元素

栈顶插入

void STPush(ST* ps, STDataType x)
{
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("malloc mail");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[ps->top++] = x;
}

先检查栈的当前容量是否已满，如果已满则使用 realloc 函数将栈的容量扩大为原来的两倍，之后将新元素压入栈顶，并更新栈顶指针

栈的个数

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

这里栈是用数组实现的，top 指的是栈顶的下一个元素，所以索引就是栈的元素个数

栈的判空

int STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0 ? 0 : 1;
}

如果为空，就返回 0，那么条件就不会执行；如果不为空，就返回 1 ，条件正常执行

栈顶获取

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(STEmpty(ps));
	return ps->a[ps->top - 1];
}

top - 1 表示最后一个元素，即栈顶元素

队列的概念及结构

队列和我们字面上理解一样，先进入队列的元素会先被处理，后进入的元素会在队列尾部等待

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

🚩入队列： 进行插入操作的一端称为队尾

🚩出队列： 进行删除操作的一端称为队头

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低

由于是链式结构，所以每个元素还是以节点的形式体现，指向队列头部节点的指针 head、指向队列尾部节点的指针 tail 以及记录队列中元素数量的 size

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

队列接口实现

队列初始化

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

队列的头部指针 head 和尾部指针 tail 都设置为 NULL，表示队列为空，同时将队列的元素数量 size 初始化为 0

队列销毁

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

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

因为每个节点都存储了指向下一个节点的指针，所以需要先存储节点，再释放节点

队列插入

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

入列只能从尾入

队列为空：
if (pq->head == NULL)：判断队列是否为空
assert(pq->tail == NULL)：若队列为空，断言队尾指针也为空，确保队列状态的一致性
pq->head = pq->tail = newnode：将队列的头指针和尾指针都指向新节点，此时队列中只有一个元素
队列非空：
pq->tail->next = newnode：将新节点连接到队尾节点的后面
pq->tail = newnode：更新队尾指针，使其指向新节点

注意要先链接，后移动尾指针，否则找不到链接的节点 next 指针

队列删除

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	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;
	}
	
	pq->size--;
}

出列只能从头出，保存队列头部节点的下一个节点指针，释放队列头部节点的内存，将队列头部指针更新为原头部节点的下一个节点

队列元素个数

void QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

队列判空

int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0 ? 0 : 1;
}

如果为空，就返回 0，那么条件就不会执行；如果不为空，就返回 1 ，条件正常执行

队头获取

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;
}

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现

栈和队列习题

选择题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ B ）
A 12345ABCDE
B EDCBA54321
C ABCDE12345
D 54321EDCBA
2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ C ）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（ D ）
A 1
B 2
C 99
D 0或者100
4.以下( B )不是队列的基本运算？
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)( B )
A (rear - front + N) % N + 1
B (rear - front + N) % N
C (rear - front) % (N + 1)
D (rear - front + N) % (N - 1)

解析

1. 栈是一种后进先出（LIFO）的数据结构。元素依次入栈后，最后入栈的元素会最先出栈。这里元素 1、2、3、4、5、A、B、C、D、E 依次入栈，那么出栈顺序就应该是 E 最先出栈，接着是 D、C、B、A、5、4、3、2、1，所以答案是 B

2. A 选项 1,4,3,2：1 进栈，1 出栈；2、3、4 依次进栈，然后 4、3、2 依次出栈，该出栈序列是可能的
   B 选项 2,3,4,1：1、2 进栈，2 出栈；3 进栈，3 出栈；4 进栈，4 出栈；最后 1 出栈，该出栈序列是可能的
   C 选项 3,1,4,2：3 要先出栈，那么 1、2、3 必须先依次进栈，3 出栈后，栈顶元素是 2，此时只能 2 出栈，而不能 1 出栈，所以该出栈序列不可能
   D 选项 3,4,2,1：1、2、3 进栈，3 出栈；4 进栈，4 出栈；然后 2、1 依次出栈，该出栈序列是可能的

3. 在循环队列中，当 front = rear 时，有两种情况：
   队列为空： 初始状态 front = rear 表示队列是空的。经过一系列操作后又出现 front = rear，有可能队列又变回了空的状态
   队列为满： 循环队列中，当队列满时也会出现 front = rear 的情况。对于长度为 100 的循环队列，当入队和出队操作使得队列刚好满一圈时，也会出现 front = rear。所以元素个数可能是 0 或者 100，答案选 D

4. 队列是一种先进先出（FIFO）的数据结构，其基本运算有：
   入队： 从队尾插入一个新元素，对应选项 A
   出队： 从队头删除元素，而不是删除第 i 个元素，选项 B 不符合队列的基本运算规则
   判断队列是否为空，对应选项 C
   读取队头元素的值，对应选项 D，所以答案是 B

5. 计算循环队列中元素的有效长度需要考虑 rear 和 front 的相对位置
   当 rear >= front 时，队列中元素的个数为 rear - front
   当 rear < front 时，队列中元素的个数为 rear - front + N（因为是循环队列，需要加上队列的长度 N 来计算实际元素个数）
   综合这两种情况，可以使用 (rear - front + N) % N 来统一计算队列中元素的有效长度。因为取模运算可以处理 rear 和 front 的各种相对位置关系，所以答案选 B

编程OJ题

1. 括号匹配问题。OJ链接
2. 用队列实现栈。OJ链接
3. 用栈实现队列。OJ链接
4. 设计循环队列。OJ链接

代码展示

栈

传送门：Gitee栈代码

Stack.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//	int capacity;
//}ST;

typedef int STDataType;

typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);

void STDestroy(ST* ps);

void STPop(ST* ps);

void STPush(ST* ps, STDataType x);

int STSize(ST* ps);

int STEmpty(ST* ps);

STDataType STTop(ST* ps);

7.1.2 Stack.c

#define _CRT_SECURE_NO_WARNINGS

#include "Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc mail");
		return;
	}
	ps->capacity = 4;
	ps->top = 0; //top是栈顶元素的下一个位置
	//ps->top = 1; //top是栈顶元素位置
}

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void STPop(ST* ps)
{
	assert(ps);
	assert(STEmpty(ps));
	ps->top--;
}

void STPush(ST* ps, STDataType x)
{
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("malloc mail");
			return;
		}

		ps->a = tmp;
		ps->capacity *= 2;
	}

	ps->a[ps->top++] = x;
}

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

int STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0 ? 0 : 1;
}

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(STEmpty(ps));
	return ps->a[ps->top - 1];
}

队列

传送门：Gitee队列代码

Queue.h

#pragma once

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

typedef struct BinaryTreeNode* QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(QNode* pq);

void QueueDestroy(QNode* pq);

void QueuePush(QNode* pq, QDataType x);

void QueuePop(QNode* pq);

void QueueSize(QNode* pq);

int QueueEmpty(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"

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

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

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

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	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;
	}

	pq->size--;
}

void QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0 ? 0 : 1;
}

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;
}

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！