【数据结构】栈和队列

前言：
栈（Stack）和队列（Queue），它们都是常用的数据结构，用于组织和存储数据。

---

一、栈

当我们谈论栈时，我们实际上在谈论一种后进先出（Last In, First Out，LIFO）的数据结构。这意味着最后插入的元素首先被移除。让我们深入了解一下栈的特性和操作：

1. 特性：

• 后进先出（LIFO）： 最后放入栈的元素是第一个被移除的。

• 操作受限： 栈有两个主要操作：推入（Push）和弹出（Pop）。推入将元素添加到栈的顶部，而弹出则将栈顶的元素移除。

• 栈顶： 只有栈顶的元素是可见的，即只能访问或修改栈顶的元素。

2. 操作：

• 推入（Push）： 将元素添加到栈的顶部。

• 弹出（Pop）： 从栈的顶部移除元素。

• 查看栈顶（Peek）： 查看栈顶的元素，但不移除它。

• 判空和判满： 可以检查栈是否为空（Empty）或已满（Full），虽然栈的大小通常是动态调整的，因此满的情况相对较少。

---

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。这里我们使用动态的数组来实现栈。

Stack 结构体：

typedef int STDataType;

typedef struct Stack {
	STDataType* a; 
	int top;     //标识栈顶
	int capacity; //容量

}ST;

操作栈的函数：

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

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

//栈顶推入
void StackPush(ST* pst, STDataType x);

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

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

//检测栈是否为空
bool StackEmpty(ST* pst);

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

完整的栈的代码在最后

---

二、队列

队列（Queue）是一种基本的数据结构，它遵循先进先出（First In, First Out，FIFO）的原则。这意味着最先进入队列的元素将最先被移出，就像排队一样。队列常被用于需要按顺序处理的场景，比如任务调度、广度优先搜索、打印任务等。

以下是队列的一些关键特性和基本操作：

1. 特性：

• 先进先出（FIFO）： 队列中最早进入的元素首先被移除。

• 操作受限： 队列主要支持两个操作：入队（Enqueue）和出队（Dequeue）。

• 队头和队尾： 队列的前端称为队头（Front），用于出队操作；队列的后端称为队尾（Rear），用于入队操作。

2. 操作：

• 入队（Enqueue）： 向队尾添加元素。

• 出队（Dequeue）： 从队头移除元素。

• 查看队头元素（Front）： 查看队头的元素，但不移除它。

• 检查队列是否为空： 判断队列中是否有元素。

• 检查队列是否已满（对于有限队列）： 在使用有限大小的队列时，可以检查队列是否已满。

在实际编程中，队列可以使用数组、链表或其他数据结构来实现。例如，使用数组时需要考虑队列的大小和溢出的问题，而使用链表时可以更方便地处理动态大小的队列。

---

队列的实现

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

Queue结构体

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

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

//队列元素个数
int QueueSize(Queue* pq);

---

附录

栈实现的完整代码

“Stack.h”

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

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;     //标识栈顶
	int capacity; //容量

}ST;

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

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

//栈顶推入
void StackPush(ST* pst, STDataType x);

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

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

//检测栈是否为空
bool StackEmpty(ST* pst);

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

“Stack.c”

#include"Stack.h"

void StackInit(ST* pst) {
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//指向栈顶下一个元素
}

void StackDestroy(ST* pst) {
	assert(pst);

	free(pst->a);
}

void StackPush(ST* pst, STDataType x) {
	assert(pst);

	if (pst->top == pst->capacity) {
		int newcapacity = pst->capacity = 0 ? 4 : 2 * pst->capacity;
		STDataType* temp = realloc(pst->a,sizeof(STDataType)*newcapacity);
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}

		pst->a = temp;
		pst->capacity = newcapacity;
	}

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

void StackPop(ST* pst) {
	assert(pst);
	//不为空
	assert(pst->top > 0);

	pst->top--;
}

STDataType StackTop(ST* pst) {
	assert(pst);
	//不为空
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

bool StackEmpty(ST* pst) {
	assert(pst);

	return pst->top == 0;
}

int StackSize(ST* pst) {
	assert(pst);

	return pst->top;
}

“test.c”

#include"Stack.h"

int main() {
	ST s;
	StackInit(&s);
	StackPush(&s,1);
	StackPush(&s,2);
	StackPush(&s,3);
	printf("%d ", StackTop(&s));
	StackPush(&s, 4);
	printf("%d ", StackTop(&s));

	while (!StackEmpty(&s)) {
		printf("%d ", StackTop(&s));
		StackPop(&s);
	}
	
	return 0;
}

---

队列实现的完整代码

“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);

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

//队列元素个数
int QueueSize(Queue* pq);

“Queue.c”

#include "Queue.h"

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

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

	QNode* cur = pq->phead;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = 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->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL) {
		pq->ptail = pq->phead = newnode;
	}
	else {
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

void QueuePop(Queue* pq) {
	assert(pq->phead);
	assert(pq);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = 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;
}

bool QueueEmpty(Queue* pq) {
	assert(pq);

	return pq->phead == NULL;
}

int QueueSize(Queue* pq) {
	assert(pq);

	return pq->size;
}

“test.c”

#include"Queue.h"

int main() {
	Queue q;
	QueueInit(&q);
	QueuePush(&q,1);
	QueuePush(&q,2);
	QueuePush(&q,3);
	QueuePush(&q,4);
	QueuePush(&q,5);
	while (!QueueEmpty(&q)) {
		printf("%d",QueueFront(&q));
		QueuePop(&q);
	}
}

---

如果你喜欢这篇文章，点赞👍+评论+关注??哦！
欢迎大家提出疑问，以及不同的见解。