一文彻底搞清楚数据结构之栈与队列：从定义到实战解析

� 前言:前面我通过介绍了一些链表的算法题的解题思路和双向链表的相关知识,相信你一定有所感悟和体会!至此关于链表的内容小编就告一段落了,接下来我要介绍一种特殊的线性表—>栈和队列.它们又有什么作用和用途呢?废话不多说,下面跟着小编的节奏🎵一起学习吧！

1.栈的定义 栈是一种只允许在表的一端进行插入和删除的线性表.通常将表中允许进行插入、删除操作的一端称为栈顶,另一端称为栈底.栈的插入操作称为进栈或入栈,删除操作为出栈或退栈.当栈中没有元素时称为空栈.由于插入和删除操作都是在栈顶中进行,故栈顶元素的位置是动态变化的,它是由一个称为栈顶指针的位置指示器指示.每次进栈道元素都被放在原栈顶元素之上称为新的栈顶,而每次出栈的元素都是当前的栈顶元素,即最后进栈的元素.换句话说,最先入栈的元素最后出栈,即元素的进栈和出栈是按照"后进先出"(Last In First Out,LIFO)的原则进行的.

压栈:栈的插⼊操作叫做进栈/压栈/⼊栈,⼊数据在栈顶.

出栈:栈的删除操作叫做出栈.出数据也在栈顶.

2.栈的结构 1️⃣栈的顺序存储结构:在内存中用一组地址连续的存储单元依次存放自栈底到栈顶顶数据元素同时设置一个指针top指示栈顶元素的当前位置.可以用一个一维数组来描述.

2️⃣栈的链式存储结构:栈中的每一个数据元素用一个结点来表示,同时设置一个指针top指示栈顶元素的当前位置.

⭐️栈底层结构选型:

栈的实现⼀般可以使⽤数组或者链表实现,相对⽽⾔数组的结构实现更优⼀些.因为数组在尾上插⼊数据的代价⽐较⼩.

3.多栈共享空间 栈的应用非常广泛,经常会出现一个程序中需要同时使用多个栈的情况.由于各个栈的实际大小在使用过程中会发生变化,故其所需空间大小难以准确估计.为了避免出现有的栈溢出有的栈空闲的情况,可以让多个栈共享一个足够大的数组空间,使空间充分利用.

以最常用的两栈共享空间为例:

栈满的条件是:top1=top2+1;栈空的条件是:top1=0或top2=M-1.

两栈共享空间比两个栈分别申请M/2的空间利用率要高.

4.栈的实现 stack.c

代码语言：javascript复制#include"Stack.h"

void StackInit(ST* ps)

