数据结构什锦（三）——栈与队列篇

这里我们来学习队列和栈的数据结构。

---

栈

什么是栈

栈（stack）是一个有序序列，只能在称为栈顶的一段进行数据的插入和删除的操作，最后一个插入的元素是第一个被删除的元素。所以栈也被称作“先进后出”表（LIFO）或“后进先出”表（FILO）。

对栈操作的方法有特殊的称呼。比如把数据插入栈，称为向栈压入（push）一个元素，而把数据从栈中删除，我们称为从栈弹出（pop）一个元素。从空栈中弹出元素会发生下溢（underflow），而向满栈压入元素会发生上溢（overflow）。我们把上溢和下溢统称为异常（exception）。

栈的抽象数据类型/ADT

为了简单起见，我们先把栈的内容数据类型设置为整形int。

操作

• Push(int data)：将元素data压入栈中
• int Pop()：从栈顶中弹出元素，并返回该元素的值。
• int Top()：返回栈顶元素的值，但是不删除该元素
• int Size()：返回栈中元素个数
• int IsEmptyStack()：判断栈是否为空
• int IsFullStack()：判断栈是否为满

异常

有时候栈的操作不能执行，比如向空栈中弹出元素或者向满栈中压入元素，此时Push()函数和Pop()函数无法正常执行，这时我们要求程序要抛出（throw）一个异常。

栈的应用

• 符号平衡
• 中缀表达式转后缀表达式
• 后缀表达式的计算
• 函数调用的实现
• 查找划分
• Web浏览器的访问历史
• 文本编辑器的撤销功能
• HTML和XML的标签匹配

栈的实现

栈的抽象数据类型有几种实现方法，下面我们介绍三种。

• 基于简单数组的实现
• 基于动态数组的实现
• 基于链表的实现

基于简单数组的实现

在数组中，我们从左向右的给数组添加元素，并使用一个辅助变量跟踪栈顶元素在数组中的下标。

数组实现的栈是会变满的，所以可能发生上溢异常。当数组为空时弹出元素也会发生下溢异常。

以下是代码的实现。

struct ArrayStack {
	int top;
	int capacity;
	int* array;//一个辅助指针指向栈顶
};
struct ArrayStack* CreateStack() {
	struct ArrayStack* S = malloc(sizeof(struct ArrayStack));
	if (!S)//如果创建新栈失败返回空
		return NULL;
	S->capacity = 1;//数组的容量，应该是初始化时可以更改的
	S->top - 1;//最开始空栈的top为-1代表不存在，一个元素时为0，对应数组的0下标
	S->array = malloc(S->capacity * sizeof(int));//声明一个数组用来储存压入栈的数据
	if (!S->array)
		return NULL;
	return S;
}

int IsEmptyStack(struct ArrayStack* S) {
	return(S->top == -1);//如果相等返回1，否则返回0
}

int IsFullStack(struct ArrayStack* S) {
	return(S->top == S->capacity - 1);//同上
}

void Push(struct ArrayStack* S, int data) {
	if (IsFullStack(S))
		printf("Stack overflow");
	else
		S->array[++S->top] = data;
	/*首先栈顶标识符自增，然后向数组对应下标存入元素*/
}

int Pop(struct ArrayStack* S) {
	if (IsEmptyStack(S)) {
		printf("Stack is empty");
		return 0;
	}
	else
		/*返回栈顶的元素，然后top减1*/
		return(S->array[S->top--]);
}

void DeleteStack(struct ArrayStack* S) {
	if (S) {
		if (S->array) {
			free(S->array);
		}
		free(S);
	}
}

这个方法存在一个局限性，就是数组的大小需要事先指定，而且超出数组大小时压入元素会发生上溢。

最后总结一下使用静态数组实现栈的思路。我们使用一个下标变量top，用它来指向栈中最近插入元素的位置。为了插入一个元素，我们增加top元素的值，并把新元素放到top指定的位置上。为了弹出一个元素，我们先返回top上的元素，然后让top减1。

基于动态数组的实现

因为使用静态数组时栈的大小有限制，会发生上溢异常。为了动态的调整栈的大小，我们可以使用动态数组，当我们使用动态数组时，我们有两种思路。

首先是当每一次栈满时，我们就把栈的大小加1。但这样会造成巨大的时间开销。假如我们的数组初始长度为1，最后长度为n-1，当满栈时我们就要新建一个长度为n的数组，然后将n-1个元素复制过来。而这之前我们已经过（1+2+……+n-1）次复制操作，这样的算法时间复杂度为O(n²)。

另一种方法就是重复翻倍的思想。每当栈满时，我们就创建一个长度为当前数组的两倍的数组，再将元素复制过去。这样我们的算法时间复杂度就变成了O(n)。

注意，过多的翻倍操作可能会导致内存上溢。

基于链表的实现

利用链表也可以实现栈。Push操作通过在链表的首部插入元素来实现，而Pop操作则是删除链表的头部元素来实现。

以下是代码实现。

struct Stack {
	int data;
	struct Stack* next;
};

struct Stack* CreateStack() {
	return NULL;
}

