LeetCode232. 用栈实现队列🌟🌟🌟🌟🌟简单

课后作业

问题描述

原文链接：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

提示：

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

代码实现

Java

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }

        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }

        return stack2.pop();
    }

    public int peek() {
        if(!stack2.isEmpty()){
            return stack2.peek();
        }
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }

        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Python

class MyQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)

    def pop(self):
        """
        :rtype: int
        """
        if self.stack2:
            return self.stack2.pop()

        while self.stack1:
            self.stack2.append(self.stack1.pop())

        return self.stack2.pop()

    def peek(self):
        """
        :rtype: int
        """
        if self.stack2:
            return self.stack2[-1]

        while self.stack1:
            self.stack2.append(self.stack1.pop())

        return self.stack2[-1]

    def empty(self):
        """
        :rtype: bool
        """
        return not self.stack1 and not self.stack2

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

C++

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

public:
    MyQueue() {

    }

    void push(int x) {
        stack1.push(x);
    }

    int pop() {
        if (!stack2.empty()) {
            int val = stack2.top();
            stack2.pop();
            return val;
        }

        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }

        int val = stack2.top();
        stack2.pop();
        return val;
    }

    int peek() {
        if (!stack2.empty()) {
            return stack2.top();
        }

        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }

        return stack2.top();
    }

    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

// Your MyQueue object will be instantiated and called as such:
// MyQueue* obj = new MyQueue();
// obj->push(x);
// int param_2 = obj->pop();
// int param_3 = obj->peek();
// bool param_4 = obj->empty();

Go

type MyQueue struct {
    stack1 []int
    stack2 []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    this.stack1 = append(this.stack1, x)
}

func (this *MyQueue) Pop() int {
    if len(this.stack2) > 0 {
        val := this.stack2[len(this.stack2)-1]
        this.stack2 = this.stack2[:len(this.stack2)-1]
        return val
    }

    for len(this.stack1) > 0 {
        val := this.stack1[len(this.stack1)-1]
        this.stack1 = this.stack1[:len(this.stack1)-1]
        this.stack2 = append(this.stack2, val)
    }

    val := this.stack2[len(this.stack2)-1]
    this.stack2 = this.stack2[:len(this.stack2)-1]
    return val
}

func (this *MyQueue) Peek() int {
    if len(this.stack2) > 0 {
        return this.stack2[len(this.stack2)-1]
    }

    for len(this.stack1) > 0 {
        val := this.stack1[len(this.stack1)-1]
        this.stack1 = this.stack1[:len(this.stack1)-1]
        this.stack2 = append(this.stack2, val)
    }

    return this.stack2[len(this.stack2)-1]
}

func (this *MyQueue) Empty() bool {
    return len(this.stack1) == 0 && len(this.stack2) == 0
}

// Your MyQueue object will be instantiated and called as such:
// obj := Constructor();
// obj.Push(x);
// param_2 := obj.Pop();
// param_3 := obj.Peek();
// param_4 := obj.Empty();

shuaidi永久会员

收藏 海报 链接