526互联

LeetCode225.用队列实现栈

发布时间 2023-10-30 22:02:22作者: 白布鸽

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

示例

image

提交的代码

方法一：

import java.util.Deque;
import java.util.LinkedList;

class MyStack {
    Deque<Integer> inQueue;
    Deque<Integer> outQueue;

    public MyStack() {
        inQueue=new LinkedList<>();
        outQueue=new LinkedList<>();
    }
    
    public void push(int x) {
        inQueue.offerLast(x);
    }
    
    public int pop() {
        dumpQueue();
        return outQueue.pollFirst();
    }
    
    public int top() {
        dumpQueue();
        return outQueue.peekFirst();
    }
    
    public boolean empty() {
        return inQueue.isEmpty()&&outQueue.isEmpty();
    }

    public void dumpQueue(){
        if(inQueue.isEmpty())return;
        while(!inQueue.isEmpty()){
            outQueue.offerFirst(inQueue.pollFirst());
        }
    }
}

实现的思想和上一篇实现栈的思想类似。只不过dumpQueue方法和dumpStack方法中判断空的逻辑变了一些。

方法二

import java.util.Queue;
import java.util.LinkedList;

class MyStack {
    Queue<Integer> mainQueue;
    Queue<Integer> auxQueue;

    public MyStack() {
        mainQueue=new LinkedList<>();
        auxQueue=new LinkedList<>();
    }
    
    public void push(int x) {
        while(!mainQueue.isEmpty()){
            auxQueue.offer(mainQueue.poll());
        }
        mainQueue.offer(x);
        while(!auxQueue.isEmpty()){
            mainQueue.offer(auxQueue.poll());
        }
    }
    
    public int pop() {
        return mainQueue.poll();
    }
    
    public int top() {
        return mainQueue.peek();
    }
    
    public boolean empty() {
        return mainQueue.isEmpty();
    }

}

实现的思想就是主队列来模拟栈(倒着的),当offer元素时，先将主队列的元素出队依次添加到辅助队列的末尾，保持次序不变，然后将新添加的元素添加到主队列的尾部(此时队列为空，也是头部),然后再将辅助队列依次出队并加入主队列的后面。

学习到的东西

本来还想找一下jdk官方对于Queue实现的，但是发现有个Deque(Double end queue)这个类既可以做栈又可以做队列，和Queue的操作类似，不过加了个first和last而已(offerFirst,offerLast,pollFirst,pollLast,peekFirst,peekLast)。