526互联

04-栈和队列

发布时间 2023-11-09 09:43:44作者: 犹豫且败北

4. 栈和队列

栈：push，pop，peek（返回当前值），empty

队列：add，remove，peek（返回当前值），isEmpty

4.1 双向链表实现栈和队列

4.2 数组实现栈和队列

加一个指针指向某个位置。

队列：环形数组

4.3 最小栈

1. 题目

https://leetcode.cn/problems/min-stack/

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

2. 思路

两个栈，A栈放值，B栈放当前A的最小值（新加入的时候，如果比最小值大就接着放之前的最小值，如果比最小值小，就放新的最小值）

3. 代码

class MinStack {
    Deque<Integer> val;
    Deque<Integer> min;
    public MinStack() {
        val = new LinkedList<Integer>();
        min = new LinkedList<Integer>();
    }
    
    public void push(int val) {
        this.val.push(val);
        if(this.min.isEmpty()){
            this.min.push(val);
        }else{
            int cur = this.min.peek();
            if(cur > val){
                this.min.push(val);
            }else{
                this.min.push(cur);
            }
        }
    }
    
    public void pop() {
        if(!val.isEmpty()){
            val.pop();
            min.pop();
        }
    }
    
    public int top() {
        return val.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

4.4 用栈实现队列

1. 题目

https://leetcode.cn/problems/implement-queue-using-stacks/

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

实现 MyQueue 类：

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

输入：
["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. 思路

两个栈，一个in，一个out，

进入：加入到in栈。

弹出：如果out为空，就把in倒入，否则弹出out。

3. 代码

class MyQueue {
    Stack<Integer> in;
    Stack<Integer> out;
    public MyQueue() {
        in = new Stack<Integer>();
        out = new Stack<Integer>();
    }
    public void inToOut(){
        while(!in.empty()){
            out.push(in.pop());
        }
    }
    public void push(int x) {
        in.push(x);
    }
    
    public int pop() {
        if(out.empty()){
            // 清空in到out中
            inToOut();
        }
        return out.pop();
    }
    
    public int peek() {
        if(out.empty()){
            // 清空in到out中
            inToOut();
        }
        return out.peek();
    }
    
    public boolean empty() {
        if(out.empty() && in.empty()){
            return true;
        }
        return false;
    }
}

4.4 用队列实现栈

1. 题目

https://leetcode.cn/problems/implement-stack-using-queues/

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

实现 MyStack 类：

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

输入：
["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. 思路

两个队列，A，B，不断转换状态。

弹出：A中只留一个剩下加入B，B转为活跃，A的弹出。而后B中只留下一个剩下加入A，A转为活跃，B弹出

进入：加入到活跃队列中

3. 代码

class MyStack {
    Queue<Integer> a;
    Queue<Integer> b;
    char alive;
    public MyStack() {
        a = new LinkedList<Integer>();
        b = new LinkedList<Integer>();
        alive = 'a';
    }

    public int changeQue(Queue<Integer> from, Queue<Integer> to){
        int size = from.size();
        // 导出，只留最后一个
        for(int i = 0; i < size-1; i++){
            int temp = from.remove();
            to.add(temp);
        }
        alive = alive == 'a'?'b':'a';
        return from.remove();
    }

    public void push(int x) {
        if(alive == 'a'){
            a.add(x);
        }else{
            b.add(x);
        }
    }
    
    public int pop() {
        int val = 0;
        if(alive == 'a'){
            val =  changeQue(a,b);
        }else{
            val = changeQue(b,a);
        }
        return val;
    }
    
    public int top() {
       int val = 0;
       if(alive == 'a'){
           val = changeQue(a,b);
           b.add(val);
            
        }else{
            val = changeQue(b,a);
            a.add(val); 
        } 
        return val;
    }
    
    public boolean empty() {
        if(a.isEmpty() && b.isEmpty()){
            return true;
        }
        return false;
    }
}