文章目录

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

1、1 具体分析

1、2 整体概括

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

2、1 手撕 栈 代码

2、1、1 stack.h

2、1、2 stack.c

2、2 用栈实现队列代码

---

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

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

? 标题：用栈模拟队列 ?

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

  在数据结构中，栈和队列是较为常见的两种数据结构。他们各有自己的特点：栈是后进先出原则，队列是先进先出原则。那怎么用栈去实现队列呢？此问题在面试中也是高频出现的问题。本篇文章会给出详细解释。

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

1、1 具体分析

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

  当我们用栈实现队列时，最根本的也是最重要的是需要解决删除的问题。我们用栈实现队列时，在栈中的删除就不是删除栈顶的元素了，我们需要根据队列的特点进行删除，也就是我们需要删除的是栈底的元素。  怎么删除栈底的元素呢？在这里我们需要两个栈，分别命名为push栈和pop栈。我们先把元素的插入全部插入到push栈中，当需要删除时，我们首先把push栈中的元素全部导入到pop栈中，此时的pop栈中的栈顶元素，相当于我们要删除的对头元素了。

  那如果我们想要接着插入呢？我们接着往push栈中插入即可。删除的话我们看pop栈中是否有元素，如果pop栈不为空，就接着删除，如果pop栈为空，我们需要把push栈的元素再次导入到pop栈中删除即可。具体流程我们可以结合下图（gif）理解： 

1、2 整体概括

  用栈模拟队列我们整体的思路分为以下几步：

我们需要先定义两个栈，分别为push栈和pop栈；插入数据到往push栈中；删除数据时，需要先判断pop栈是否为空。如果为空，需要将push栈的所有数据导入到pop栈中。如果不为空，就直接在pop栈删除即可。再插入数据时，就往push栈中插入即可。

  以上即为用栈模拟队列的全过程，那我们来看代码的实现。

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

  这里我们用c语言进行实现。所以我们这里需要先手撕出一个栈。

2、1 手撕 栈 代码

2、1、1 stack.h

#define INT_CAPACITY 4typedef int STDataType;typedef struct stack{STDataType* a;int top;int capacity;}ST;void STInit(ST* ps);void STDestory(ST* ps);bool STIsEmpty(ST* ps);void STPush(ST* ps, STDataType x);void STPop(ST* ps);int STSize(ST* ps);STDataType STTop(ST* ps);

2、1、2 stack.c

void STInit(ST* ps){assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType)* INT_CAPACITY);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->top = 0;ps->capacity = INT_CAPACITY;}void STDestory(ST* ps){assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;}bool STIsEmpty(ST* ps){assert(ps);return ps->top==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");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top++] = x;}void STPop(ST* ps){assert(ps);assert(!STIsEmpty(ps));ps->top--;}int STSize(ST* ps){assert(ps);return ps->top;}STDataType STTop(ST* ps){assert(ps);assert(!STIsEmpty(ps));return ps->a[ps->top - 1];}

2、2 用栈实现队列代码

这个是OJ链接（ 用栈实现队列 - OJ链接（力扣）），大家可以直接点开链接用其他语言做一下。我们看C语言的代码实现。

#define INT_CAPACITY 4typedef int STDataType;typedef struct stack{STDataType* a;int top;int capacity;}ST;void STInit(ST* ps);void STDestory(ST* ps);bool STIsEmpty(ST* ps);void STPush(ST* ps, STDataType x);void STPop(ST* ps);int STSize(ST* ps);STDataType STTop(ST* ps);void STInit(ST* ps){assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType)* INT_CAPACITY);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->top = 0;ps->capacity = INT_CAPACITY;}void STDestory(ST* ps){assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;}bool STIsEmpty(ST* ps){assert(ps);return ps->top==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");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top++] = x;}void STPop(ST* ps){assert(ps);assert(!STIsEmpty(ps));ps->top--;}int STSize(ST* ps){assert(ps);return ps->top;}STDataType STTop(ST* ps){assert(ps);assert(!STIsEmpty(ps));return ps->a[ps->top - 1];}typedef struct {    ST StackPop;    ST StackPush;} MyQueue;MyQueue* myQueueCreate(){    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));    STInit(&obj->StackPop);    STInit(&obj->StackPush);    return obj;}void myQueuePush(MyQueue* obj, int x) {    STPush(&obj->StackPush,x);}int myQueuePeek(MyQueue* obj) {    if(STSize(&obj->StackPop)==0)    {        while(STSize(&obj->StackPush)!=0)        {            STPush(&obj->StackPop,STTop(&obj->StackPush));            STPop(&obj->StackPush);        }    }    return STTop(&obj->StackPop);}int myQueuePop(MyQueue* obj) {    int ret=myQueuePeek(obj);    STPop(&obj->StackPop);    return ret;}bool myQueueEmpty(MyQueue* obj) {    return STSize(&obj->StackPop)==0 && STSize(&obj->StackPush)==0;}void myQueueFree(MyQueue* obj) {    STDestory(&obj->StackPop);    STDestory(&obj->StackPush);    free(obj);}