{

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//销毁

void StackDestroy(ST* ps)

{

if (ps->arr)

free(ps->arr);

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//入栈---栈顶

void StackPush(ST* ps, STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

//增容

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc 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(!StackEmpty(ps));

--ps->top;

}

//取栈顶元素

STDataType StackTop(ST* ps)

{

assert(!StackEmpty(ps));

return ps->arr[ps->top - 1];

}

//获取栈中有效元素个数

int StackSize(ST* ps)

{

return ps->top;

} stack.h

代码语言：javascript复制#pragma once

#include

#include

#include

#include

//定义栈的结构

typedef int STDataType;

typedef struct Stack

{

STDataType* arr;

int top; //指向栈顶的位置

int capacity;//栈的容量

}ST;

//初始化

void StackInit(ST* ps);

//销毁

void StackDestroy(ST* ps);

//入栈---栈顶

void StackPush(ST* ps, STDataType x);

//出栈——栈顶

void StackPop(ST* ps);

//取栈顶元素

STDataType StackTop(ST* ps);

//获取栈中有效元素个数

int StackSize(ST* ps);

//栈是否为空

bool StackEmpty(ST* ps); test.c

代码语言：javascript复制#include"Stack.h"

void test01()

{

ST st;

StackInit(&st);

StackPush(&st, 1);

StackPush(&st, 2);

StackPush(&st, 3);

StackPush(&st, 4);

StackPush(&st, 5);

StackPop(&st);

StackPop(&st);

StackPop(&st);

StackPop(&st);

StackPop(&st);

while (!StackEmpty(&st))

{

int top = StackTop(&st);

printf("%d ", top);

StackPop(&st);

}

int size = StackSize(&st);

printf("size:%d\n", size);

StackDestroy(&st);

}

int main()

{

test01();

return 0;

}5.队列的定义 队列它只允许在表的一端进行插入操作,而在另一端进行删除操作.队列中允许进行插入操作的一端称为队尾,允许进行删除操作的一端称为队头.队列的插入操作称为进队,队列的删除操作称为出队.没有元素的队列称为空队.队列的结构与现实生活中排队的规则是一致的,后来的成员总是加入到队尾,每次离开队列的总是队头上的成员.也就是说,队列中的元素按照"先进先出(First in Frist Out,FIFO)"的原则进行的.

⼊队列:进⾏插⼊操作的⼀端称为队尾.

出队列:进⾏删除操作的⼀端称为队头.

6.队列的结构 1️⃣队列的顺序存储结构:在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素,同时设置两个指针front和rear分别指示队头元素和队尾元素的位置.

2️⃣队列的链式存储结构:队列中每一个元素对应链表中的一个结点,并设置两个分别指示队头和队尾的指针.

⭐️队列底层结构选型:队列也可以数组和链表的结构实现,使⽤链表的结构实现更优⼀些,因为如果使⽤数组的结构,出队列在数组头上出数据,效率会⽐较低.

7.队列的实现 Queue.c

代码语言：javascript复制#include"Queue.h"

//初始化

void QueueInit(Queue* pq)

{

assert(pq);

pq->phead = pq->ptail = NULL;

//pq->size = 0;

}

//销毁队列

void QueueDestroy(Queue* pq)

{

assert(pq);

QueueNode* pcur = pq->phead;

while(pcur)

{

QueueNode* next = pcur->next;

free(pcur);

pcur = next;

}

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 = pq->ptail->next;

}

//pq->size++;

}

//队列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->phead == NULL;

}

//出队——队头

void QueuePop(Queue* pq)

