[数据结构] 用两个队列实现栈详解

文章目录

一、队列实现栈的特点分析

1、1 具体分析

1、2 整体概括

二、队列模拟实现栈代码的实现

2、1 手撕 队列 代码

queue.h

queue.c

2、2 用队列模拟实现栈代码

三、总结 

---

🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️

👀 专栏：数据结构与算法、高频面试问题 👀

💥 标题：用队列模拟栈 💥

 ❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️

  我们上篇文章讲述了用两个栈实现队列 ，用过对上篇文章的学习后，我们再去学用两个队列实现栈就变得相对来说容易了很多。本篇文章会对用两个队列实现栈进行详解，希望会对你有所帮助。 

一、队列实现栈的特点分析

1、1 具体分析

 队列和栈在插入数据时，队列是从队尾进行插入，栈是从栈顶插入。但是他们的删除数据是不同的。我们知道队列的特点是：先新先出 ，删除数据是在对头进行删除，栈的特点是：先进后出，也就是在栈顶进行删除。

  当我们用队列实现栈时，最根本的也是最重要的是需要解决删除的问题。我们用队列实现栈时，在队列中的删除就不是删除对头的元素了，我们需要根据栈的特点进行删除，也就是我们需要删除的是队尾的元素。

   操作时，首先我们先往队列中插入元素。注意，我们插入元素时，应该往不为空的队列中插入元素，如果两个队列都为空，我们可以随意往一个队列中插入元素。为什么要往不为空的队列中插入元素呢？我们先接着往下看。我们是用队列模拟栈，此时我们想要删除的是栈顶的元素，也就是队尾的元素。我们需要把前size-1个元素移动到另一个空的对列中，然后再删除队列中的最后一个元素，也就是队尾元素。  这也是我们为什么插入元素时要往不为空的队列中插入的原因。因为我们需要一个空的队列进行来回导元素，从而达到删除队尾元素的目的。这时，插入操作和删除操作我们都是可以用队列去模拟实现出栈的效果了。插入和删除重复上面的操作就可以。

1、2 整体概括

  通过我们上面的分析，用队列模拟实现栈和用栈模拟队列的思路大同小异。我们看用队列模拟栈的整体思路：

• 插入时往不为空的队列插入。第一次插入时，两个队列都为空，此时随便插入一个队列即可。
• 删除时，需要把不为空的队列中的元素前size-1个元素导入到空队列中。然后再删除剩下的一个元素。
• 返回栈顶的元素，也就是返回队尾的元素。

二、队列模拟实现栈代码的实现

  我们这里用c语言实现，所以还要手撕一个队列的代码。当然C++容器中，有队列，可以直接用。大家熟悉思路后，可以用其它语言做一下本题，OJ链接：用队列实现栈 - OJ链接（LeetCode）。

2、1 手撕 队列 代码

queue.h

typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

queue.c

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestory(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)
{assert(pq);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("malloc failed");exit(-1);}tmp->next = NULL;tmp->data = x;if (pq->head == pq->tail && pq->head == NULL){pq->head = pq->tail = tmp;}else{pq->tail->next = tmp;pq->tail = tmp;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);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--;
}

2、2 用队列模拟实现栈代码

typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
void QueueDestory(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)
{assert(pq);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("malloc failed");exit(-1);}tmp->next = NULL;tmp->data = x;if (pq->head == pq->tail && pq->head == NULL){pq->head = pq->tail = tmp;}else{pq->tail->next = tmp;pq->tail = tmp;}pq->size++;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);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--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}typedef struct 
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() 
{MyStack* st=(MyStack*)malloc(sizeof(MyStack));if(st==NULL)return false;QueueInit(&st->q1);QueueInit(&st->q2);return st;
}void myStackPush(MyStack* obj, int x) 
{if(QueueSize(&obj->q1)!=0){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) 
{Queue* tmp=&obj->q1;Queue* notmp=&obj->q2;if(QueueSize(notmp)==0){tmp=&obj->q2;notmp=&obj->q1;}while(QueueSize(notmp)>1){QueuePush(tmp,QueueFront(notmp));QueuePop(notmp);}QDataType res=QueueFront(notmp);QueuePop(notmp);return res;
}int myStackTop(MyStack* obj) 
{if(QueueSize(&obj->q1)!=0)return QueueBack(&obj->q1);elsereturn QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&obj->q1)  &&  QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) 
{QueueDestory(&obj->q1);QueueDestory(&obj->q2);free(obj);
}

三、总结 

  以上就是整个用队列模拟实现栈的整个过程，主要是利用空队列删除队尾的元素。我们应该熟练掌握用队列模拟实现栈和用栈模拟实现队列，两者都是面试中的高频题目。本篇文章的讲解就到这里，希望以上对容对对你有所帮助，感谢阅读ovo~