数据结构——队列和栈的面试题分析

之前我们写过了有效括号的分析了，接下来，我们继续来学习一下，有关栈和队列之间的相关转换的题目吧。

栈实现队列

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

这里我们使用c语言的形式来写，所以我们先自己模拟一个栈。

typedef int  STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;   // top是栈顶元素的下一个位置//ps->top = -1;   // top是栈顶元素位置
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);// assert(!STEmpty(ps));ps->top--;
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

上面代码是我们之前写过的栈那篇文章的内容，如果有兴趣可以自行去了解了解鸭。

这里我们就之间来使用它就行了。

接下来我们先来讲解一下它的思路吧：

1.我们已经明白了，栈是后进先出的，队列是先进先出的。

2.那么，要使用两个栈来实现队列。下图分析：

1）push那边基本没有太大的问题，直接一个一个push到其中一个栈就行。

2）Pop那边，我们该怎么实现呢？

我们下图可以看出：

如果单单是上面的话，你直接pop，那么会发现，它会先删除4这个数字，而队列的话，它得先删1这个数字，这显然不对。所以我们得换种方法。

你看如果是这样的话：

接着，你会发现，第二个栈是不是就可以直接删去也可以达到队列的效果了。

因此我们可以有这种思路：

建立两个栈，分别是专门push和pop的栈

如果你想要插入的话，直接在push那边插就可以了，那么什么时候移动过去push的数据到pop那边呢？就当检查到pop那边的数据为空时，再把push那边的数据移动过pop即可。

好了，有了下面的铺垫后，我们开始这道题的代码。

一：建立两个栈

typedef struct {ST Pushst;ST Popst;  
} MyQueue;

此外，为了更直观地看，可以画出图片来辅助理解：

创建MyQueue部分

MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));  if(obj==NULL){perror("malloc fail");}  初始化STInit(&obj->Pushst);STInit(&obj->Popst);记得最后返回objreturn obj;
}

push部分

void myQueuePush(MyQueue* obj, int x) {STPush(&obj->Pushst,x);}

返回头数据

int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->Popst)){//倒数据while(!STEmpty(&obj->Pushst)){STPush(&obj->Popst,STTop(&obj->Pushst));STPop(&obj->Pushst);}}return STTop(&obj->Popst);
}

解释：

1.如果pop那边为空时，条件为真，进入循环。开始倒数据，（这里也就是上面我解释过的思路那里）

2.最后返回栈顶元素即可完成了。

删除部分

int myQueuePop(MyQueue* obj) {int Front=myQueuePeek(obj);STPop(&obj->Popst);return Front;
}

判断空部分

bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->Pushst) &&STEmpty(&obj->Popst);
}

这里直接用我们写的模拟栈的判断空函数部分就行了

销毁部分

void myQueueFree(MyQueue* obj) {STDestroy(&obj->Pushst);STDestroy(&obj->Popst);free(obj);
}

需要注意的是，我们这里不可以直接是否push栈，和pop栈，

但是呢我们有Destory神器，我们直接调用它就可以了。

这道题的最后，我们附上总代码：

typedef int  STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("malloc fail");return;}ps->capacity = 4;ps->top = 0;   // top是栈顶元素的下一个位置//ps->top = -1;   // top是栈顶元素位置
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);// assert(!STEmpty(ps));ps->top--;
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}typedef struct {ST Pushst;ST Popst;  
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));  if(obj==NULL){perror("malloc fail");}  STInit(&obj->Pushst);STInit(&obj->Popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(&obj->Pushst,x);}int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->Popst)){//倒数据while(!STEmpty(&obj->Pushst)){STPush(&obj->Popst,STTop(&obj->Pushst));STPop(&obj->Pushst);}}return STTop(&obj->Popst);
}int myQueuePop(MyQueue* obj) {int Front=myQueuePeek(obj);STPop(&obj->Popst);return Front;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->Pushst) &&STEmpty(&obj->Popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->Pushst);STDestroy(&obj->Popst);free(obj);
}

队列实现栈

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

1.同样，我们想到：队列是先进先出，栈是后进先出。

2.这里我们使用的方法是：

1）保持一个队列为空，一个队列存数据。

2）出栈，前面的数据倒入空队列。

好了，至此，我们开始解这道题：

1.模拟一个队列

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef char QDatatype;
typedef struct Queuenode
{struct Queuenode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QInit(Queue* pq);
void QDestory(Queue* pq);
void QueuePush(Queue* pq,QDatatype x);
void QueuePop(Queue* pq);
int Size(Queue* pq);
bool QEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
void QInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}
void QueuePop(Queue* pq)
{assert(pq);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}int Size(Queue* pq)
{assert(pq);return pq->size;
}
bool QEmpty(Queue* pq)
{assert(pq);return pq->size==0;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return pq->head->data;
}
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return pq->tail->data;
}

这个也是之前写过的文章有队列模拟实现的分析，有兴趣的可以去看看.

2.搭建两个队列

typedef struct {Queue q1;Queue q2;
} MyStack;

这里呢，可以画个图来方便理解

创建MyTack部分

MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("malloc fail");return NULL;}QInit(&pst->q1);QInit(&pst->q2);最后记得返回return pst;
}

这里跟上面一题的这个部差不多。