{

assert(!QueueEmpty(pq));

//只有一个节点，phead和ptail都套置为空

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

else {

QueueNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

//pq->size--;

}

//取队头数据

QDataType QueueFront(Queue* pq)

{

assert(!QueueEmpty(pq));

return pq->phead->data;

}

//取队尾数据

QDataType QueueBack(Queue* pq)

{

assert(!QueueEmpty(pq));

return pq->ptail->data;

}

//队列有效元素个数

int QueueSize(Queue* pq)

{

assert(pq);

//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景

QueueNode* pcur = pq->phead;

int size = 0;

while (pcur)

{

size++;

pcur = pcur->next;

}

return size;

//第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景

//return pq->size;

} Queue.h

代码语言：javascript复制#pragma once

#include

#include

#include

#include

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 QueueDestroy(Queue* pq);

//入队——队尾

void QueuePush(Queue* pq, QDataType x);

//出队——队头

void QueuePop(Queue* pq);

//队列判空

bool QueueEmpty(Queue* pq);

//队列有效元素个数

int QueueSize(Queue* pq);

//取队头数据

QDataType QueueFront(Queue* pq);

//取队尾数据

QDataType QueueBack(Queue* pq); test.c

代码语言：javascript复制#include"Queue.h"

void test01()

{

Queue q;

QueueInit(&q);

QueuePush(&q, 1);

QueuePush(&q, 2);

QueuePush(&q, 3);

QueuePop(&q);

int front = QueueFront(&q);

int rear = QueueBack(&q);

printf("front:%d\n", front);

printf("rear:%d\n", rear);

printf("size:%d", QueueSize(&q));

QueueDestroy(&q);

}

int main()

{

test01();

return 0;

}8.栈和队列的算法题 1.有效括号

代码语言：javascript复制//定义栈的结构

typedef char STDataType;

typedef struct Stack

{

STDataType* arr;

int top; //指向栈顶的位置

int capacity;//栈的容量

}ST;

void StackInit(ST* ps)

{

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//销毁

void StackDestroy(ST* ps)

{

if (ps->arr)

free(ps->arr);

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//入栈---栈顶

void StackPush(ST* ps, STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

//增容

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc 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(!StackEmpty(ps));

--ps->top;

}

//取栈顶元素

STDataType StackTop(ST* ps)

{

assert(!StackEmpty(ps));

return ps->arr[ps->top - 1];

}

//获取栈中有效元素个数

int StackSize(ST* ps)

{

return ps->top;

}

//栈的实现代码

bool isValid(char* s) {

ST st;

StackInit(&st);

char*pi =s;

while(*pi !='\0')

{

//左括号入栈

if(*pi=='('|| *pi =='['|| *pi == '{')

{

StackPush(&st,*pi);

}else{

//判断栈为空的情况

if(StackEmpty(&st))

{

StackDestroy(&st);

return false;

}

//右括号--取栈顶跟*pi进行匹配

char top =StackTop(&st);

if((top =='('&& *pi !=')')

||(top == '['&& *pi !=']')

||(top == '{'&& *pi !='}'))

{

StackDestroy(&st);

return false;

}

StackPop(&st);

}

pi++;

}

bool ret =StackEmpty(&st)?true:false;

StackDestroy(&st);

return ret;

} 2.用队列实现栈

代码语言：javascript复制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 QueueDestroy(Queue* pq)

{

assert(pq);

QueueNode* pcur = pq->phead;

while(pcur)

{

QueueNode* next = pcur->next;

free(pcur);

pcur = next;

}

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 = pq->ptail->next;

}

//pq->size++;

}

//队列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->phead == NULL;

}

//出队——队头

void QueuePop(Queue* pq)

{

assert(!QueueEmpty(pq));

//只有一个节点，phead和ptail都套置为空

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

else {

QueueNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

//pq->size--;

}

//取队头数据

QDataType QueueFront(Queue* pq)

{

assert(!QueueEmpty(pq));

return pq->phead->data;

}

//取队尾数据

QDataType QueueBack(Queue* pq)

{

assert(!QueueEmpty(pq));

return pq->ptail->data;

}

//队列有效元素个数

int QueueSize(Queue* pq)

{

assert(pq);

//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景

QueueNode* pcur = pq->phead;

int size = 0;

while (pcur)

{

size++;

pcur = pcur->next;

}

return size;

//第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景

//return pq->size;

}

//以上是队列结构和方法的实现

typedef struct {

Queue q1;

Queue q2;

} MyStack;

//初始化

MyStack* myStackCreate() {

MyStack* pst = (MyStack*)malloc(sizeof(MyStack));

QueueInit(&pst->q1);

QueueInit(&pst->q2);

return pst;

}

void myStackPush(MyStack* obj, int x) {

//往不为空的队列中插入数据

if(!QueueEmpty(&obj->q1))

{

QueuePush(&obj->q1,x);

}else{

QueuePush(&obj->q2,x);

}

}

//将不为空队列中前size-1个数据挪到另一个队列中

//再将最后一个数据出队列

int myStackPop(MyStack* obj) {

Queue* emp = &obj->q1;

Queue* noneEmp = &obj->q2;

if(QueueEmpty(&obj->q2))

{

emp = &obj->q2;

noneEmp = &obj->q1;

}

while(QueueSize(noneEmp) > 1)

{

QueuePush(emp,QueueFront(noneEmp));

QueuePop(noneEmp);

}

int top = QueueFront(noneEmp);

QueuePop(noneEmp);

return top;

}

//取栈顶

int myStackTop(MyStack* obj) {

//找不为空队列中的队尾数据

if(!QueueEmpty(&obj->q1))

{

return QueueBack(&obj->q1);

}else{

return QueueBack(&obj->q2);

}

}

bool myStackEmpty(MyStack* obj) {

return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

//销毁

void myStackFree(MyStack* obj) {

QueueDestroy(&obj->q1);

QueueDestroy(&obj->q2);

free(obj);

obj = NULL;

} 3.用栈实现队列

在这里插入图片描述代码语言：javascript复制//定义栈的结构

typedef int STDataType;

typedef struct Stack

{

STDataType* arr;

int top; //指向栈顶的位置

int capacity;//栈的容量

}ST;

void StackInit(ST* ps)

{

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//销毁

void StackDestroy(ST* ps)

{

if (ps->arr)

free(ps->arr);

ps->arr = NULL;

ps->top = ps->capacity = 0;

}

//入栈---栈顶

void StackPush(ST* ps, STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

//增容

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc 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(!StackEmpty(ps));

--ps->top;

}

//取栈顶元素

STDataType StackTop(ST* ps)

{

assert(!StackEmpty(ps));

return ps->arr[ps->top - 1];

}

//获取栈中有效元素个数

int StackSize(ST* ps)

{

return ps->top;

}

//以上是栈结构和方法的实现

typedef struct {

ST pushST;

ST popST;

} MyQueue;

MyQueue* myQueueCreate() {

MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));

StackInit(&pq->pushST);

StackInit(&pq->popST);

return pq;

}

void myQueuePush(MyQueue* obj, int x) {

//往pushST中插入数据

StackPush(&obj->pushST,x);

}

//检查popST是否为空

//1）不为空，直接出popST栈顶

//2)为空，pushST数据导入到popST中，再出popST栈顶

int myQueuePop(MyQueue* obj) {

if(StackEmpty(&obj->popST))

{

//导数据

while(!StackEmpty(&obj->pushST))

{

StackPush(&obj->popST,StackTop(&obj->pushST));

StackPop(&obj->pushST);

}

}

int top = StackTop(&obj->popST);

StackPop(&obj->popST);

return top;

}

int myQueuePeek(MyQueue* obj) {

if(StackEmpty(&obj->popST))

{

//导数据

while(!StackEmpty(&obj->pushST))

{

StackPush(&obj->popST,StackTop(&obj->pushST));

StackPop(&obj->pushST);

}

}

return StackTop(&obj->popST);

}

bool myQueueEmpty(MyQueue* obj) {

return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);

}

void myQueueFree(MyQueue* obj) {

StackDestroy(&obj->pushST);

StackDestroy(&obj->popST);

free(obj);

obj = NULL;

}9.循环队列的定义 将队列的存储空间看成一个环状的空间,即将队列的首、尾位置连接起来形成的结构称为循环队列.

循环队列中的元素变化与头、尾指针的关系如图所示.循环队列初始化时,front=rear;a1~a5依次进队后,队头元素是a1,队尾元素是a5;然后,a1和a2相继出队,a6～a10依次进队后,则队列空间被占满,此时,front=rear.

在循环队列中,指针front和rear在到达数组末尾后将自动回到数组开始的位置,即它们是由0～MAXSIZE之间循环变化的.

队列为空的判断:front==rear

队列为满的判断:(rear+1)%MAXSIZE=front

10.循环队列的算法题 设计循环队列

在这里插入图片描述代码语言：javascript复制typedef struct {

int*arr;

int front;//队头

int rear;//队尾

int capacity;//循环队列的空间大小

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {

MyCircularQueue* pq =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

//申请k+1个空间

pq->arr=(int*)malloc(sizeof(int)*(k+1));

pq->front=pq->rear= 0;

pq->capacity= k;

return pq;

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

return obj->front == obj->rear;

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

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;

obj->rear %= obj->capacity + 1;

return true;

}

//从循环队列中删除一个元素

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

{

return false;

}

//非空

++obj->front;

obj->front %= obj->capacity+1;

return true;

}

//从队首获取元素

int myCircularQueueFront(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

{

return -1;

}

return obj->arr[obj->front];

}

//获取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) {

if(myCircularQueueIsEmpty(obj))

{

return -1;

}

int prev =obj->rear-1;

if(obj->rear == 0)

{

prev =obj->capacity;

}

return obj->arr[prev];

}

void myCircularQueueFree(MyCircularQueue* obj) {

if(obj->arr)

{

free(obj->arr);

free(obj);

obj=NULL;

}

} 敬请期待下一篇文章内容:数据结构之堆!

以上就是今天的博客内容了，希望能够帮助到读者朋友们！

我们一起继续加油努力💪！一键三连🙏！！！

本篇完结，点赞收藏加关注，找到小编不迷路，感谢大家🙏🤝！