数据结构刷题训练：用栈实现队列（力扣OJ）

前言

1. 题目：用栈实现队列

2. 思路

3. 分析

3.1 定义 “ 队列 ”

3.2 创建队列

3.3 入队

3.4 队头数据

3.5 出队

3.6 判空和销毁

4.题解

总结

前言

栈和队列是数据结构中的两个重要概念，它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用栈来模拟实现队列，让你在解决问题时更加灵活和创新，便于大家更深入的理解栈和队列。

1. 题目：用栈实现队列

题目描述：

题目链接：

用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/

2. 思路

这道题目的解题思路于队列实现栈有很大的相似点。这道题也是给了两个栈，要求使用两个栈来实现队列。这里我们可以使用两边倒的方式来模拟实现队列。

假设入栈：1、2、3、4那么出栈的顺序就是4、3、2、1，如果我们按照出栈的顺序再入栈到另一个栈中（空栈），再次出栈就可以达到队列出队的效果（1、2、3、4）

3. 分析

根据上述的思路我们就可以利用两个栈模拟实现队列。思路的大概过程：

那么我们来考虑一下特殊的情况，如果我们入队了1、2、3、4，出队了1和2，然后再入队5和6，这时候我们考虑一下是否还需要倒一次（将剩下的3和4入栈到原栈中，然后入栈5和6，再将3、4、5、6依次出栈，入栈到另外一个栈中）？

这里其实是不需要在倒一次，入队1、2、3、4。出队1和2，然后再入队5和6，然后再出队，出队的顺序是：1、2、3、4、5、6。我们可以将5和6入栈到原栈中，然后将3和4继续出栈，当一个栈为空时再入栈原栈中的数据。过程如下：

好的过程分析完之后，我们来对每个接口进行实现。题目中依然是没有现成的栈，所以我们依然需要 “ 造轮子 ” 前边我们已经实现的栈可以复制过来使用。

3.1 定义 “ 队列 ”

由于我们再模拟队列时需要用到两个栈，但调用函数时传两个栈又太麻烦，这里我们就使用结构体来定义两个栈（MyQueue），这样传参时就可以直接传结构体（MyQueue）指针就可以了。

typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;

3.2 创建队列

创建队列就非常简单了，我们只需要调用前边实现的InItStack函数将两个栈进行初始化就可以了：

MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    InItStack(&obj->pushst);
    InItStack(&obj->popst);

    return obj;
}

可能对结构体不熟练的同学会有疑惑：

问题一：

为什么要malloc一个空间？这里注意：前边我们仅仅只是定义了一个模拟实现的队列，定义的是类型，并没有创建结构体变量，这里malloc也仅仅只是创建一个结构体变量。

问题二：

那为什么不直接MyQueue obj；这样定义？这是在函数内部，如果这样创建结构体变量它是创建在栈区，一旦出了函数1就会被销毁，为了后续的传参，所以最好使用malloc在堆区开辟空间。

问题三：

初始化两个栈时需要取地址，那我们可不可以在定义时直接定义成指针类型例如：

Stack* pushst;
Stack* popst;

这当然可以，但是如果按照这样的写法，那么在创建 “队列” 时就需要malloc给两个栈开辟空间（在调用的初始化函数中并没有开辟空间给栈）。如果是这样定义：

typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;

那么在malloc，obj时就已经将两个栈的空间开辟好了。这样也更简单便捷。

3.3 入队

入队就很简单了，直接将数据入栈到pushst中。

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

3.4 队头数据

这里为什么先写队头数据呢？那是因为出队时不仅需要将队头移除，还需要返回被移除队头的数据。所以这里我们先实现队头数据的接口。

想要得到队头数据，那就需要将pushst中的元素按照出栈顺序入栈到popst中，然后返回popst这个栈的栈顶元素即可，过程如下：

int myQueuePeek(MyQueue* obj) {
    if(IsEmpty(&obj->popst))
    {
        while(!IsEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,TopData(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return TopData(&obj->popst);
}

这里注意：入栈到popst中的条件是popst为空，这也与上述的分析对应，popst栈为空时才可以继续将pushst中入队元素倒到popst中。

3.5 出队

有了队头数据的接口，出队接口的实现就非常简单了，在出队前保存一下队头数据（popst栈顶数据），然后将popst中的栈顶元素出栈，最后返回front即可

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);

    return front;
}

3.6 判空和销毁

判空和销毁的接口也非常简单，当两个栈都为空时就表明队列为空，代码如下：

bool myQueueEmpty(MyQueue* obj) {
    return (IsEmpty(&obj->pushst)&&IsEmpty(&obj->popst));
}

接下来是销毁，销毁队列前我们需要先将两个栈销毁，最后销毁obj。代码如下：

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    free(obj);
}

4.题解

整体代码如下：

typedef int Datatype;
typedef struct Stack
{
	Datatype* a;
	int top;
	int capacity;
}Stack;

void InItStack(Stack* ps);

void DestoryStack(Stack* ps);

void StackPush(Stack* ps, Datatype x);

void StackPop(Stack* ps);

int Stacksize(Stack* ps);

Datatype TopData(Stack* ps);

bool IsEmpty(Stack* ps);


void InItStack(Stack* ps)
{
	assert(ps);
	ps->top = 0;
	ps->a = NULL;
	ps->capacity = 0;
}

void DestoryStack(Stack* ps)
{
	assert(ps);
	ps->top = ps->capacity = 0;
	free(ps->a);
	ps->a = NULL;
}
void StackPush(Stack* ps, Datatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		Datatype* tmp = (Datatype*)realloc(ps->a, sizeof(Datatype) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
int Stacksize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
Datatype TopData(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
bool IsEmpty(Stack* ps)
{
	assert(ps);
	return (ps->top == 0);
}


typedef struct {
    Stack pushst;
    Stack popst;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    InItStack(&obj->pushst);
    InItStack(&obj->popst);

    return obj;
}

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


int myQueuePeek(MyQueue* obj) {
    if(IsEmpty(&obj->popst))
    {
        while(!IsEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,TopData(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return TopData(&obj->popst);
}

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->popst);

    return front;
}

bool myQueueEmpty(MyQueue* obj) {
    return (IsEmpty(&obj->pushst)&&IsEmpty(&obj->popst));
}

void myQueueFree(MyQueue* obj) {
    DestoryStack(&obj->popst);
    DestoryStack(&obj->pushst);
    free(obj);
}