void Push(struct Stack** top, int data) {
	struct Stack* temp;
	temp = malloc(sizeof(struct Stack));

	if (!temp)//新节点申请不成功则返回空
		return NULL;

	temp->data = data;
	temp->next = *top;//新节点指向原头节点

	*top = temp;//修改头指针指向新节点
}

int IsEmptyStack(struct Stack* top) {
	return (top == NULL);
}

int Pop(struct Stack** top) {
	int data;
	struct Stack* temp;

	if (IsEmptyStack(top))
		return INT_MIN;//如果是空栈，则返回一个最小int值

	temp = *top;//临时变量储存要弹出的位置
	*top = (*top)->next;//将头指针指向下一个变量
	data = temp->data;

	free(temp);//释放弹出数据的位置
	return data;
}

int Top(struct Stack* top) {
	if (IsEmptyStack(top))
		return INT_MIN;

	return (top->next)->data;//返回栈顶元素
	/*注意这里top指向的节点是一个*/
}

void DeleteStack(struct Stack** top) {
	struct Stack* temp, * p;
	p = *top;//p为头指针的一个副本
	while (p->next) {
		//循环条件 p指向的下一个元素不为空
		temp = p->next;
		p->next = temp->next;
		free(temp);//释放临时变量指向的节点
	}
	free(p);//释放最后一个节点
}

队列

什么是队列

队列（queue）是一个有序序列，只能在序列的一段（rear）插入元素，而在另一端（front）进行删除操作。最先被插入的元素也是最先被删除的元素。所以队列又被称为“先进先出”表（FIFO）或者“后进后出”表（LILO）

与栈类似，队列的插入和删除也有特定的称谓。队列在队尾进行插入操作我们称为入列（EnQueue）操作，删除队首元素，我们称之为出列（Dequeue）操作。

对空队列执行出列操作称为下溢（underflow）错误，对满队列执行入列操作称为上溢（overflow）错误。这些错误统称为异常（exception）。

队列的抽象数据类型/ADT

假设数据元素为整形。

操作

• EnQueue(int data)：插入元素data到队列的队尾
• int DeQueue()：删除队首元素，并返回该元素的值
• int Front()：返回队首元素的值，但不删除首元素
• int QueueSize()：返回队列的元素个数
• int IsEmptyQueue()：判断队列是否为空

异常

和栈相同，对空队列执行DeQueue会抛出空队列异常，对满队列执行EnQueue会抛出满队列异常。

队列的应用

• 操作系统按照到达的顺序进行作业
• 模拟现实中的队列问题
• 异步数据传输
• 确定超市需要的收银员人数
• 算法的辅助数据结构
• 其他数据结构的组成部分

队列的实现

队列的实现与栈类似，有以下三种方法：

• 基于简单数组的实现
• 基于循环数组的实现
• 基于链表的实现

基于简单循环数组的实现

我们利用循环数组实现对队列ADT的简单实现，并用两个元素追踪队首和队尾元素。通常，用front指向队首元素，用rear指向队尾元素。

用来储存队列元素的数组可能会变满，此时EnQueue操作将抛出满队异常。同样的，对于空队列执行DeQueue操作将抛出空队异常。

初始化时，front和rear均指向-1，表示此时队列为空。

以下是实现的代码：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>

struct ArrayQueue {
	int front, rear;
	int capacity;
	int* array;
};

struct ArrayQueue *Queue(int size) {
	struct ArrayQueue* Q = malloc(sizeof(struct ArrayQueue));
	if (!Q)
		return NULL;//如果创建内存失败，返回空
	Q->capacity = size;//初始化队列的容量
	Q->front = Q->rear = -1;
	Q->array = malloc(Q->capacity * sizeof(int));//申请一片内存作为数组，来储存队列元素

	if (!Q->array)
		return NULL;//假如数组申请失败，则返回空
	return Q;//返回初始化成功的队列数据对象
}

int IsEmptyQueue(struct ArrayQueue* Q) {
	return(Q->front == -1);
}

int IsFullQueue(struct ArrayQueue* Q) {
	return((Q->rear + 1) % Q->capacity == Q->front);//如果队尾位置后即为队首说明队满
}

int QueueSize(struct ArrayQueue* Q) {
	return (Q->capacity - Q->front + Q->rear + 1) % Q->capacity;
}

void EnQueue(struct ArrayQueue* Q, int data) {
	if (IsFullQueue(Q)) {
		printf("Queue Overflow!");
	}
	else {
		Q->rear = (Q->rear + 1) % Q->capacity;
		Q->array[Q->rear] = data;
		if (Q->front == -1) {
			Q->front = Q->rear;
		}
	}
}

int DeQueue(struct ArrayQueue* Q) {
	int data = 0;//或者为Q中不存在的元素值
	if (IsEmptyQueue(Q)) {
		printf("Queue is empty!");
		return 0;
	}
	else {
		data = Q->array[Q->front];
		if (Q->front == Q->rear) {
			Q->front = Q->rear = -1;//对应队列中仅有一个元素的情况，删除后为空队列
		}
		else Q->front = (Q->front + 1) % Q->capacity;
	}
	return data;
}

