【初阶数据结构】5.栈和队列

---

1.栈

1.1 概念与结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈底层结构选型

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

---

1.2 栈的实现

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义栈的结构
typedef int STDataType;
typedef struct Stack {STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}ST;//栈的初始化
void STInit(ST* ps);//栈的销毁
void STDestory(ST* ps);//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x);
//出数据
void StackPop(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"//栈的初始化
void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈的销毁
void STDestory(ST* ps) {assert(ps);if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("relloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//出数据
void StackPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空报错--ps->top;
}//判断栈是否为空
bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0;
}//获取栈中有效元素个数
int STSize(ST* ps){assert(ps);return ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"void STTest() {ST st;STInit(&st);//StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);printf("size: %d\n", STSize(&st));//循环出栈，直到栈为空while (!StackEmpty(&st)) {STDataType data = StackTop(&st);printf("%d ", data);//出栈StackPop(&st);}printf("size: %d\n", STSize(&st));////STDestory(&st);
}int main() {STTest();return 0;
}

---

2.队列

2.1 概念与结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列底层结构选型

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

---

2.2 队列的实现

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义队列结构
typedef int QDataType;typedef struct QueueNode {QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue {QueueNode* phead;//队头：删QueueNode* ptail;//队尾：插int size;//保存队列有效数据个数
}Queue;//初始化队列
void QueueInit(Queue* pq);// 入队列，队尾
void QueuePush(Queue* pq, QDataType x);// 出队列，队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化队列
void QueueInit(Queue* pq) {assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 入队列，队尾
void QueuePush(Queue* pq, QDataType x) {assert(pq);//申请新结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) {//判断队列是否为空pq->phead = pq->ptail = newnode;}else {//队列不为空pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;//入一次，size++ 一次
}//队列判空
bool QueueEmpty(Queue* pq) {assert(pq);return (pq->phead == NULL) && (pq->ptail == NULL);
}// 出队列，队头
void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//只有一个结点的情况，避免ptail变成野指针if (pq->ptail == pq->phead) {free(pq->phead);pq->phead = pq->ptail = NULL;}else {//删除队头元素QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;//出一次，size-- 一次
}//取队头数据
QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断队列不为空return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断队列不为空return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq) {assert(pq);/*int size = 0;QueueNode* pcur = pq->phead;while (pcur) {size++;pcur = pcur->next;//复杂度O(n)}*/return pq->size;//复杂度O(1)
}//销毁队列
void QueueDestroy(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁QueueNode* pcur = pq->phead;while (pcur) {QueueNode* Next = pcur->next;free(pcur);pcur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"void QueueTest01() {Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//QueuePop(&q);printf("head:%d\n", QueueFront(&q));printf("tail:%d\n", QueueBack(&q));printf("size:%d\n", QueueSize(&q));QueueDestroy(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);QueuePop(&q);
}int main() {QueueTest01();return 0;
}

---

3.栈和队列算法题

3.1 有效的括号

点击链接答题

思路：

定义一个指针ps遍历字符串

若ps遍历到的字符为左括号，入栈

若ps遍历到的字符为右括号，取栈顶元素与ps进行比较，

1. 栈顶元素 匹配 *ps，出栈，ps++
2. 栈顶元素 不匹配 *ps，返回false

代码：

//定义栈的结构
typedef char STDataType;
typedef struct Stack {STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}ST;//栈的初始化
void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈的销毁
void STDestory(ST* ps) {assert(ps);if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("relloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0;
}//出数据
void StackPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空报错--ps->top;
}//获取栈中有效元素个数
int STSize(ST* ps){assert(ps);return ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}bool isValid(char* s) {ST st;//初始化STInit(&st);//遍历字符串schar* ps = s;while(*ps != '\0'){//左括号，入栈if(*ps == '(' || *ps == '[' || *ps == '{'){StackPush(&st, *ps);}else{//右括号，和栈顶元素比较是否匹配//栈为空，直接返回falseif(StackEmpty(&st)){return false;}//栈不为空才能取栈顶元素char ch = StackTop(&st);if((*ps == ')' && ch == '(')|| (*ps == ']' && ch == '[')|| (*ps == '}' && ch == '{') ){StackPop(&st);} else{//不匹配STDestory(&st);return false;}}ps++;}bool ret = StackEmpty(&st) == true;//如果为空，返回true//销毁STDestory(&st);return ret;
}

---

3.2 用队列实现栈

点击链接答题

思路：

出栈：找不为空的队列，将size-1个数据导入到另一个队列中。

入栈：往不为空队列里面插入数据

取栈顶元素：

例如：

两个队列：

1. Q1：1 2 3
2. Q2：NULL

---

如果是栈的话：

1. 插入1 2 3
2. 出栈一次
3. 插入4
4. 全部出栈

得到：3 4 2 1

---

将Q1里面的1 2出栈到Q2，把3取出来，此时Q1为NULL

取出了3

往Q2里面插入4，此时Q2为1 2 4

将Q2里面的1 2出栈到Q1，此时Q2为4，把4取出来，此时Q2为NULL

取出了3 4

将Q1里面的1出栈到Q2，把2取出来 ，此时Q1为NULL

取出了3 4 2

将Q2里面的1取出来

取出了3 4 2 1

代码：

//定义队列结构
typedef int QDataType;typedef struct QueueNode {QDataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue {QueueNode* phead;//队头：删QueueNode* ptail;//队尾：插int size;//保存队列有效数据个数
}Queue;//初始化队列
void QueueInit(Queue* pq) {assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 入队列，队尾
void QueuePush(Queue* pq, QDataType x) {assert(pq);//申请新结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) {//判断队列是否为空pq->phead = pq->ptail = newnode;}else {//队列不为空pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;//入一次，size++ 一次
}//队列判空
bool QueueEmpty(Queue* pq) {assert(pq);return (pq->phead == NULL) && (pq->ptail == NULL);
}// 出队列，队头
void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//只有一个结点的情况，避免ptail变成野指针if (pq->ptail == pq->phead) {free(pq->phead);pq->phead = pq->ptail = NULL;}else {//删除队头元素QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}--pq->size;//出一次，size-- 一次
}//取队头数据
QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断队列不为空return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));//判断队列不为空return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq) {assert(pq);return pq->size;//复杂度O(1)
}//销毁队列
void QueueDestroy(Queue* pq) {assert(pq);//这里允许pq为空// assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁QueueNode* pcur = pq->phead;while (pcur) {QueueNode* Next = pcur->next;free(pcur);pcur = Next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//两个队列来实现栈
typedef struct {Queue q1;//队列1Queue q2;//队列2
} MyStack;//STInit
MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}//Push入栈
void myStackPush(MyStack* obj, int x) {//往不为空的队列中插入数据if(!QueueEmpty(&obj->q1)){//如果q1不为空，执行这个QueuePush(&obj->q1,x);//往队列q1里面插入x}else{//如果q2不为空，执行这个QueuePush(&obj->q2,x);//往队列q2里面插入x}
}//Pop出栈
int myStackPop(MyStack* obj) {//找不为空的队列Queue* empQ = &obj->q1;//定义q1为空Queue* noneQ = &obj->q2;//定义q2为非空if(!QueueEmpty(&obj->q1)){//如果q1不为空，执行这个noneQ = &obj->q1;//q1是非空队列empQ = &obj->q2;//q2是空队列}//将不为空队列中size-1个数据导入到空队列中while(QueueSize(noneQ) > 1){//循环结束的判断，是只剩下一个数据int front = QueueFront(noneQ);//取队头数据QueuePush(empQ,front);//往空队列q2里面插入队头元素QueuePop(noneQ);//把非空队列q1里面的队头元素拿出来，这样下次循环出来的队头元素就不会重复了}//非空队列中只剩下一个数据------要出栈的数据int pop = QueueFront(noneQ);//把要取出的数据存起来QueuePop(noneQ);//将数据出队列，让q1变成空队列return pop;//返回要取出的数据
}//取栈顶元素：找不为空的队列，取队尾元素
//不出栈
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){//q1不为空return QueueBack(&obj->q1);//取队尾数据}else{//q2不为空return QueueBack(&obj->q2);//取队尾数据}
}//判断栈是否为空
//也就是判断两个队列是否为空
bool myStackEmpty(MyStack* obj) {//栈是空的，返回 true ；否则，返回 false 。return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}//栈的销毁
//也就是判断两个队列的销毁
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);//销毁q1QueueDestroy(&obj->q2);//销毁q2//因为MyStack* myStackCreate()里面有个指针pst，所以我们还要销毁指针objfree(obj);//销毁指向栈的指针obj = NULL;
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

