与队列和栈相关的【OJ题】

✨✨✨专栏：数据结构     

          🧑‍🎓个人主页：SWsunlight

目录

 

 一、用队列实现栈：

1、2个队列的关联起来怎么由先进先出转变为先进后出：（核心）

 2、认识各个函数干嘛用的：

3、代码实现：

二、用栈实现队列：

1、题目:

2、思路：

 3、代码：

 三、设计循环队列:

1、题目：

 2、思路：

​编辑

3、代码：

---

 

 一、用队列实现栈：

内容如下：

 2个队列实现栈：：首先考虑的是  栈的规则：先进后出（后进先出）

                                                   队列的规则：先进先出

1、2个队列的关联起来怎么由先进先出转变为先进后出：（核心）

 如上图，外围框架（虚构的，为了更好理解，让他具体化）就是我要实现的栈，而我要通过2个队列来实现栈，是不是是可以让小球先走上面的“通道”进去，全部小球（元素）进入上“通道”中，此时我排在通道最后的小球（元素）就是我要出栈的第一个数据。

---

如下图：2号球要第一个出栈，我们发现下“通道”是空的，那么我让2号球前面的球离开这个“通道”去到下面的通道，上通道就会剩下一个2号球，此时取2号球顺利的第一个走出去，就相当于栈的Top(将后进的元素取出)

 反复进行，就可以实现栈了，(队尾的元素能出栈，其他位置得绕着2个通道来回转（有点像明知她(他)不爱你，你还是要困死再这颗树），只有自己在成为队尾了（心灰意冷了），才会幡然醒悟（不能再一直停留再原地绕圈了，要向前看啦)

 2、认识各个函数干嘛用的：

可能只是对我而言 

我已经标好了，各个函数的功能：知道功能就好实现了

这个结构体的成员放2个队列即可：

 

 结构体MyStack嵌套2个（队列）结构体（Queue）——>Queue的结构体在嵌套节点的结构体

如下：头节点后面还会链接更多的尾节点

 

3、代码实现：

将之前写队列的代码复制过来直接可以用了