void DeleteQueue(struct ArrayQueue* Q) {
	if (Q) {
		if (Q->array)
			free(Q->array);
		free(Q);
	}
}

局限性：队列的最大长度需要事先定义且不能更改，EnQueue满队时会产生满队异常。

基于动态循环数组的实现

动态循环数组的实现和简单循环数组大致相同，唯一的区别是加入了一个ResizeQueue函数用来调整预设循环数组的大小，代码如下：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>

struct ArrayQueue {
	int front, rear;
	int capacity;
	int* array;
};

struct ArrayQueue* Queue(int size) {
	struct ArrayQueue* Q = malloc(sizeof(struct ArrayQueue));
	if (!Q)
		return NULL;//如果创建内存失败，返回空
	Q->capacity = size;//初始化队列的容量
	Q->front = Q->rear = -1;
	Q->array = malloc(Q->capacity * sizeof(int));//申请一片内存作为数组，来储存队列元素

	if (Q->array)
		return NULL;//假如数组申请失败，则返回空
	return Q;//返回初始化成功的队列数据对象
}

int IsEmptyQueue(struct ArrayQueue* Q) {
	return(Q->front == -1);
}

int IsFullQueue(struct ArrayQueue* Q) {
	return((Q->rear + 1) % Q->capacity == Q->front);//如果队尾位置后即为队首说明队满
}

int QueueSize(struct ArrayQueue* Q) {
	return (Q->capacity - Q->front + Q->rear + 1) % Q->capacity;
}

void EnQueue(struct ArrayQueue* Q, int data) {
	if (IsFullQueue(Q)) {
		ResizeQueue(Q);//扩大数组，调整大小
	}
	else {
		Q->rear = (Q->rear + 1) % Q->capacity;
		Q->array[Q->rear] = data;
		if (Q->front == -1) {
			Q->front = Q->rear;
		}
	}
}

void ResizeQueue(struct ArrayQueue* Q) {
	int size = Q->capacity;
	Q->capacity = Q->capacity * 2;
	Q->array = realloc(Q->array, Q->capacity);//realloc函数会自动将原内存数据复制到一片新申请的空间上
	if (!Q->array) {
		printf("Memory Error");
		return;
	}
	if (Q->front > Q->rear) {
		//如果此时尾指针在首指针前，也就是队尾循环回到了队尾
		//但是作为一维数组来看，表现为队首指针到数组起点存在元素
		for (int i = 0; i < Q->front; i++)
		{
			Q->array[i + size] = Q->array[i];
		}
		Q->rear = Q->rear + size;
		//即把拓展后的循环数列“展开”，重新将尾指针移向头指针后
	}
}

int DeQueue(struct ArrayQueue* Q) {
	int data = 0;//或者为Q中不存在的元素值
	if (IsEmptyQueue(Q)) {
		printf("Queue is empty!");
		return 0;
	}
	else {
		data = Q->array[Q->front];
		if (Q->front == Q->rear) {
			Q->front = Q->rear = -1;//对应队列中仅有一个元素的情况，删除后为空队列
		}
		else Q->front = (Q->front + 1) % Q->capacity;
	}
	return data;
}

void DeleteQueue(struct ArrayQueue* Q) {
	if (Q) {
		if (Q->array)
			free(Q->array);
		free(Q);
	}
}

基于链表的实现

实现队列的另一种途径是利用链表。EnQueue操作可以通过在链表表尾插入元素实现，而DeQueue则可以通过删除链表首元素实现。

代码实现如下：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
	int data;
	struct ListNode* next;
};//定义了一个节点

struct Queue
{
	struct ListNode* front;
	struct ListNode* rear;
};

struct Queue* CreatQueue(void) {
	struct Queue* Q;
	struct ListNode* temp;
	Q = malloc(sizeof(struct Queue));

	if (!Q) {
		return NULL;
	}

	temp = malloc(sizeof(struct ListNode));
	Q->front = Q->rear = NULL;
	return Q;
}

int IsEmptyQueue(struct Queue* Q) {
	return(Q->front == NULL);
}

void EnQueue(struct Queue* Q, int data) {
	struct ListNode* newNode;
	newNode = malloc(sizeof(struct ListNode));
	if (!newNode)
		return NULL;
	newNode->data = data;
	newNode->next = NULL;
	if (Q->rear)Q->rear->next = newNode;
	Q->rear = newNode;

	if (Q->front == NULL)
		Q->front = Q->rear;//插入时队列为空的情况
}
int DeQueue(struct Queue* Q) {
	int data = 0;//或者队列中不存在的元素
	struct ListNode *temp;
	if (IsEmptyQueue(Q)) {
		printf("Queue is empty!");
		return 0;
	}
	else {
		temp = Q->front;
		data = Q->front->data;
		Q->front = Q->front->next;
		free(temp);
	}
	return data;
}

void DeleteQueue(struct Queue* Q) {
	struct ListNode* temp;
	while (Q->front) {
		temp = Q->front;
		Q = Q->front->next;
		free(temp);
	}
	free(Q);
}

完结咯(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