Leetcode算法训练日记 | day10

一、用栈实现队列

1.题目

Leetcode：第 232 题
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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

2.解题思路

队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。可以用两个stack容器来实现一个队列，将入队操作转换为栈的压栈操作，而出队操作可以将输入栈的元素弹出，并压入到输出栈中，再使用输出栈弹栈即可。

3.实现代码

#include <iostream>
#include <stack>
using namespace std;

class MyQueue 
{
public:
    stack<int> stIn; //定义一个名为stIn的栈，用于存放新进入队列的元素
    stack<int> stOut; //定义一个名为stOut的栈，用于存放即将出队的元素

    MyQueue() //构造函数，初始化两个栈
    {}

    void push(int x) //入队操作
    {
        stIn.push(x); //将要入队的元素压入stIn栈中
    }

    int pop() //出队操作
    {
        //如果stOut栈为空，说明需要从stIn栈中转移元素到stOut栈
        if (stOut.empty())
        {
            while (!stIn.empty()) //当stIn栈不为空时循环转移元素
            {
                stOut.push(stIn.top()); //将要出队的元素从stIn栈转移到stOut栈
                stIn.pop(); //从stIn栈中弹出元素
            }
        }
        int result = stOut.top(); //获取stOut栈顶元素，即为队列的下一个出队元素
        stOut.pop(); //弹出stOut栈顶元素，完成出队操作
        return result; //返回出队元素
    }

    int peek() //查看队列头部元素操作
    {
        int res = this->pop(); //调用pop()函数获取队列头部元素
        stOut.push(res); //将刚刚弹出的元素再次压入stOut栈中
        return res; //返回队列头部元素
    }

    bool empty() //判断队列是否为空操作
    {
        //如果stIn栈和stOut栈都为空，则队列为空
        return stIn.empty() && stOut.empty();
    }
};

//测试
int main()
{
    MyQueue* myQueue = new MyQueue();
    myQueue->push(1); 
    myQueue->push(2); 
    cout << "队首元素：" << myQueue->peek()<<endl;
    cout << "出队元素：" << myQueue->pop() << endl;
    cout << "出队元素：" << myQueue->pop() << endl;
    cout << "队列是否为空：" << myQueue->empty()<<endl;
    cout <<endl;
    return 0;
}

二、用队列实现栈

1.题目

Leetcode：第 225 题
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：
你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

2.解题思路

我们可以将栈看成是封住队头的队列，入栈操作就是队列入队，而出栈时，我们可以先将除了队尾的那个元素（即出栈元素）以外的元素都依次出队，并再依次入队，最后出栈元素出队即可。

3.实现代码

#include <iostream>
#include <queue>
using namespace std;

class MyStack 
{
public:
    queue<int> que; //定义一个队列que，用于实现栈的功能

    MyStack() //构造函数，初始化队列que
    {
    }

    void push(int x) //入栈操作，将元素x压入栈顶
    {
        que.push(x); //直接将元素x添加到队列que的末尾
    }

    int pop() //出栈操作，移除并返回栈顶元素
    {
        int size = que.size(); //获取队列que的当前大小
        size--; //因为即将移除一个元素，所以大小减少1

        //将队列que中的所有元素（除了最后一个依次移动到队列的末尾，实现出栈操作
        while (size--)
        {
            que.push(que.front()); //取出队列头部元素并添加到队列尾部
            que.pop(); //移除队列头部元素
        }

        //此时队列尾部的元素即为原来的栈顶元素
        int result = que.front(); //获取队列头部元素，即栈顶元素
        que.pop(); //移除队列头部元素，完成出栈操作
        return result; //返回被移除的栈顶元素
    }

    int top() //获取栈顶元素的值，但不移除该元素
    {
        return que.back(); //返回队列尾部的元素，即栈顶元素
    }

    bool empty() //判断栈是否为空
    {
        return que.empty(); //如果队列que为空，则返回true，表示栈为空
    }
};

//测试
int main()
{
	MyStack* myStack = new MyStack();
	myStack->push(1);
	myStack->push(2);
	cout<<"栈顶元素："<<myStack->top() << endl;
    cout<< "弹栈：" << myStack->pop() << endl;
    cout << "栈是否为空：" << myStack->empty() << endl;
    cout << endl;
	return 0;
}

ps：以上皆是本人在探索算法世界的旅途中的浅薄见解，诚挚地希望得到各位的宝贵意见与悉心指导，若有不足或谬误之处，还请多多指教。