当前位置：首页 > article >正文

用队列实现栈和用栈实现队列（下）

article 2025/3/1 19:16:38

一.队列实现栈：题目链接

题解代码：

题解思路：

二.栈实现队列：题目链接

题解代码：

题解思路:

一.队列实现栈：题目链接

题解代码：

private Queue<Integer> s1;
    private Queue<Integer> s2;


    public MyStack() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();

    }
    
    public void push(int x) {
        if(empty()) {
            s1.offer(x);
            return;
        }

        if(!s1.isEmpty()) {
            s1.offer(x);
        } else {
            s2.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(s1.isEmpty()) {
            int a = s2.size(); 
            while(a - 1 != 0) {
                s1.offer(s2.poll());
                a--;
            }
            return s2.poll();
        } else {
             int a = s1.size(); 
            while(a - 1 != 0) {
                s2.offer(s1.poll());
                a--;
            }
            return s1.poll();
        }
    }
    
    public int top() {
         if(empty()) {
            return -1;
        }
        if(s1.isEmpty()) {
            int a = s2.size(); 
            int tem = 0;
            while(a != 0) {
                tem = s2.poll();
                s1.offer(tem);
                a--;
            }
            return tem;
        } else {
             int a = s1.size(); 
             int tem = 0;
            while(a != 0) {
                tem = s1.poll();
                s2.offer(tem);
                a--;
            }
            return tem;
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }

题解思路：

首先，对于这个问题，我们可以使用两个队列来实现一个栈，保证其中栈的入元素，出元素，获取栈顶元素和判断栈是否为空的基本方法是否有效。

入元素：

如果两个队列都为空的话，我们默认入元素在 s1队列里面。

如果只是其中一个队列为空的话，则入元素在为空的队列里。

出元素：

先判断两个队列是否都为空，防止异常。

先判断那个队列为空，再把不空的队列里的元素放到空的队列里，不空的队列里剩下最后一个元素就是要出的元素。

获取栈顶元素：

这里的实现逻辑与出元素的逻辑很相像，不同的是，在放元素之前定义了一个整型变量用来存储每次出元素的值，就不用特意剩下一个元素在之前的队列里了，直接返回最后一个tem值就是要获取的栈顶元素。

二.栈实现队列：题目链接

题解代码：

private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();

    }
    
    public void push(int x) {
       
        s1.add(x);
       
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.add(s1.pop());
            }
        }
         return s2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.add(s1.pop());
            }
        }
         return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }