数据结构初步（八）- 线性表之栈和队列的解析与实现

怠惰的未禾

发布于 2023-04-27 21:35:07

2310

发布于 2023-04-27 21:35:07

文章被收录于专栏：Linux之越战越勇Linux之越战越勇

前言

本节继续数据结构的学习，看一看栈和队列的概念。

1. 栈 - Stack

1.1 概念

栈是一种特殊的线性表，只允许在一端进行插入和删除元素的操作。栈顶：数据插入和删除操作的一端。 栈底：和栈顶相对的一端。栈中的元素遵守后进先出Last In First Out的规则。压栈/进栈/入栈：在栈顶的插入操作。出栈/弹栈：在栈顶的删除操作。

注意：

数据结构中的栈与内存中的栈(由操作系统使用)是两个不同的概念，二者相同的是遵守相同的数据插入与数据删除规则：后进先出Last In First Out。

1.2 栈的结构

数据结构的栈就像按顺序放入箱子中的书本，先放进去的书被压在了底下；从箱子中拿书。先拿到的是最上面的后放进去的书，先放进去的书反而是最后拿到。

1.3 栈功能分析

栈的结构只需要遵守先入后出的规则即可。栈顶与栈底的位置是相对的。栈的实现既可以使用顺序表，也可以使用链表。顺序表实现栈相比链表更有优势，顺序表实现方式更多，当然链表也可以实现栈。

顺序表实现栈，需要特别注意一下栈顶下标所在初始的位置，初始位置不同，出栈同一个元素操作也有差别。 栈顶下标初始为-1

栈顶下标初始为0

1.4 顺序表实现栈

1. 防止头文件被重复包含

条件编译指令：

#ifndef __STACK__H__
#define __STACK__H__
//...
#endif

#pragma once

2. 头文件的包含

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

3. 栈的封装

对于顺序表，尾删、尾插操作效率很高。如果把顺序表起始出(0下标处)作为栈底，那么顺序表的尾插，尾删操作就对应于栈的入栈和出栈操作。

typedef int STDataType;
typedef struct Stack {
	STDataType* data;
	int top;
	int capacity;
}ST;

栈中栈底一定在0下标处，只需要标记栈顶位置；对于动态顺序表，还需要一个通用数据类型的指针STDataType*用于开辟储存数据的空间，变量capacity记录顺序表的容量。

4. 栈的初始化

函数接受外部栈的地址，产生其副本pst，因为并不需要改变外部栈本身，改变的是栈内部的成员。由于定义的栈是一个结构体，所以栈的地址一定存在，所以需要对传入的栈的地址进行暴力断言判断是否为NULL。
初始化成员指针pst->data指向NULL，栈顶下标和容量都为0。

//初始化
void StackInit(ST* pst) {
	assert(pst);
	pst->data = NULL;
	pst->top = pst->capacity = 0;
}

5. 入栈操作(尾插数据)

//入栈
void StackPush(ST* pst, STDataType val) {
	assert(pst);
	//扩容
	if (pst->top == pst->capacity) {
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newCapacity);
		if (!tmp) {
			perror("StackPush");
		}
		pst->data = tmp;
		pst->capacity = newCapacity;
	}
	pst->data[pst->top] = val;
	++pst->top;
}

元素入栈之前，需要先判断栈的容量是否足够，如果不够就扩容。我们初始化栈顶下标pst->top为0，注意数据在入栈时先放入pst->top处，然后pst->top加1。

6. 出栈操作(尾删数据)

//出栈
void StackPop(ST* pst) {
	assert(pst);
	assert(!StackEmpty(pst));
	--pst->top;
}

出栈操作之前，需要先检查栈是否为空，这里用了暴力检查assert()；如果栈为空就不能继续删除数据。

7. 取出栈顶元素

//取出栈顶元素
STDataType StackTop(ST* pst) {
	assert(pst);
	return pst->data[pst->top -1];
}

注意栈的栈顶pst->top初始化是0还是-1： pst->top初始化是0，取出的是pst->top-1位置的元素； pst->top初始化是-1，取出的是pst->top位置的元素。

8. 判断栈是否是空

//判断栈是否是空
bool StackEmpty(ST* pst) {
	assert(pst);
	return pst->top == 0;
}

注意栈的栈顶pst->top初始化是0还是-1： pst->top初始化是0，那么pst->top等于0栈就是空； pst->top初始化是-1，那么pst->top等与-1就是空。

9. 返回栈的大小

//返回栈的大小
int StackSize(ST* pst) {
	assert(pst);
	return pst->top;
}

注意栈的栈顶pst->top初始化是0还是-1： pst->top初始化是0，那么pst->top的值就是栈元素的个数，也就是栈的大小； pst->top初始化是-1，那么pst->top + 1的值才是栈元素的个数，也就是栈的大小。

栈的销毁

//销毁栈
void StackDestroy(ST* pst) {
	assert(pst);
	free(pst->data);
	pst->top = pst->capacity = 0;
}

手动释放栈内部指针成员pst->data动态申请的空间。

