代码随想录算法训练营第九天 | LeetCode 232(用栈实现队列) LeetCode 225(用队列实现栈)

栈和队列理论基础

定义

栈（stack ），一种遵循先进后出（FILO—First-In/Last-Out）原则的线性存储结构。
队列（queue），一种遵循先进先出（FIFO—first in first out）原则的线性存储结构

栈方法

队列方法

232：用栈实现队列

LeetCode 232(用栈实现队列)

方法一

import java.util.Stack;
class MyQueue {
    /**
     * 栈的操作
     * push(e) 入栈
     * pop() 弹出栈顶元素 并返回
     * push()  返回栈顶元素
     */
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;



    public MyQueue() {
        this.stackIn = new Stack<Integer>();
        this.stackOut = new Stack<Integer>();
    }
    
    public void push(int x) {
        //入栈
        stackIn.push(x);
    }
    
    public int pop() {
        if(!stackOut.empty()){
            return stackOut.pop();
        }
        while(!stackIn.empty()){
            stackOut.push(stackIn.pop());
        }
        return stackOut.pop();
    }
    
    public int peek() {
        if(!stackOut.empty()){
            return stackOut.peek();
        }
        while(!stackIn.empty()){
            stackOut.push(stackIn.pop());
        }
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

225：用队列实现栈

LeetCode 225(用队列实现栈)

方法一 双队列实现

import java.util.LinkedList;
import java.util.Queue;
class MyStack {
    //输入队列
    Queue<Integer> queueIn;
    //备份队列
    Queue<Integer> queueCopy;

    public MyStack() {
        queueIn = new LinkedList<>();
        queueCopy = new LinkedList<>();
    }
    
    public void push(int x) {
        //置于辅助队列
        queueCopy.offer(x);
        //将输入队列的元素添加到辅助队列
        while(!queueIn.isEmpty()){
            queueCopy.offer(queueIn.remove());
        }
        //再将辅助队列元素转移到输入队列
        while(!queueCopy.isEmpty()){
            queueIn.offer(queueCopy.remove());
        }
    }
    
    public int pop() {
        return queueIn.remove();
    }
    
    public int top() {
        return queueIn.peek();
    }
    
    public boolean empty() {
        return queueIn.isEmpty();
    }
}

方法二 单队列实现

import java.util.LinkedList;
import java.util.Queue;
class MyStack {
    //输入队列
    Queue<Integer> queueIn;

    public MyStack() {
        queueIn = new LinkedList<>();
    }
    
    public void push(int x) {
        queueIn.add(x);
    }
    
    public int pop() {
        int size = queueIn.size() - 1;
        while(size-- > 0){
            queueIn.offer(queueIn.remove());
        }
        return queueIn.remove();
    }
    
    public int top() {
        int size = queueIn.size() - 1;
        while(size-- > 0){
            queueIn.offer(queueIn.remove());
        }
        int result = queueIn.remove();
        queueIn.offer(result);
        return result;
    }
    
    public boolean empty() {
        return queueIn.isEmpty();
    }
}