双队列实现栈？双栈实现队列？

女爷i 2023-09-28 17:54 152阅读 0赞

**目录**

双队列实现栈

最容易理解的办法

双栈实现队列

最容易理解的办法

--------------------

# 双队列实现栈 #

> 单个队列是无法实现栈的，双队列是可以的，如下分析（例如**出栈**）

![cddb62a0ca5c441a81557d5909c57940.png][]

![053222a4399c4ab5b32940e0edea1be5.png][]

![e94b8d814e454ce5b781bd94de8b181e.png][]

![df5e3982fdf5429fb8a023a27149b41a.png][]

> 注意：

*  **哪个队列不为空就放入哪个将元素放入哪个队列**
 *  **若两个都为空，任选一个队列放入即可**

> 如下代码：

class MyStack {
        public Queue<Integer> q1;
        public Queue<Integer> q2;
        public int usedSize;
        public MyStack() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }
        //压栈
        public void push(int x) {
            //哪个队列不为空，往那里里面放，都为空就放q1
            if(!q1.isEmpty()){
                q1.offer(x);
            }
            else if(!q2.isEmpty()){
                q2.offer(x);
            }
            else{
                q1.offer(x);
            }
            usedSize++;
        }
        //出栈
        public int pop() {
            //哪个队列不为空，就从哪里取元素放到另一个队列里
            if(empty()){
                return -1;
            }
            if(!q1.isEmpty()){
                //转移usedSize - 1个元素到另一个队列
                //for(int i = 0; i < usedSize - 1; i++)//不能这样写，usedSize会随着出栈不断减少
                int size = usedSize;
                for(int i = 0; i < size - 1; i++){
                    q2.offer(q1.poll());
                }
                usedSize--;
                return q1.poll();
            }
            else{
                int size = usedSize;
                for(int i = 0; i < size - 1; i++){
                    q1.offer(q2.poll());
                }
                usedSize--;
                return q2.poll();
            }
        }
        
        public int top() {
            //哪个队列不为空，就从哪里取元素放到另一个队列里
            if(empty()){
                return -1;
            }
            int tmp = 0;
            if(!q1.isEmpty()){
                int size = usedSize;
                for(int i = 0; i < size - 1; i++){
                    q2.offer(q1.poll());
                }
                tmp = q1.peek();
                q2.offer(q1.poll());
            }
            else{
                int size = usedSize;
                for(int i = 0; i < size - 1; i++){
                    q1.offer(q2.poll());
                }
                tmp = q2.peek();
                q1.offer(q2.poll());
            }
            return tmp;
        }
        //判空
        public boolean empty() {
            return usedSize == 0;
        }
    }

## 最容易理解的办法 ##

画个图就清楚啦~

class MyStack {
    
        private Queue<Integer> queue1 = new LinkedList<>(); 
        private Queue<Integer> queue2 = new LinkedList<>(); 
    
        public MyStack() {
            
        }
        
        public void push(int x) {
            while(!queue1.isEmpty()) {
                queue2.offer(queue1.poll());
            }
            queue1.offer(x);
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }
        }
        
        public int pop() {
            return queue1.poll();
        }
        
        public int top() {
            return queue1.peek();
        }
        
        public boolean empty() {
            return queue1.isEmpty();
        }
    }

##  ##

--------------------

# 双栈实现队列 #

> 单个栈是无法实现队列的，双栈是可以的，如下分析（例如**出队**）

![2c721e363f8b42e18d39baf64f6e4403.png][]

![2b639cfd60b84a03ae8943ad2602d963.png][]

![b7c6a10a6e5d433e817a4cc25acb5f1c.png][]

![b46c8791bda4446ea9151968d2384b40.png][]

> 注意：

*  **出队之前一定要先检查s2中是否有元素，若有直接弹出即可，若没有再将s1全部压入s2中**
 *  **检查队列首元素也是如此(peek)**

> 代码如下：

class MyQueue {
        public Stack<Integer> s1;//入栈
        public Stack<Integer> s2;//出栈
        public MyQueue() {
            this.s1 = new Stack<>();
            this.s2 = new Stack<>();
        }
        //进队
        public void push(int x) {
            s1.push(x);
        }
        //出队
        public int pop() {
            if(empty()) {
                return -1;
            }
            //s2如同蓄水池，一旦要出队列，就全压s1
            //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
            if(s2.empty()){
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
                return s2.pop();
            }
            //如果s2里有元素，就直接弹出
            return s2.pop();
        }
        public int peek() {
            if(empty()) {
                return -1;
            }
            //s2如同蓄水池，一旦要出队列，就全压s1
            //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
            if(s2.empty()){
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
                return s2.peek();
            }
            //如果s2里有元素，就直接弹出
            return s2.peek();
        }
        
        public boolean empty() {
            return s1.empty() && s2.empty();
        }
    }

## 最容易理解的办法 ##

画个图就知道了~

class MyQueue {
    
        private Stack<Integer> stack1 = new Stack<>();
        private Stack<Integer> stack2 = new Stack<>();
    
        public MyQueue() {
            
        }
        
        public void push(int x) {
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            stack1.push(x);
            while(!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
        }
        
        public int pop() {
            return stack1.pop();
        }
        
        public int peek() {
            return stack1.peek();
        }
        
        public boolean empty() {
            return stack1.isEmpty();
        }
    }

--------------------

![dd6d2d5cb9ba4b8585f405c45d90fa01.gif][]

[cddb62a0ca5c441a81557d5909c57940.png]: https://img-blog.csdnimg.cn/cddb62a0ca5c441a81557d5909c57940.png
[053222a4399c4ab5b32940e0edea1be5.png]: https://img-blog.csdnimg.cn/053222a4399c4ab5b32940e0edea1be5.png
[e94b8d814e454ce5b781bd94de8b181e.png]: https://img-blog.csdnimg.cn/e94b8d814e454ce5b781bd94de8b181e.png
[df5e3982fdf5429fb8a023a27149b41a.png]: https://img-blog.csdnimg.cn/df5e3982fdf5429fb8a023a27149b41a.png
[2c721e363f8b42e18d39baf64f6e4403.png]: https://img-blog.csdnimg.cn/2c721e363f8b42e18d39baf64f6e4403.png
[2b639cfd60b84a03ae8943ad2602d963.png]: https://img-blog.csdnimg.cn/2b639cfd60b84a03ae8943ad2602d963.png
[b7c6a10a6e5d433e817a4cc25acb5f1c.png]: https://img-blog.csdnimg.cn/b7c6a10a6e5d433e817a4cc25acb5f1c.png
[b46c8791bda4446ea9151968d2384b40.png]: https://img-blog.csdnimg.cn/b46c8791bda4446ea9151968d2384b40.png
[dd6d2d5cb9ba4b8585f405c45d90fa01.gif]: https://img-blog.csdnimg.cn/dd6d2d5cb9ba4b8585f405c45d90fa01.gif