算法-栈和队列

Keep thinking. / 2024-03-04 / 原文

1. 用栈实现队列(LeetCode 232)

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

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

思路：

用stackin和stackout两个栈模拟队列
在dumpstackin时，需要先确认stackout是否为空；只有stackout为空时才能将stackin中的内容压入

java：

Stack常用函数:push(), pop(), empty(), peek()（返回栈顶元素，但不删除）

class MyQueue {
    // 用两个栈模拟队列
    Stack<Integer> stackin;
    Stack<Integer> stackout;

    public MyQueue() {
        stackin = new Stack<>();
        stackout = new Stack<>();
    }
    
    public void push(int x) {
        stackin.push(x);
    }
    
    // 将stackin中的元素全部放到stackout中
    private void dumpstackin(){
        //stackout清空后才能继续压入，否则顺序会出现问题
        if(!stackout.empty())   return;
        while (!stackin.empty()){
            stackout.push(stackin.pop());
        }
    }

    //移除并返回队列开头元素
    public int pop() {
        dumpstackin();
        return stackout.pop();
    }
    
    //返回队列开头元素
    public int peek() {
        dumpstackin();
        return stackout.peek();
    }
    
    public boolean empty() {
        return stackin.empty() && stackout.empty();
    }
}

2. 用队列模拟栈(LeetCode 225)

题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

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

思路：唯一需要处理的就是pop()和peek()。把que1弹出的只剩最后一个元素，即为栈顶元素。

java：

单向列表接口Queue：实现类LinkedList
双向列表接口Deque：实现类ArrayDeque
Deque可以使用addLast(), pollFirst, peekFirst()可以等效单向队列的add(), poll(), peek()

class MyStack {

    Deque<Integer> que1 = new ArrayDeque<>();
    Deque<Integer> que2 = new ArrayDeque<>();

    public MyStack() {
    }
    
    public void push(int x) {
        que1.addLast(x);
    }
    
    public int pop() {
        while(que1.size() > 1){
            que2.addLast(que1.pollFirst());
        }
        int res = que1.pollFirst();
        que1 = que2;
        que2 = new ArrayDeque<>();
        return res;
    }
    
    public int top() {
        while(que1.size() > 1){
            que2.addLast(que1.pollFirst());
        }
        int res = que1.pollFirst();
        que2.addLast(res);
        que1 = que2;
        que2 = new ArrayDeque<>();
        return res;
    }
    
    public boolean empty() {
        return (que1.size() == 0);
    }
}