LeetCode 232. 用栈实现队列

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 232. 用栈实现队列

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

思路分析

为了使用栈实现队列，我们可以使用两个栈：

inStack 用于处理入队操作。

outStack 用于处理出队操作。

具体步骤如下：

当我们进行 push 操作时，将元素压入 inStack。

当我们进行 pop 或 peek 操作时，如果 outStack 为空，则将 inStack 中的所有元素依次弹出并压入 outStack，这样 outStack 的栈顶元素就是队列的首部元素。

如果 outStack 不为空，直接从 outStack 中弹出或获取栈顶元素。

参考代码

// 定义队列结构
type MyQueue struct {
	inStack  []int
	outStack []int
}

// 初始化队列
func Constructor() MyQueue {
	return MyQueue{}
}

// 入队操作
func (q *MyQueue) Push(x int) {
	q.inStack = append(q.inStack, x)
}

// 出队操作
func (q *MyQueue) Pop() int {
	q.move()
	if len(q.outStack) <= 0 {
		return -1 // 队列为空
	}
	val := q.outStack[len(q.outStack)-1]
	q.outStack = q.outStack[:len(q.outStack)-1]
	return val
}

// 获取队首元素
func (q *MyQueue) Peek() int {
	q.move()
	if len(q.outStack) <= 0 {
		return -1 // 队列为空
	}
	return q.outStack[len(q.outStack)-1]
}

// 判断队列是否为空
func (q *MyQueue) Empty() bool {
	return len(q.inStack) <= 0 && len(q.outStack) <= 0
}

// 将 inStack 中的元素移动到 outStack 中
func (q *MyQueue) move() {
	if len(q.outStack) <= 0 {
		for len(q.inStack) > 0 {
			val := q.inStack[len(q.inStack)-1]
			q.inStack = q.inStack[:len(q.inStack)-1]
			q.outStack = append(q.outStack, val)
		}
	}
}

时间复杂度：

push 操作：O (1)

pop 操作：均摊 O (1)

peek 操作：均摊 O (1)

empty 操作：O (1)

空间复杂度：O (N)，其中 N 是队列中的元素数量。我们使用了两个栈来存储元素。

🍏 点击查看 Java 题解

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

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

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

    public int pop() {
        peek();
        return stack2.pop();
    }

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

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/06263683