[数据结构与算法]java用队列实现栈、用栈实现对队列

目录

用队列实现栈

用栈实现对队列

LeetCode题

225. 用队列实现栈

232. 用栈实现队列

用队列实现栈

思路：
1.创建两个队列，
2.哪个队列不为空就将要push的元素放到该队列中，若都为空就默认放入qu1队列中，
3.pop时，将不为空的队列元素放入为空的队列中，并弹出最后一个元素

import java.util.LinkedList;
import java.util.Queue;
class MyStack {
    //1.创建两个队列
    public Queue<Integer> qu1;
    public Queue<Integer> qu2;
    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    //2.哪个队列不为空就将要push的元素放到该队列中，若都为空就默认放入qu1队列中，
    public void push(int x) {
        if(empty()){//都为空默认放入qu1中
            qu1.offer(x);
        }
        else if(!qu1.isEmpty()){//不为空就可以offer
            qu1.offer(x);
        }
        else{
            qu2.offer(x);
        }
    }
    
    //3.pop时，将不为空的队列元素放入为空的队列中，并弹出最后一个元素
    public int pop() {
        int len = 0;
        if(empty()){//都为空
            return -1;
        }
        if(!qu1.isEmpty()){//qu1不为空就放到qu2中(空)
        len = qu1.size();
            for(int i = 0; i < len - 1; ++i){//放入到qu2
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();//弹
        }
        else{
            len = qu2.size();
            for(int i = 0; i < len - 1; ++i){//放入到qu1
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();//弹
        }
    }

    //和pop一样，只是一个return元素，一个return值
    public int top() {
        int len = 0;
        int x = 0;
        if(empty()){//都为空
            return -1;
        }
        if(!qu1.isEmpty()){//不为空就放到qu2中
        len = qu1.size();

            for(int i = 0; i < len; ++i){//放入到qu2
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;//弹
        }
        else{
            len = qu2.size();
            for(int i = 0; i < len; ++i){//放入到qu1
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;//弹
        }

    }

    //判空
    public boolean empty() {
        if(qu1.isEmpty() && qu2.isEmpty()){
            return true;
        }
        return false;
    }
}

用栈实现对队列

思路：
1.创建两个栈，
2.st1栈用于压入元素，
3.st2用于弹出元素，
4.若st2为空，则将st1栈中的元素压入st2栈中

import java.util.Stack;
class MyQueue {

    //1.创建两个栈，
    Stack<Integer> st1;
    Stack<Integer> st2;
    public MyQueue() {
        st1 = new Stack();
        st2 = new Stack();
    }
    //2.st1栈用于压入元素
    public void push(int x) {
        //第一个栈入，第二个栈出
        st1.push(x);
    }
    
    //3.st2用于弹出元素
    public int pop() {
        int len = 0;
        if(empty()){//都为空
            return -1;
        }
        if(!st2.empty()){//第二个不为空，直接出
            return st2.pop();
        }
        else{//第二个为空
            len = st1.size();
            int val = 0;
            for(int i = 0; i < len; ++i){
                val = st1.pop();
                st2.push(val);
            }
            return st2.pop();
        }
    }
    
    //与pop类似，只是返回值不同
    public int peek() {
        int len = 0;
        if(empty()){//都为空
            return -1;
        }
        if(!st2.empty()){//第二个不为空，直接出
            return st2.peek();
        }
        else{//第二个为空
            len = st1.size();
            int val = 0;
            for(int i = 0; i < len; ++i){
                val = st1.pop();
                st2.push(val);
            }
            return st2.peek();
        }

    }
    //判空
    public boolean empty() {
        if(st1.empty() && st2.empty()){
            return true;
        }
        return false;
    }
}