代码随想录算法训练营第十天 | 232.用栈实现队列、225. 用队列实现栈

2023-12-22 15:59:35

232.用栈实现队列

题目链接:232.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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(双端队列)来模拟一个栈,只要是标准的栈操作即可。

文章讲解/视频讲解:https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

思路

设置两个栈,分别为stack1,stack2。

当采用push操作时,将元素推到stack1中去。

当采用pop或者peek操作时,如果是第一次请求或此时stack2为空,将stack1中所有元素全部pop出来,推入stack2中,

此时stack2的栈顶就是所实现队列的队列头。而如果此时stack2中还有元素,则只需要pop出stack2当前栈顶元素即可。

判断是否为空,只需要判断当前两个栈stack1和stack2是否都为空即可。

C++实现

class MyQueue {
private:
    stack<int> stack1;
    stack<int> stack2;

public:
    MyQueue() {

    }
    
    void push(int x) {
        stack1.push(x);
    }
    
    int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int value = stack2.top();
        stack2.pop();
        return value;
    }
    
    int peek() {
        if(stack2.empty()){
            while(!stack1.empty()){
                int tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
        }
        int value = stack2.top();
        return value;
    }
    
    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

225. 用队列实现栈

题目链接:225. 用队列实现栈

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

文章讲解/视频讲解:https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

思路

可以仅采用一个队列来实现。

定义一个队列queue1,实现push操作,只需要将元素置入队尾即可。

实现pop操作时,可以先记录当前队列的长度length,然后不断地将元素从队首排出,再推入队列尾部,这个循环持续length - 1次。

此时队列首部的元素正是构建的栈的栈顶,将该元素从队首排出即可。

对于top操作来说,前面的循环过程于pop类似,只是当获得该元素的值后,再将该元素从队首排出,推入队列尾部。

判断实现的栈是否为空,只需要判断队列是否为空即可。

C++实现

class MyStack {
private:
    queue<int> queue1;

public:
    MyStack() {

    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        int length = queue1.size();
        for(int i = 0;i<length-1;i++){
            int tmp = queue1.front();
            queue1.pop();
            queue1.push(tmp);
        }
        int value = queue1.front();
        queue1.pop();
        return value;
    }
    
    int top() {
        int length = queue1.size();
        for(int i = 0;i<length-1;i++){
            int tmp = queue1.front();
            queue1.pop();
            queue1.push(tmp);
        }
        int value = queue1.front();
        queue1.pop();
        queue1.push(value);
        return value;
    }
    
    bool empty() {
        return queue1.empty();
    }
};

文章来源:https://blog.csdn.net/weixin_43347688/article/details/135153857
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。