【C语言】数据结构——栈和队列实例探究

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读：
一、栈
- 1. 栈的概念及结构
- 2. 栈的实现
- 3. 实现代码
- - 3.1 定义结构体
  - 3.2 初始化栈
  - 3.3 销毁栈
  - 3.4 入栈
  - 3.5 出栈
  - 3.6 获取栈顶元素
  - 3.7 检测栈是否为空
  - 3.8 获取栈中有效元素个数
- 4. 代码整理
- - 4.1 **Stack.h**
  - 4.2 Stack.c
  - 4.3 study.c
二、队列
- 1. 队列的概念及结构
- 2. 队列的实现
- 3. 实现代码
- - 3.1 定义结构体
  - 3.2 初始化队列
  - 3.3 销毁队列
  - 3.4 队尾入队列
  - 3.5 队头出队列
  - 3. 6 获取队列头部元素
  - 3.7 获取队列队尾元素
  - 3.8 检测队列是否为空
  - 3.9 获取队列中有效元素个数
- 4. 代码整理
- - 4.1 **Queue.h**
  - 4.2 Queue.c
  - 4.3 study.c

导读：

我们在前面学习了单链表和顺序表，今天我们来学习栈和队列。
栈和队列相对于单链表和顺序表来说是较为简单的，之后我们再深入学习双链表。关注博主或是订阅专栏，掌握第一消息。

一、栈

1. 栈的概念及结构

栈(Stack)是一种只能在一端进行插入和删除操作的线性数据结构，该端被称为栈顶(Top)，另一端被称为栈底(Bottom)。
栈的特点是后进先出(Last In First Out, LIFO)，即最后放入栈中的元素最先被弹出。栈中的元素可以是任意类型，但栈顶永远只能是一个元素。

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

2. 栈的实现

栈可以用数组或链表来实现，常见应用场景包括函数调用、表达式求值、括号匹配、逆序输出等。

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

其基本操作包括：

push(x): 将元素x压入栈顶。
pop(): 弹出栈顶元素并返回其值。
top(): 返回栈顶元素的值，但不弹出。
empty():判断栈是否为空。

3. 实现代码

我们需要创建两个 C文件: study.c 和 Stack.c，以及一个头文件： Stack.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

3.1 定义结构体

typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。

若struct Stack {}这样来定义结构体的话。在申请Stack 的变量时，需要这样写，struct Stack n;
若用typedef，可以这样写，typedef struct Stack{}ST; 。在申请变量时就可以这样写，ST n;
区别就在于使用时，是否可以省去struct这个关键字。

Stack.h

typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

3.2 初始化栈

Stack.h 声明函数

// 初始化栈 
void STInit(ST* pst);

Stack.c 定义函数

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

3.3 销毁栈

动态内存空间开辟，使用完之后需要进行销毁。
Stack.h 声明函数

// 销毁
void STDestroy(ST* pst);

Stack.c 定义函数

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

3.4 入栈

我们在顺序表和单向链表里，都另定义一个函数来进行空间的开辟，这样我们在其它的函数中有开辟空间的需要只用调用即可，而无需再去写一次开辟空间的代码。但是在栈中我们只有在入栈的函数中需要进行空间的开辟，所有不用再单独写一个函数。
Stack.h 声明函数

// 入栈 
void STPush(ST* pst, STDataType x);

Stack.c 定义函数


void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

3.5 出栈

后进先出原则，最后进来的数据先出。
Stack.h 声明函数

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

Stack.c 定义函数

// 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，不让访问即可
	pst->top--;
}

3.6 获取栈顶元素

栈并不能像打印数组那样把数据全部打印出来，只能获取到栈顶的元素，想要获取其它数据就只能先把其它的数据给删除，也就是出栈。
Stack.h 声明函数

// 获取栈顶元素 
STDataType STTop(ST* pst);

Stack.c 定义函数

// 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

3.7 检测栈是否为空

Stack.h 声明函数

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

Stack.c 定义函数

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

3.8 获取栈中有效元素个数

Stack.h 声明函数

// 获取栈中有效元素个数 
int STSize(ST* pst);

Stack.c 定义函数

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

4. 代码整理

4.1 Stack.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;		//标识栈顶的位置
	int capacity;
}ST;

// 初始化栈 
void STInit(ST* pst);

// 销毁
void STDestroy(ST* pst);

// 入栈 
void STPush(ST* pst, STDataType x);

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

// 获取栈顶元素 
STDataType STTop(ST* pst);

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst);

// 获取栈中有效元素个数 
int STSize(ST* pst);

4.2 Stack.c

#include "Stack.h"

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

// 销毁栈
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
}

// 入栈 
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	// 检查空间，如果满了，进行增容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		//如果开辟成功则重新赋给原来的数组指针
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//栈顶从0开始，可以作为数组的下标来进行插入数据
	pst->a[pst->top] = x;
	pst->top++;
}

// 出栈 
void STPop(ST* pst)
{
	assert(pst);
	//top大于0，栈里面有数据才能删除数据
	assert(pst->top > 0);
	//直接让top--，有效数据减一即可
	pst->top--;
}

// 获取栈顶元素 
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	//top-1即是栈顶元素
	return pst->a[pst->top - 1];
}