typedef int QUDataType;
//节点
typedef struct QueueNode{QUDataType a;//一定要用指针，不然结构体的大小就无法确定了struct QueueNode *next;
}QuNode;
//再建立一个保存头和尾的结构体
typedef struct Queue {QuNode* head;QuNode* tail;int size;
}Queue;//初始化头尾节点
void QuInto(Queue* q)
{//不能传空指针  即（q=NULL）assert(q);q->head = NULL;q->tail = NULL;q->size = 0;
}//尾插(2种情况：1.头尾都为NUL  2.又数据入队列了)
void QuPush(Queue* q, QUDataType x)
{//申请空间QuNode* newnode = (QuNode*)malloc(sizeof(QuNode));//判空if (newnode == NULL){perror("malloc");return;}newnode->a = x;newnode->next = NULL;//节点创建完成//判断尾的位置if (q->tail == NULL){q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}//头删(删除到尾以后，就不能再删了)
void QuPop(Queue* q)
{assert(q);//头的位置也不能为空assert(q->size!=0);//此时数据个数为1（也就是最后一个节点）if (q->head->next==NULL){free(q->head);q->head = q->tail = NULL;}else//q->head != q->tail；{QuNode* next = q->head->next;free(q->head);q->head = next;}//数据个数也要减去q->size--;}//判空
bool QuEmpty(Queue* q)
{assert(q);//头尾都相等时到达同一个位置，此时就为真，其他的情况都为假；return q->size==0;
}//取头数据
QUDataType QuFront(Queue* q)
{assert(q);assert(q->head);return q->head->a;
}//取尾数据
QUDataType QuBack(Queue* q)
{assert(q);//队尾都为空了，已经没数据了assert(q->tail);return q->tail->a;
}
//数据个数
int QuSize(Queue* q)
{assert(q);return q->size;
}//销毁空间(写进数据，想要一次性释放完就来用)
void QuDestroy(Queue* q)
{assert(q);QuNode* cur = q->head;while (cur){QuNode* next = cur->next;free(cur);cur = next;}q->head = q->tail =NULL;q->size = 0;
}//2个队列
typedef struct {Queue q1;Queue q2;
} MyStack;//初始化
MyStack* myStackCreate() {MyStack*pts = (MyStack*)malloc(sizeof(MyStack));if(pts==NULL){perror("malloc");//exit(1);return NULL;}QuInto(&pts->q1);QuInto(&pts->q2);return pts;  
}
//插入
void myStackPush(MyStack* obj, int x) {//判空插入,将数据插入不为空的队列if(!QuEmpty(&obj->q1)){QuPush(&obj->q2,x);}else{QuPush(&obj->q2,x);}
}
//删除并取出top元素
int myStackPop(MyStack* obj) {//假设法：no存不为空Queue* noEmpty = &obj->q1;Queue* empty = &obj->q2;if(!QuEmpty(empty)){noEmpty = &obj->q2;empty = &obj->q1;}//我们要让size-1个数据去到那条空通道while(QuSize(noEmpty)>1){//头删，所以取头int x = QuFront(noEmpty);QuPop(noEmpty);//将其数据存到size-1个数据存入空道QuPush(empty,x);}//随便头还是尾取，因为此时这通道只有最后一个元素了int top =QuFront(noEmpty);QuPop(noEmpty);return top;
}
//直接取top元素
int myStackTop(MyStack* obj) {//不要删除，只是取元素，那么取不为空的通道的队尾元素（因为根据栈的原则：先出的是队尾元素）if(!QuEmpty(&obj->q1)){return QuBack(&obj->q1);}else{return QuBack(&obj->q2);}
}
//判空
bool myStackEmpty(MyStack* obj) {//2个都是空同通道则为真，否则为假return QuEmpty(&obj->q1)&&QuEmpty(&obj->q2);
}
//销毁
void myStackFree(MyStack* obj) {QuDestroy(&obj->q1);QuDestroy(&obj->q2);free(obj);obj = NULL;
}

 关于销毁：要先从小（从内向外）的开始，我们应该先从q1和q2进行销毁，在销毁obj

obj申请的空间是为2个队列开辟的，2个队列申请的空间又是为里面的单链表开辟的，你直接销毁大哥，小弟起步就是群龙无首，变成了“野狗”

二、用栈实现队列：

1、题目:

2

2、思路：

和上面思路大差不差

先画图：和上面说的类似，不做赘述

 区别1：栈的top指向的是  栈顶元素   还是  栈顶元素下一个位置

根据之前我写的top指向的是栈顶元素的下一个位置叙说：如下

没有数据是top = 0；当存入一个时top = 1；

 

 所以你再取数据放到空的栈时应该也要注意先pop一下再取

 还有一个需要注意的点：它比队列实现栈跟倔强（醒悟的更慢）！！！

一个栈里面的数据如下：

 4 3 2 取出放到下面的空栈中

 流程图如下:1 就顺利走了，以为这样就完事了？？一开始我也这样想的，结果碰壁了

将1取走后，根据之前的思路，再pop时就会将3 2放到上面栈，那么最后出队顺序变成了：1 4 2 3

乱套了

非常不对劲

 我想到了再回转一次，这样就可以保证我开始入队时的顺序不变，也就是将上面的栈作为出数据用，每次出一次数据，就将其他数据入栈到下面的栈，出完再回到上面的栈，无论你

可以理解为：不撞南墙不回头（心死了，才向前）！！！！头比较硬哈，越靠后撞的次数越多

 3、代码：

有更好的代码，作参考即可

typedef int LTDataType;
//顺序表（栈）
typedef struct SL
{LTDataType* a;int top;int capacity;
}SL;
//入栈
void SLPush(SL* p,LTDataType x)
{//不能传NULL,判空;assert(p);if (p->top == p->capacity){//先判断是否为0，好进行扩容int newnode = p->capacity == 0 ? 4 : 2 * (p->capacity);//扩容；创建一个临时变量接收新的空间，成功在将其交给p->a；LTDataType* s = (LTDataType*)realloc(p->a,newnode * sizeof(LTDataType));if (s == NULL){perror("realloc");return;}p->a = s;p->capacity = newnode;}p->a[p->top] = x;//指向下一个数据地址p->top++;
}
//出栈(类似尾删)
void SLPop(SL* p)
{//是否为空assert(p);assert(p->top > 0);p->top--;
}
//初始化
void SLInit(SL* p)
{p->a = NULL;p->capacity = 0;//p->top = -1;//指向栈顶的数据p->top = 0;//指向栈顶的下一个数据
}
//销毁
void SLDestroy(SL* p)
{assert(p);free(p->a);p->a = NULL;p->capacity = p->top = 0;
}
//判空
bool SLEmpty(SL* p)
{//不能是空地址assert(p);//为0就是真(true)，为1就是假(flase)return p->top == 0;
}
//数据个数
int SLsize(SL* p)
{int size = p->top;return size;
}
//取数据：
LTDataType SLPot(SL*p)
{assert(p);return p->a[p->top];
}//2个栈
typedef struct {SL q1;SL q2;
} MyQueue;//初始化
MyQueue* myQueueCreate() {MyQueue*pts = (MyQueue*)malloc(sizeof(MyQueue));if(pts==NULL){perror("malloc");return NULL;}SLInit(&pts->q1);SLInit(&pts->q2);return pts;
}
//入队
void myQueuePush(MyQueue* obj, int x) {//非空，存数据:一定要注意top，我的top是指向栈顶元素的下一个位置if(!SLEmpty(&obj->q1)){SLPush(&obj->q1,x);}else{SLPush(&obj->q2,x);}
}
//出队
int myQueuePop(MyQueue* obj) {//假设法：SL *noEmpty =&obj->q1;SL *empty =&obj->q2;if(!SLEmpty(empty)){noEmpty =&obj->q2;empty =&obj->q1;}while(SLsize(noEmpty)>1){//根据top指向位置要先popSLPop(noEmpty);int x = SLPot(noEmpty);SLPush(empty,x);}SLPop(noEmpty);int Top = SLPot(noEmpty);while(!SLEmpty(empty)){//根据top指向位置要先popSLPop(empty);int x = SLPot(empty);SLPush(noEmpty,x);}return Top;
}
//取
int myQueuePeek(MyQueue* obj) {SL*qq1 = &obj->q1;SL*qq2 = &obj->q2;//直接取第一个进去的数据if(!SLEmpty(qq1)){return qq1->a[0];}else{        return qq2->a[0];}}
//判空
bool myQueueEmpty(MyQueue* obj) {return SLEmpty(&obj->q1)&&SLEmpty(&obj->q2);
}
//销毁
void myQueueFree(MyQueue* obj) {SLDestroy(&obj->q1);SLDestroy(&obj->q2);free(obj);obj = NULL;
}

 三、设计循环队列:

粗略讲解一下：循环队列

循环队列是一种线性数据结构。它也被称为“环形缓冲器”，大致就是一个队列有了空间大小，这个空间只能存出的数据是有限个，满了不能存，未满则可以继续存，相当于苍蝇馆吃饭，比较火爆，只能坐下k个人，那么就得排队，若是离开一个，就能进去一个，接着走

 

1、题目：

 

 2、思路：

有链表和顺序表（数组）都可以实现，我用的数组，因为更简单一点：

根据上面的介绍可以知道，循环列队要一个标记首和尾的变量（head和tail）

初状态:都在头的位置，下标来看的话就是  0 的位置

检查队列满和空的情况：

空的情况：很简单，就是head = tail

---

满队时，tail应该指向的下一个位置，存一个数据tail后移一位，所以如下：4个数据的空间，满队时，刚好 tail = k（k表示数据个数（空间大小））要判满的话  也是tail==head才行，

tail%k==head；   但是这么做的话有问题：空也是head == tail，这不是冲突么！ 

有2种方法：任选，操作难度差不多

1、设置size ——记下数据个数

2、多创建一个空间

当满栈时，tail与head差了一步，我们写下 （tail+1）%（k+1）；有点抽象，看下面

 

给它用环来看：是不是更清晰了，头和尾的差了一个 1也就是tail+1；因为数组是一块连续的空间，所以我们要用%(k+1)将尾和头相连 

插入数据时，需要注意tail的取值：

 先存数据再给tail = tail+1；但是tail不能一直往后走的（循环规定了循环的范围）！！！！它的取值只能是[0,k];所以要写一个tail %=（k+1）;  因为x%k  (取值为：0 —— k-1)

 若是数据如此：tail是在下标为5的位置，后面是不能用的，所以要将tail传回到头去，保证了差一步（保证了一个空间不能用，因为我们多申请了一个，这个空间只是饰品，不能用）

 

取尾元素：

 tail的位置是下一个元素的位置，所以要用tail-1来调用，但是有坑，当tail的位置到达了下标0处，还能减掉吗？？？那不就是-1么，但是我们要的取的值tail-1的范围应该是[o,k]这个区间范围内

上面我们是  tail = tail%（k+1）;——>>> tail-1 = tail%（k+1)-1;

我们要将它区间变成[0,k];  变形：

 

3、代码：

typedef struct {int *a;int head;int tail;int k;
} MyCircularQueue;
//因为在判空和判满的上面的函数需要调用他俩，所以我们要进行函数声明
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//初始化：
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue*pts = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(pts==NULL){perror("malloc");return NULL;}pts->a = (int*)malloc(sizeof(int)*(k+1));if(pts->a==NULL){perror("malloc");return NULL;}pts->k = k;pts->tail = pts->head =0;return pts;
}//插入，返回真假
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//是否为满，满了就不能插入；if(myCircularQueueIsFull(obj)){return false;}else{obj->a[obj->tail]= value;obj->tail++;obj->tail%=(obj->k+1);return true;}}
//删除：返回真假
bool myCircularQueueDeQueue(MyCircularQueue* obj) {//是否为空，为空不能删除if(myCircularQueueIsEmpty(obj)){return false;}else{obj->head++;obj->head%=(obj->k+1);return true;}
}
//取头元素
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else{return obj->a[obj->head];}
}
//取尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else{return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];}
}
//s是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}
//是否满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return obj->head == (obj->tail+1)%(obj->k+1);
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);obj->a =NULL;free(obj);obj = NULL;}