线性链表之栈、队列的代码实现

目录

一 、栈

1.栈的概念

2.栈的主要操作：

size(): 返回栈中元素的数量。

3.栈的应用场景：

4.栈的代码实现

4.1 初始化栈

4.2 入栈

 4.3 出栈

4.4 判空

4.5 取栈顶元素

3.6 获取栈中有效元素个数

 3.7 销毁栈

 5.总体代码

二、队列

1.队列的概念：

2.队列的主要操作：

3.队列的应用场景：

 ​编辑4.队列的代码实现

4.1 初始化队列

4.2  入队

 4.3 出队

 4.4 获取对列的元素个数

4.5 判空

4.6获取队列头部元素

 4.7获取队列队尾元素

4.8 队列销毁

5.总体代码

三、结尾

---

一 、栈

1.栈的概念

栈：栈是一种后进先出（LIFO, Last In First Out）的数据结构。它只允许在栈顶进行添加（push）或删除（pop）元素的操作。这意味着最后添加到栈中的元素将是第一个被移除的。

2.栈的主要操作：

• push(element): 将元素压入栈顶。
• pop(): 移除并返回栈顶元素。
• peek() 或 top(): 返回栈顶元素，但不移除它。
• isEmpty(): 检查栈是否为空。

• size(): 返回栈中元素的数量。

3.栈的应用场景：

• 表达式求值（如后缀表达式求值）。
• 递归调用（函数调用栈）。
• 浏览器历史记录（最近访问的页面放在最上面）。
• 回溯算法（如深度优先搜索DFS）。

4.栈的代码实现

在这我就用通过顺序表的形式来实现栈 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
//动态栈
typedef int STDataType;
 
typedef struct Stack
{
	int* a;
	int top;
	int capacity;
}ST;
 
//栈的初始化
void STInit(ST* pc);
 
//栈的销毁
void STDestory(ST* pc);
 
//压栈
void STPush(ST* pc, STDataType x);
 
//出栈
void STPop(ST* pc);
 
//返回栈内的空间大小
int STSize(ST* pc);
 
//判断栈内是否为空
bool STEmpty(ST* pc);
 
//返回栈顶的元素
STDataType STTop(ST* pc);

4.1 初始化栈

栈的初始化将传入函数的结构体进行初始化：

a. 栈顶初始化的时候注意有两种情况:
1. top指向栈顶元素
2. top指向栈顶元素的后面一个位置
当然都可以，我选择 2 仅仅方便我自己理解

b.对栈申请容量为4个STDataType的字节大小

void STInit(ST* pc)
{
	assert(pc);
	pc->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (pc->a == NULL)
	{
		perror("malloc");
		return;
	}
 
	pc->capacity = 4;
	pc->top = 0;//从栈底的下一个元素开始
}

4.2 入栈

当数据入栈时需要判断栈是否为满，若为满则需要扩容

void STPush(ST* pc, STDataType x)
{
	assert(pc);
 
	if (pc->top == pc->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pc->a, sizeof(STDataType) * (pc->capacity) * 2);
		if (tmp == 0)
		{
			perror("realloc");
			return;
		}
		
		pc->a = tmp;
		pc->capacity *= 2;
 
	}
		pc->a[pc->top] = x;
		++pc->top;
}

 4.3 出栈

执行出栈操作时，栈不能为空，且只需要 top-- ， 不需要将其数据抹除。

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

4.4 判空

 此次的bool类型接收若为真，则返回Ture，若为假，则返回Flase，通过返回pc->top是否等与零，也就是栈是否为空来判断返回。

bool STEmpty(ST* pc)
{
	assert(pc);
 
 
	return pc->top == 0;
}

4.5 取栈顶元素

先通过STEmpty判断栈内是否为空

top是指栈顶元素的最后一个位置，所以需要减一（top-1）来指定栈顶数据

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

3.6 获取栈中有效元素个数

 由于op是指栈顶元素的最后一个位置，而元素个数从下标零开始，所以直接放回top

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

 3.7 销毁栈

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

 5.总体代码

#define _CRT_SECURE_NO_WARNINGS 1
 
#include"Stack.h"
 
void STInit(ST* pc)
{
	assert(pc);
	pc->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (pc->a == NULL)
	{
		perror("malloc");
		return;
	}
 
	pc->capacity = 4;
	pc->top = 0;//从栈底的下一个元素开始
}
 
void STDestory(ST* pc)
{
	assert(pc);
	free(pc->a);
	pc->a = NULL;
	pc->capacity = 0;
	pc->top = 0;
}
 
void STPush(ST* pc, STDataType x)
{
	assert(pc);
 
	if (pc->top == pc->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(pc->a, sizeof(STDataType) * (pc->capacity) * 2);
		if (tmp == 0)
		{
			perror("realloc");
			return;
		}
		
		pc->a = tmp;
		pc->capacity *= 2;
 
	}
		pc->a[pc->top] = x;
		++pc->top;
}
 
void STPop(ST* pc)
{
	assert(pc);
	assert(!STEmpty(pc));
	pc->top--;
}
 
int STSize(ST* pc)
{
	assert(pc);
 
	return pc->top;
}
 
bool STEmpty(ST* pc)
{
	assert(pc);
	return pc->top == 0;
}
 
STDataType STTop(ST* pc)
{
	assert(pc);
	assert(!STEmpty(pc));
 
	return pc->a[pc->top - 1];
}

二、队列

1.队列的概念：