push部分

void myStackPush(MyStack* obj, int x) {if(!QEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}

插入部分，是看那个不为空，就往哪个队列插。

3.删除部分：

int myStackPop(MyStack* obj) {Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QEmpty(&obj->q1))   {empty=&obj->q2;nonempty=&obj->q1;}//倒数据while(Size(nonempty)>1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top=QueueFront(nonempty);QueuePop(nonempty);return top;
}

1.这里先定义两个队列的指针，一个叫空的队列，一个叫不为空的队列。（方便辨别）

由于不能保证它q1q2哪个为空，所以加一个if语句，如果不对就换过来。

2.倒数据：将原本不为空的队列的数据移动到空的，只留下最后一个数据，然后再删去。

3.最后返回头队列的数据

4.栈顶元素

int myStackTop(MyStack* obj) {if(!QEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

这里的栈顶元素，也就是队列的尾，直接返回队列的尾巴就行了。

5.判断空部分

bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) &&QEmpty(&obj->q2);
}

6.释放部分

void myStackFree(MyStack* obj) {QDestory(&obj->q1);QDestory(&obj->q2);free(obj);
}

这道题，基本就结束了，这里附上总代码：

typedef char QDatatype;
typedef struct Queuenode
{struct Queuenode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QInit(Queue* pq);
void QDestory(Queue* pq);
void QueuePush(Queue* pq,QDatatype x);
void QueuePop(Queue* pq);
int Size(Queue* pq);
bool QEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);
void QInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QDatatype x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}
void QueuePop(Queue* pq)
{assert(pq);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}int Size(Queue* pq)
{assert(pq);return pq->size;
}
bool QEmpty(Queue* pq)
{assert(pq);return pq->size==0;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return pq->head->data;
}
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QEmpty(pq));return pq->tail->data;
}
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));if(pst==NULL){perror("malloc fail");return NULL;}QInit(&pst->q1);QInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* empty=&obj->q1;Queue* nonempty=&obj->q2;if(!QEmpty(&obj->q1)){empty=&obj->q2;nonempty=&obj->q1;}//倒数据while(Size(nonempty)>1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top=QueueFront(nonempty);QueuePop(nonempty);return top;
}int myStackTop(MyStack* obj) {if(!QEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) &&QEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QDestory(&obj->q1);QDestory(&obj->q2);free(obj);
}

设置循环队列

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

注意：这里不是你要插入一个数据才开这个节点，而是最开始就要把这个链表开好。

开始的时候为空，那你是不是要一个一个插数据进去才能满啊，这个队列。

但是，当你填满之后，你会发现这里会出现一个问题：

front和rear重合了。这和刚刚开始空的时候一致啊，我们无法区分满和空这两种情况啊：

那么我们有什么方式解决呢？

这里我们有两种方式解决：

1.加size：循环的时候，增加一个size可以判断空满的问题size=0就是空，size=k就是满了

2.多一个位置（不是哨兵位）：出队列：移动front就可以了

用数组：加size
删到某一个的时候，在想要去push的话，就可以size++，或者取模的形式，就可以回去

满的时候：就是rear+1=front

同样，满的时候不能插入（即判断rear-> next ！=front），此时它不会插入了。

空的时候：就是rear的下一个是front就是了

这是推荐使用数组的形式，因为链表的唯一优势就是把尾的时候，直接next就可以了

找那个的话，这里不能--，只能-1，不然它就变了

记住你malloc几次就要free几次，不要忘记了。

好了，现在正式开始我们这道题解：

这里主要使用数组来解这道题：

建立结构体

typedef struct {数组int *a;头int front;尾int rear;长度int k;
} MyCircularQueue;

create部分

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail");}obj->front=obj->rear=0;多开一个空间obj->a=(int*)malloc(sizeof(int)*(k+1));obj->k=k;return obj;
}

1.首先是先创建好数组

2.再初始化，把front和rear置空

3.记录长度k。

4.最后记得返回obj

判断满

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}

解释：(obj->rear+1)%(obj->k+1)==obj->front;这是为了防止数组越界，%（k+1）把下标都控制在k之内。-------》就像4%7==4，%一个比它大的数，永远都在这个范围之内。

判断空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}

上面有解释了。

插入数据

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++]=value;obj->rear %=(obj->k+1);return true;
}

1.这里需要主要的是如果这个队列已经满了的话，它就不能插了，就返回错误就行了。

2.把数据插入到rear后，再++移动rear

3.这里同样要注意数组越界的情况。

4.这里入队列就是rear++，倒入数据，

删数据

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front %=(obj->k+1);return true;
}

1.出队列就是front++，唯一他们有一个点就是麻烦的点就是绕到到最后一个数据的下一个时
k+1一定要挪一下

返回头数据

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}

1.这里要注意本身就为空的情况。

返回尾数据

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}

1.注意本身队列为空的情况

2.还要防止数组越界。

释放部分

void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);    
}

最后，附上总代码

typedef struct {int *a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(obj==NULL){perror("malloc fail");}obj->front=obj->rear=0;obj->a=(int*)malloc(sizeof(int)*(k+1));obj->k=k;return obj;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear+1)%(obj->k+1)==obj->front;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->rear;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++]=value;obj->rear %=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front %=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);    
}