前言：
栈（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);}
}

---

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