// 检测栈是否为空，如果为空返回true，如果不为空返回false 
bool STEmpty(ST* pst)
{
	assert(pst);
	//如果表达式成立则为真
	return pst->top == 0;
}

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

4.3 study.c

#include "Stack.h"

void TestST1()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	printf("%d\n", STTop(&s));

	//一     对   多
	//入栈顺序 -- 出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	STDestroy(&s);
}
int main()
{
	TestST1();
	return 0;
}

二、队列

1. 队列的概念及结构

队列是一种线性的数据结构，它可以存储一系列数据，其中第一个添加的数据会被第一个删除，也就是先进先出（FIFO）的原则。

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

2. 队列的实现

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

队列通常有两个指针，一个是front指针，指向队列的第一个元素，另一个是rear指针，指向队列的最后一个元素。当一个新元素进入队列时，它被插入到rear指针所指向的位置，当一个元素从队列中删除时，它会从front指针所指向的位置被删除。

3. 实现代码

我们需要创建两个 C文件: study.c 和 Queue.c，以及一个头文件： Queue.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

3.1 定义结构体

定义了一个链式队列的数据结构。
包含了两个结构体：

QNode结构体表示队列中的一个节点，包含一个整数数据成员val和指向下一个节点的指针next。
Queue结构体表示一个队列，包含指向队头和队尾节点的指针phead和ptail，以及队列的大小size。

这个队列是通过链式结构实现的，即每个节点都包含一个指向下一个节点的指针。队列的头指针phead指向队列的第一个节点，而队列的尾指针ptail指向队列的最后一个节点。
链式队列的优点是可以动态地增加和减少队列的大小，而不需要像顺序队列那样预留一定的空间。缺点是每个节点都需要额外的指针空间来指向下一个节点，因此相对于顺序队列会占用更多的存储空间。

Queue.h

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

3.2 初始化队列

Queue.h

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

Queue.c

void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

3.3 销毁队列

Queue.h

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

Queue.c

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

3.4 队尾入队列

Queue.h

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

Queue.c

void QueuePush(Queue* pq, QDataType x)
{
	//开辟新空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

3.5 队头出队列

Queue.h

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

Queue.c

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

3. 6 获取队列头部元素

Queue.h

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

Queue.c

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

3.7 获取队列队尾元素

Queue.h

// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

Queue.c

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

3.8 检测队列是否为空

Queue.h

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

Queue.c

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

3.9 获取队列中有效元素个数

Queue.h

// 获取队列中有效元素个数 
int QueueSize(Queue* pq);

Queue.c

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

4. 代码整理

4.1 Queue.h

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

// 链式结构：表示队列 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

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

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

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

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

// 获取队列队尾元素
QDataType QueueBack(Queue* pq);

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq);

// 获取队列中有效元素个数 
int QueueSize(Queue* pq);

4.2 Queue.c

#include "Queue.h"

// 初始化队列 
void QueueInit(Queue* pq)
{
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead->next;
	while (cur)
	{
		free(pq->phead);
		pq->phead = cur;
		cur = cur->next;
	}
	cur = NULL;
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

// 队尾入队列 
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* tmp = pq->phead;
	pq->phead = pq->phead->next;
	free(tmp);
	tmp = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}
	pq->size--;
}

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

// 检测队列是否为空，如果为空返回true，如果非空返回false 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

4.3 study.c

#include "Queue.h"

void TestQ1()
{
	Queue s;
	QueueInit(&s);
	QueuePush(&s, 1);
	QueuePush(&s, 2);
	QueuePush(&s, 3);
	QueuePush(&s, 4);
	QueuePush(&s, 5);
	printf("%d ", QueueFront(&s));
	printf("%d ", QueueBack(&s));
	printf("%d\n", QueueSize(&s));
	QueuePop(&s);
	QueuePop(&s);
	printf("%d ", QueueFront(&s));
	printf("%d\n", QueueSize(&s));
	if (!QueueEmpty(&s))
	{
		QueuePop(&s);
		printf("%d ", QueueFront(&s));
		printf("%d\n", QueueSize(&s));
	}
	QueueDestroy(&s);
	printf("%d\n", QueueSize(&s));

}
int main()
{
	TestQ1();
	return 0;
}

文章出处登录后可见！

已经登录？立即刷新

【C语言】数据结构——栈和队列实例探究

目录

导读：

一、 栈

1. 栈的概念及结构

2. 栈的实现

3. 实现代码

3.1 定义结构体

3.2 初始化栈

3.3 销毁栈

3.4 入栈

3.5 出栈

3.6 获取栈顶元素

3.7 检测栈是否为空

3.8 获取栈中有效元素个数

4. 代码整理

4.1 Stack.h

4.2 Stack.c

4.3 study.c

二、队列

1. 队列的概念及结构

2. 队列的实现

3. 实现代码

3.1 定义结构体

3.2 初始化队列

3.3 销毁队列

3.4 队尾入队列

3.5 队头出队列

3. 6 获取队列头部元素

3.7 获取队列队尾元素

3.8 检测队列是否为空

3.9 获取队列中有效元素个数

4. 代码整理

4.1 Queue.h

4.2 Queue.c

4.3 study.c

相关推荐

一、栈