简单题 用栈实现对列

本题来自：232. 用栈实现队列 - 力扣（LeetCode）

目录

题面：

代码：

题面：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

代码：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持动态增长的栈
typedef int STDataType;

typedef struct Stack
{
	STDataType* _a;
	int _top; // 栈顶
	int _capacity; // 容量
}Stack;

// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
// 初始化栈
void StackInit(Stack* ps)
{
	ps->_a = (STDataType*)malloc(sizeof(STDataType)*4);
	ps->_top = 0;
	ps->_capacity = 4;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		ps->_capacity *= 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * ps->_capacity);
		if (tmp == NULL)
			exit(-1);
		ps->_a = tmp;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top != 0);
	(ps->_top)--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空，如果为空返回1，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top == 0 ? 1 : 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
	free(ps->_a);
	ps->_capacity = 0;
	ps->_top = 0;
}

// 以上是手搓栈
//
// 本代码是使用c语言实现，如果使用c++就不用手搓栈了
//
// 以下是题给接口实现代码

typedef struct MyQueue
{
	Stack _push; // 这个栈只存数据，即每次数据都放在这个栈里
	Stack _pop;  // 每次取数据都从这个栈去取
} MyQueue;


MyQueue* myQueueCreate() 
{
	MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue)); 
	StackInit(&pq->_push);
	StackInit(&pq->_pop);
	return pq;
}

void myQueuePush(MyQueue* obj, int x) //只往push栈中存数据
{
	StackPush(&obj->_push, x);
}

int myQueuePop(MyQueue* obj) // 依赖myQueuePeek接口，不同的是取完元素后弹出栈顶元素
{
	int ret = myQueuePeek(obj);
	StackPop(&obj->_pop);
	return ret;
}

int myQueuePeek(MyQueue* obj) // 本题的核心接口
{
	if (StackEmpty(&obj->_pop) == 1) // 如果pop栈为空，说明数据都在push栈存储
	{
		while (StackEmpty(&obj->_push) != 1) // 把push栈中的所有数据挪到pop栈
		{
			StackPush(&obj->_pop, StackTop(&obj->_push));
			StackPop(&obj->_push);
		}
	}
	return StackTop(&obj->_pop); // 打出pop栈的第一元素，不需要销毁pop栈
}

bool myQueueEmpty(MyQueue* obj) // 需要pop和push同时为空
{
	return StackEmpty(&obj->_push) && StackEmpty(&obj->_pop);
}

void myQueueFree(MyQueue* obj) 
{
	StackDestroy(&obj->_pop);
	StackDestroy(&obj->_push);
	free(obj);
}
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

思路解析：

（这里数字的顺序是左端为栈顶，右端为栈底）

本题的关键在于两个栈如何实现对列的操作，栈的原则是后进先出，对列是先进先出

不难发现将1234存入栈之后取出来就是4321，完全逆序了，再存到另一个栈就是4321，再取出就是1234，符合队列的需求了。

还要解决的问题是中途取数据，中途存数据也不能打乱顺序

我们用两个栈_push和_pop来实现操作，其中push栈负责接收每次的数据，pop负责出数据

入数据的不管三七二十一，统统往push栈放

出数据的时候，要判断一下pop栈是否为空，如果pop为空，就把push栈的所有元素取出来放到pop栈中，一次性把push栈清空，这些数据都存在pop栈，会发现pop出栈的顺序和对列的顺序一样。

比如，push入栈了1234，取出来的时候就是4321，拿到pop就是1234，出的时候就是1，2，3，4

pop栈不为空的时候，直接取栈顶元素就好了

本题相对于用对列实现栈还简单一些。

完