1.4 栈的C语言实现

分文件实现头文件Stack.h

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

typedef int STDataType;
typedef struct Stack {
	STDataType* data;
	int top;
	int capacity;
}ST;

//初始化
void StackInit(ST* pst);

//销毁栈
void StackDestroy(ST* pst);

//入栈
void StackPush(ST* pst, STDataType val);

//出栈
void StackPop(ST* pst);

//取出栈顶元素
STDataType StackTop(ST* pst);

//判断栈是否是空
bool StackEmpty(ST* pst);

//返回栈的大小
int StackSize(ST* pst);

源文件Stack.c

//初始化
void StackInit(ST* pst) {
	assert(pst);
	pst->data = NULL;
	pst->top = pst->capacity = 0;
}

//销毁栈
void StackDestroy(ST* pst) {
	assert(pst);
	free(pst->data);
	pst->top = pst->capacity = 0;
}

//入栈
void StackPush(ST* pst, STDataType val) {
	assert(pst);
	//扩容
	if (pst->top == pst->capacity) {
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->data, sizeof(STDataType) * newCapacity);
		if (!tmp) {
			perror("StackPush");
		}
		pst->data = tmp;
		pst->capacity = newCapacity;
	}
	pst->data[pst->top] = val;
	++pst->top;
}

//出栈
void StackPop(ST* pst) {
	assert(pst);
	assert(!StackEmpty(pst));
	--pst->top;
}

//取出栈顶元素
STDataType StackTop(ST* pst) {
	assert(pst);
	return pst->data[pst->top -1];
}

//判断栈是否是空
bool StackEmpty(ST* pst) {
	assert(pst);
	return pst->top == 0;
}

//返回栈的大小
int StackSize(ST* pst) {
	assert(pst);
	return pst->top;
}

2. 队列 - Queue

2.1 概念

队列是只允许在一端进行插入数据的操作，在另一端进行删除数据的操作的线性表。队列遵守先进先出First In First Out的规则。 队头：进行删除操作的一端。 队尾：进行插入操作的一端。 入队列：在队尾的插入数据的操作。 出队列：在对头的删除数据的操作。

2.2 结构

队列就像是穿过隧道的火车，火车从一端的隧道口驶入，一般只能从另一端的隧道口驶出，火车头先于火车尾从另一端隧道出来。也像是去银行办理业务时拿到的叫号单，先去银行的人叫号单上的数字靠前，后去银行的人的叫号单上的数字靠后；也就是先去的先办理业务先离开，后去的后办理业务后离开。
一端放入数据，一端拿出数据。就像单向通行。

2.3 队列功能分析

队列只需要遵守先入先出First In First Out的规则即可，具体的实现方式也不做限制。不过相比顺序表，链表更加适合队列的实现：链表的头删操作契合队列的出队列操作，链表的尾插操作契合入队列操作。
队列中有两个节点指针，一个指向队头。一个指向队尾。

2.4 链表实现队列

1. 防止头文件被重复包含

条件编译指令：

#ifndef __STACK__H__
#define __STACK__H__
//...
#endif

#pragma once

2. 头文件的包含

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

3. 队列的封装

先封装节点结构体类型，并对结构体类型struct QueueNode进行类型重命名为QNode，便于书写。

//封装为节点
typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;

在封装队列类型，包含指向队列的两个节点指针，一个指针head指向队头，一个指针tail指向队尾。把新封装的队列类型重命名为Queue，便于书写。

//封装节点指针为
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;

4. 队列的初始化

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

我们需要修改队列（结构体），所以需要传入队列的地址。开始时队列为空，队头指针pq->head和队尾指针pq->tail都指向NULL；队列的整型变量pq->size初始化为0。

5. 入队列 - 尾插数据

//入队列
void QueuePush(Queue* pq, QDataType val) {
	assert(pq);
    //申请新节点，申请失败就退出程序
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode) {
		perror("QueuePush");
		exit(-1);
	}
	newnode->val = val;
	newnode->next = NULL;
    //链表尾插分为两种情况：
    //1.队头指针为空
	if (pq->head == NULL) {
		pq->head = pq->tail = newnode;
	}
    //2.队头指针不为空
	else {
		//先链接前后节点，在更新尾节点
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	++pq->size;
}

入队列，就是链表尾插数据。先动态申请新节点，如果申请空间失败就退出程序；在尾插单链表，分两种情况：

队头指针为空，即单链表为空，队头指针需要改变；
队头指针不为空，即单链表不为空，只需要链接尾节点与新节点，再更新尾节点。

pq->size加1；

6. 出队列 - 头删数据

//出队列
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	//删除最后一个节点时，需要防止tail野指针
	if (pq->head == pq->tail) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
    //删除不是最后一个节点
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	--pq->size;
}

出队列，就是头删数据。在删除节点之前，需要先判断队列assert()是否为空，如果队列为空就报错。删除节点时有两种情况：

