数据结构之栈和队列

栈（Stack）和队列（Queue）是两种常见的数据结构，广泛应用于计算机科学中。它们的主要区别在于数据的存取方式。

栈（Stack）

定义： 栈是一种遵循''后进先出（LIFO, Last In First Out）"原则的线性数据结构。其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

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

操作：

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

Pop（出栈）：移除并返回栈顶的元素。

Peek/Top（查看栈顶元素）：返回栈顶元素但不移除它。

isEmpty（判断栈是否为空）：检查栈是否为空。

Size（获取栈的大小）：返回栈中元素的数量。

---

栈的实现 栈的实现一般可以使用 数组或者链表 实现，相对而言 数组 的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

Stack.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> // 下面是定长的静态栈的结构，实际中一般不实用 typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack; 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); // 判空 bool STEmpty(ST* pst); // 获取数据个数 int STSize(ST* pst);

Stack.c 

#include"Stack.h" // 初始化和销毁 void STInit(ST* pst) { assert(pst); pst->a = NULL; // top指向栈顶数据的下一个位置 pst->top = 0; // top指向栈顶数据 //pst->top = -1; pst->capacity = 0; } void STDestroy(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 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, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top > 0); pst->top--; } // 取栈顶数据 STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; } // 判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; } // 获取数据个数 int STSize(ST* pst) { assert(pst); return pst->top; }

---

队列（Queue）

定义： 队列是一种遵循 "先进先出（FIFO, First In First Out )"原则的线性数据结构。最先进入队列的元素最先被取出。

操作：

Enqueue（入队）：将元素添加到队列的尾部。

Dequeue（出队）：移除并返回队列头部的元素。

Front（查看队头元素）：返回队头元素。

Rear（查看队尾元素）：返回队尾元素。

isEmpty（判断队列是否为空）：检查队列是否为空。

Size（获取队列的大小）：返回队列中元素的数量。

---

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

Queue.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType val; }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); int QueueSize(Queue* pq); bool QueueEmpty(Queue* pq); 队尾插入 //void QueuePush(QNode** pphead, QNode** pptail, QDataType x); 队头删除 //void QueuePop(QNode** pphead, QNode** pptail);

Queue.c 

#include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; 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->next = NULL; newnode->val = x; 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->size != 0); /*QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; if (pq->phead == NULL) pq->ptail = NULL;*/ // 一个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else // 多个节点 { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } 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; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } 栈与队列的区别 特性栈（Stack）队列（Queue）存取原则后进先出（LIFO）先进先出（FIFO）主要操作Push, PopEnqueue, Dequeue应用场景函数调用、撤销操作、DFS任务调度、BFS、消息队列 总结

栈适用于需要后进先出的场景，如函数调用和撤销操作。

队列适用于需要先进先出的场景，如任务调度和广度优先搜索。

---

栈和队列例题

1.20. 有效的括号 - 力扣（LeetCode）

//C++ class Solution { public: bool isValid(string s) { stack<char> st; auto it = s.begin(); while(it != s.end()) { if(*it == '(' || *it == '{' || *it == '[') { st.push(*it); } else { if(st.empty()) { return false; } else { char top = st.top(); st.pop(); if((top=='('&&*s!=')') ||(top=='['&&*s!=']') ||(top=='{'&&*s!='}')) { return false; } } } it++; } bool ret = st.empty(); return ret; } };

//C typedef char STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps); //初始化栈 void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = ps->_top = 0; } //入栈 void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->_top == ps->_capacity) { int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity*sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->_capacity = newcapacity; ps->_a = tmp; } ps->_a[ps->_top++] = data; } //出栈 void StackPop(Stack* ps) { assert(ps); assert(ps->_top > 0); ps->_top--; } //获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(ps->_top > 0); return ps->_a[ps->_top-1]; } //获取栈中 //有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->_top; } //检测栈是否为空 bool StackEmpty(Stack* ps) { assert(ps); return ps->_top == 0; } //销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; ps->_capacity = ps->_top = 0; } bool isValid(char* s) { Stack st; StackInit(&st); while(*s) { if(*s=='('||*s=='{'||*s=='[') { //左括号入栈 StackPush(&st,*s); } else { //左括号不存在 肯定不能匹配 if(StackEmpty(&st)) { return false; } //左括号和右括号匹配 char top=StackTop(&st); StackPop(&st); if((top=='('&&*s!=')') ||(top=='['&&*s!=']') ||(top=='{'&&*s!='}')) { StackDestroy(&st); return false; } } ++s; } //为空说明左括号和右括号匹配完全 返回true 不为空说明还有左括号不能与右括号进行匹配 返回false bool ret =StackEmpty(&st); StackDestroy(&st); return ret; }

2.225. 用队列实现栈 - 力扣（LeetCode） 

3.232. 用栈实现队列 - 力扣（LeetCode）

C语言：栈实现队列 队列实现栈-CSDN博客

4.622. 设计循环队列 - 力扣（LeetCode）

typedef struct { int* a; int head; int tail; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //多开一个空间 解决空和满冲突的问题 obj->a=(int*)malloc(sizeof(int)*(k+1)); obj->head=obj->tail=0; obj->k=k; return obj; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->head==obj->tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail + 1) % (obj->k + 1) == obj -> head; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->a[obj->tail]=value; obj->tail++; obj->tail %=(obj->k + 1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->head++; obj->head %=(obj->k + 1); return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->a[obj->head] ; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->tail == 0 ? obj->a[obj->k] : obj->a[obj->tail-1]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */

---