---

3.3 用栈实现队列

点击链接答题

思路：

定义两个栈：pushST（入数据）和popST（出数据）

假设我们要在队列里放123，出队列123

我们先在pushST里面放进去1 2 3

然后把pushST里面的数据拿到popST里面，依次是3 2 1

然后把1提取出来，把2提取出来，把3提取出来.

---

如果我们先在pushST里面放进去1 2 3

然后把pushST里面的数据拿到popST里面，依次是3 2 1

然后在pushST里面放进去4

然后把popST里面的1提取出来，把2提取出来，把3提取出来.

然后把pushST里面的数据4拿到popST里面

然后把4提取出来

---

入队：往pushST中插入数据

出队：判断popST是否为空，不为空直接pop，为空的话将pushST导入到popST中再pop

取队头：跟出队一样，但这里只取数据，不pop数据

代码：

//定义栈的结构
typedef char STDataType;
typedef struct Stack {STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}ST;//栈的初始化
void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈的销毁
void STDestory(ST* ps) {assert(ps);if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("relloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0;
}//出数据
void StackPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空报错--ps->top;
}//获取栈中有效元素个数
int STSize(ST* ps){assert(ps);return ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//
typedef struct {ST pushST;ST popST;
} MyQueue;//队列的初始化
MyQueue* myQueueCreate() {MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pst->pushST);STInit(&pst->popST);return pst;
}//往pushST中插入数据
void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x);
}//删除数据
//1.检查popST是否为空，不为空直接出，为空pushST导入到popST，再出数据
int myQueuePop(MyQueue* obj) {if(StackEmpty(&obj->popST)){//如果popST为空//导数据while(!StackEmpty(&obj->pushST)){//如果pushST非空StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进popSTStackPop(&obj->pushST);}}//取栈顶，删除栈顶元素并返回栈顶数据int top = StackTop(&obj->popST);//储存删除的栈顶元素StackPop(&obj->popST);return top;//返回删除的栈顶元素
}//取队头元素
int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->popST)){//如果popST为空//导数据while(!StackEmpty(&obj->pushST)){//如果pushST非空StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进pushSTStackPop(&obj->pushST);}}//取栈顶，删除栈顶元素并返回栈顶数据return StackTop(&obj->popST);//返回删除的栈顶元素}//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}//队列的销毁
//就是两个栈的销毁
void myQueueFree(MyQueue* obj) {STDestory(&obj->pushST);STDestory(&obj->popST);free(obj);obj = NULL;
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

---

3.4 设计循环队列

点击链接答题

思路：

循环队列，空间固定。

这里我们可以用数组来实现循环队列。

---

如何判断队列是否为满？

多申请一块空间

(rear+1)%(k+1) == front

---

如何判断队列是否为空？

rear == front

代码：

//定义循环队列的结构
typedef struct {int* arr;//定义数组int front;//定义头int rear;//定义尾int capacity;//定义一个变量保存数组空间大小
} MyCircularQueue;//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {//定义一个指针，动态申请一块空间，指向循环队列MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//底层数组申请k+1个整型空间pst->arr = (int*)malloc(sizeof(int)*(k+1));pst->front = pst->rear = 0;pst->capacity = k;//把k保存起来return pst;//返回指向循环队列的指针
}//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {//(rear+1)%(k+1) == front  就满了return (obj->rear+1)%(obj->capacity+1) == obj->front;
}//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//队列满了就不能插入数据if(myCircularQueueIsFull(obj)){return false;//说明插入失败}//队列没满，可以插入数据obj->arr[obj->rear++] = value;//插入一个数据rear++obj->rear %= obj->capacity + 1;//如果rear跑到队尾了，就通过取余回到队头return true;//说明插入成功
}//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->rear == obj->front;
}//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//队列为空if(myCircularQueueIsEmpty(obj)){return false;//表示删除失败}//队列不为空obj->front++;obj->front %= obj->capacity + 1;//如果front跑到队尾了，就通过取余回到队头return true;//表示删除成功
}//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {//如果队列为空if(myCircularQueueIsEmpty(obj)){return -1;//如果队列为空，返回 -1 }//如果队列不为空return obj->arr[obj->front];
}//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {//如果队列为空if(myCircularQueueIsEmpty(obj)){return -1;//如果队列为空，返回 -1 }//如果队列不为空int prev = obj->rear-1;//prev是rear前一个位置if(obj->rear == 0){prev = obj->capacity;//如果rear是处在arr[0]，那么prev在arr[k]}return obj->arr[prev];
}//循环队列的销毁
//就是顺序表的销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);obj = NULL;
}/*** 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);
*/

---

循环队列的概念与结构

实际中还有一种特殊的队列叫循环队列，环形队列首尾相连成环，环形队列可以使用数组实现，也可以使用循环链表实现

---

思考：队列满的情况下，为什么 Q.rear 不存储数据？

为了能使用 Q.rear = Q.front 来区别是队空还是队满，我们常常认为出现左图时的情况即为队满的情况

此时： rear+1=front