回顾数据结构——使用两个栈实现一个队列和用两个队列实现一个栈

男娘i 2022-11-28 13:56 198阅读 0赞

今天下午有面试，早上先来无事，写一篇博客压压惊，由于时间不多，先写个思路和实现代码，图后面有时间补上。

## 使用两个栈实现一个队列 ##

核心思想：因为栈是先进后出的，所以自身带有翻转的光环，那队列不就是栈翻转后的结构么，因此只需要将stack1的数据给它按照栈的特性放到stack2上那就解决问题了

package com.wrial.kind.design;
    /*
     * @Author  Wrial
     * @Date Created in 11:24 2020/8/18
     * @Description 使用两个栈实现一个队列
     */
    
    import java.util.Stack;
    
    public class Queue<E> {
    
        private Stack<E> stack1 = new Stack<>();
        private Stack<E> stack2 = new Stack<>();
    
        public void add(E e) {
            stack1.push(e);
        }
    
        public E remove() {
            if (stack2.size() != 0) {
                return stack2.pop();
            }
            int size = stack1.size();
            if (size == 0) return null;
            for (int i = 0; i < size; i++) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    
        public static void main(String[] args) {
            Queue<Integer> queue = new Queue<>();
            queue.add(1);
            queue.add(2);
            System.out.println(queue.remove());
            System.out.println(queue.remove());
            System.out.println(queue.remove());
        }
    }

## 使用两个队列实现一个栈 ##

核心思想：因为队列是先进先出的，不能像栈一个自带有反转属性，因此我们可以使用一个临时队列queue2用来暂存queue1.size()-1个数据，然后让queue1剩下一个元素，这个元素移动是最尾端的元素，将这个元素移除，再将queue2的数据放回到queue1中，如此就可实现一个栈

package com.wrial.kind.design;
    /*
     * @Author  Wrial
     * @Date Created in 11:24 2020/8/18
     * @Description  用两个队列实现一个栈
     */
    
    import java.util.LinkedList;
    
    public class Stack<E> {
    
        private LinkedList<E> queue1 = new LinkedList<>();//出栈
        private LinkedList<E> queue2 = new LinkedList<>();//辅助
    
        public void push(E num) {
            queue1.addFirst(num);
        }
    
        public E pop(){
            if (queue1==null) return null;
            if (queue1.size()==1) return queue1.removeLast();
            int size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.addFirst(queue1.removeLast());
            }
            return queue1.removeLast();
        }
    
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            System.out.println(stack.pop());
        }
    
    }