队列是一种先进先出（FIFO, First In First Out）的数据结构。它允许在队尾添加元素（入队），在队首移除元素（出队）。这意味着最先添加到队列中的元素将是第一个被移除的

2.队列的主要操作：

• enqueue(element): 在队尾添加一个元素。
• dequeue(): 移除并返回队首元素。
• front(): 返回队首元素，但不移除它。
• rear(): 返回队尾元素（在某些实现中可能不提供）。
• isEmpty(): 检查队列是否为空。
• size(): 返回队列中元素的数量。

3.队列的应用场景：

• 缓冲区（如网络数据包）。
• 任务调度（如操作系统的进程调度）。
• 广度优先搜索（BFS）。
• 打印机任务队列。

 4.队列的代码实现

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
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* pc);
 
//队列的销毁
void QueueDestory(Queue* pc);
 
//入队
void QueuePush(Queue* pc,QDataType x);
 
//出队
void QueuePop(Queue* pc);
 
//队列的元素个数
void  QueueSize(Queue* pc);
 
//判空
bool QueueEmpty(Queue* pc);
 
//获取队列队头元素 
QDataType QueueFront(Queue* pc);
 
//获取队列队尾元素 
QDataType QueueBack(Queue* pc);

4.1 初始化队列

为了方便找到头和尾和元素个数所以定义了一个结构体：

这里队列的front指向队头，rear指向队尾，size表示元素个数。
当队列为空的时候，那么front和rear 都是指向 NULL

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

4.2  入队

插入时，需要向空间申请空间

1.队列为空时，需要改变队头和队尾的指针

2.不为空时，只需要将新结点指向队尾并把队尾指向新结点（注意顺序）

void QueuePush(Queue* pc, QDataType x)
{
	QNode* newnode = (Queue*)malloc(sizeof(Queue));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = x;
	newnode->next = NULL;
	if (pc->head == NULL)
	{
		pc->head = pc->tail = newnode;
	}
	else
	{
		pc->tail->next = newnode;
		pc->tail = newnode;
	}
	pc->size++;
}

 4.3 出队

1.对列只有一个结点时：删除该结点，并把head和tail指向NULL

2.队列有多个结点时：保存head->next，删除head的结点并更新head

void QueuePop(Queue* pc)
{
	assert(pc);
	assert(pc->head != NULL);
 
	if (pc->head->next == NULL)
	{
		free(pc->head);
		pc->head = pc->tail = NULL;
	}
	else
	{
		Queue* next = pc->head->next;
		free(pc->head);
		pc->head = next;
	}
	pc->size--;
}

 4.4 获取对列的元素个数

size表示队列存储的元素个数

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

4.5 判空

通过size存储的元素个数来进行判断

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

4.6获取队列头部元素

head存储着队列的头部元素

QDataType QueueFront(Queue* pc)
{
	assert(pc);
	assert(!QueueEmpty(pc));
 
	return pc->head->data;
}

 4.7获取队列队尾元素

tail存储着队列的队尾元素

QDataType QueueBack(Queue* pc)
{
	assert(pc);
	assert(!QueueEmpty(pc));
 
	return pc->tail->data;
}

4.8 队列销毁

void QueueDestory(Queue* pc)
{
	assert(pc);
	Queue* cur = pc->head;
 
	while (cur)
	{
		Queue* next = cur->next;
		free(cur);
		cur = next;
	}
	pc->head = pc->tail = NULL;
	pc->size = 0;
}

5.总体代码

#define _CRT_SECURE_NO_WARNINGS 1
 
#include"Queue.h"
 
void QueueInit(Queue* pc)
{
	assert(pc);
	pc->head = pc->tail = NULL;
 
	pc->size = 0;
}
 
void QueueDestory(Queue* pc)
{
	assert(pc);
	Queue* cur = pc->head;
 
	while (cur)
	{
		Queue* next = cur->next;
		free(cur);
		cur = next;
	}
	pc->head = pc->tail = NULL;
	pc->size = 0;
}
 
void QueuePush(Queue* pc, QDataType x)
{
	QNode* newnode = (Queue*)malloc(sizeof(Queue));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->next = x;
	newnode->next = NULL;
	if (pc->head == NULL)
	{
		pc->head = pc->tail = newnode;
	}
	else
	{
		pc->tail->next = newnode;
		pc->tail = newnode;
	}
	pc->size++;
}
 
void QueuePop(Queue* pc)
{
	assert(pc);
	assert(pc->head != NULL);
 
	if (pc->head->next == NULL)
	{
		free(pc->head);
		pc->head = pc->tail = NULL;
	}
	else
	{
		Queue* next = pc->head->next;
		free(pc->head);
		pc->head = next;
	}
	pc->size--;
}
 
void  QueueSize(Queue* pc)
{
	assert(pc);
 
	return pc->size;
}
 
bool QueueEmpty(Queue* pc)
{
	assert(pc);
 
	return pc->size == 0;
}
 
QDataType QueueFront(Queue* pc)
{
	assert(pc);
	assert(!QueueEmpty(pc));
 
	return pc->head->data;
}
 
 
QDataType QueueBack(Queue* pc)
{
	assert(pc);
	assert(!QueueEmpty(pc));
 
	return pc->tail->data;
}

三、结尾

如果有什么建议和疑问，或是有什么错误，希望大家可以在评论区提一下。
希望大家以后也能和我一起进步！！
如果这篇文章对你有用的话，希望能给我一个小小的赞！