删除一般节点，需要节点临时指针变量del记录队头节点的地址，然后更新队头指针pq->head，再手动释放指针del指向的空间，最后pq->size减1。
删除队列最后一个节点，如果直接按第一种情况删除，那么队列尾指针pq->tail仍指向最后节点位置，pq->tail就是一个空指针，所以这种情况需要单独处理，把尾节点pq->tail也置NULL。

7. 取队头数据

//取队头数据
QDataType QueueHead(Queue* pq) {
	assert(pq);
	return pq->head->val;
}

取队尾数据

//取队尾数据
QDataType QueueTail(Queue* pq) {
	assert(pq);
	return pq->tail->val;
}

8. 判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

两个队列内部指针都为空说明队列为空。

9. 计算队列长度并返回

//计算队列长度
int QueueSize(Queue* pq) {
	assert(pq);
    //遍历法，效率较低
	/*int n = 0;
	QNode* cur = pq->head;
	while (cur) {
		++n;
		cur = cur->next;
	}
	return n;*/
    
    /*直接在队列结构体里定义一个size，每次入队列或出队列同时改变size，
    使用时直接从结构体内返回即可*/
	return pq->size;
}

两种方法：

每次调用该函数，都遍历一遍链表，效率将会降低。
直接在队列结构体里定义一个pq->size，每次入队列或出队列同时改变pq->size，

使用时直接从队列返回即可。

10. 队列的销毁

//销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	/*while (cur) {
		QNode* later = cur->next;
		free(cur);
		cur = later;
	}*/
}

在程序结束前我们需要销毁队列，防止内存泄漏的现象发生。对于链表实现的队列而言，只需要借助局部节点指针变量cur记录队列头pq->head，然后依次遍历链表的每一个节点，先借助临时节点指针变量del保存当前节点的地址，在更新cur指向下一个节点，然后释放free()指针del指向节点的空间，直到cur为NULL停止。

队列的C语言实现

分文件实现头文件Queue.h

#pragma once
//封装为节点
typedef int QDataType;
typedef struct QueueNode {
	QDataType val;
	struct QueueNode* next;
}QNode;

//封装节点指针为队列类型
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDataType val);

//出队列
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueHead(Queue* pq);

//取队尾数据
QDataType QueueTail(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//计算队列长度
int QueueSize(Queue* pq);

源文件Queue.c

#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* del = cur;
		cur = cur->next;
		free(del);
	}
	/*while (cur) {
		QNode* later = cur->next;
		free(cur);
		cur = later;
	}*/
}

//入队列
void QueuePush(Queue* pq, QDataType val) {
	assert(pq);
    //申请新节点，申请失败就退出程序
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode) {
		perror("QueuePush");
		exit(-1);
	}
	newnode->val = val;
	newnode->next = NULL;
    //链表尾插分为两种情况：
    //1.队头指针为空
	if (pq->head == NULL) {
		pq->head = pq->tail = newnode;
	}
    //2.队头指针不为空
	else {
		//先链接前后节点，在更新尾节点
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	++pq->size;
}

//出队列
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	//防止tail野指针
	if (pq->head == pq->tail) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	--pq->size;

}

//取队头数据
QDataType QueueHead(Queue* pq) {
	assert(pq);
	return pq->head->val;
}

//取队尾数据
QDataType QueueTail(Queue* pq) {
	assert(pq);
	return pq->tail->val;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

//计算队列长度
int QueueSize(Queue* pq) {
	assert(pq);
    //遍历法，效率较低
	/*int n = 0;
	QNode* cur = pq->head;
	while (cur) {
		++n;
		cur = cur->next;
	}
	return n;*/
    
    /*直接在队列结构体里定义一个size，每次入队列或出队列同时改变size，
    使用时直接从结构体内返回即可*/
	return pq->size;
}

结语

栈和队列有着许多的应用场景，它们在其中扮演了重要的作用，我们今天只是了解了它们的基本结构，并没有实际应用场景给我们练习，需要注意区分栈与队列性质的相反关系。

栈和队列的概念与实现到这里就结束了，感谢看到这里的你！！！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2022-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

数据结构初步（八）- 线性表之栈和队列的解析与实现

数据结构初步（八）- 线性表之栈和队列的解析与实现

前言

1. 栈 - Stack

1.1 概念

1.2 栈的结构

1.3 栈功能分析

1.4 顺序表实现栈

1. 防止头文件被重复包含

2. 头文件的包含

3. 栈的封装

4. 栈的初始化

5. 入栈操作(尾插数据)

6. 出栈操作(尾删数据)

7. 取出栈顶元素

8. 判断栈是否是空

9. 返回栈的大小

栈的销毁

1.4 栈的C语言实现

2. 队列 - Queue

2.1 概念

2.2 结构

2.3 队列功能分析

2.4 链表实现队列

1. 防止头文件被重复包含

2. 头文件的包含

3. 队列的封装

4. 队列的初始化

5. 入队列 - 尾插数据

6. 出队列 - 头删数据

7. 取队头数据

取队尾数据

8. 判断队列是否为空

9. 计算队列长度并返回

10. 队列的销毁

队列的C语言实现

结语

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