【数据结构】队列OJ：两个栈实现队列、两个队列实现栈、实现最小值栈

梦里梦外; 2023-09-27 13:26 135阅读 0赞

**目录**

一、两个栈实现队列

二、两个队列实现栈

三、最小值栈----可获取栈的最小值

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

## 一、两个栈实现队列 ##

栈的特点是先进后出，而队列的特点是先进先出。用栈实现队列的时候，我们定义一个栈把他作为专门用于入队的栈，然后另一个栈做为出队的栈。在进行offer入队操作时我们直接把他存入入队栈，然后在进行出队操作时，我们先判断出队栈是不是空，如果是空就将入队栈的是数据出栈入栈到出队栈，然后再进行出战，数据经过两个栈原来先进的数据在出队栈的栈顶，此时出栈操作出来的数据就是入栈时先进来的，实现了先进先出

入队时：直接进入入队栈

![0806ad8b5ba64aad9890d829509099dd.png][]

出队时：此时先判断出队栈是不是空，此时为空，就先将入队栈里的数据不断出栈，然后入栈到出队栈里：

![ad45574a44bb4e108a24be14057aafdd.png][]

此时将出队栈里的数据出队顺序为1 2 3 4 5，满足先进先出。入队操作还是照常入队到入队栈，出队时，如果上次数据全部出队，出队栈为空时，就再次将入队栈里的数据存放到出队栈里

class TwoStackImplementQueue<T>{
        private Stack<T> stack1 = new Stack<>();   //入队操作的栈
        private Stack<T> stack2 = new Stack<>();   //出队操作的栈
    
        /**
         * offer
         * @param data
         */
        public void offer(T data){
            //只管进入入队栈
            stack1.push(data);
        }
    
        /**
         * poll
         * @return
         */
        public T poll(){
            //先判断出队栈是否空
            if(stack2.empty()){
                //空时将入队栈里的数据全部拿过来
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
    
            //此处要判断入队栈是否为空，防止入队栈与出队栈都为空栈空异常
            return stack2.empty() ? null : stack2.pop();
        }
    
        /**
         * peek
         * @return
         */
        public T peek(){
            //先判断出队栈是否空
            if(stack2.empty()){
                while(!stack1.empty()){
                    stack2.push(stack1.pop());
                }
            }
    
            //此处要判断入队栈是否为空，防止入队栈与出队栈都为空栈空异常
            return stack2.empty() ? null : stack2.peek();
        }
    }

## 二、两个队列实现栈 ##

两个队列实现栈，我们在入栈时，如果此时为第一次插入，就让他进入队1，此后再插入数据时，找到不空的队列进行插入，始终保持一个队列为空的状态。

![28f37737a9d04742b4b4d0652dbea59e.png][]在出栈操作时，此时空的队列就起到了至关重要的作用，我们先找到存数据的队列，计算他的长度为n后，由于队列是先进先出所以让他的前n-1个数据出队存到为空的队列里，再将剩余的最后入队的数据弹出，从而实现了后进先出，在获取栈顶元素时，执行同样的操作，不过细节是将所有的数据全部存入另一个空队，每次出队 入空队时记录当前的值，最后执行完成，记录的当前值就是最后入队的那个元素，也就是栈顶元素

![682b384d3ab143a99d23544c804207da.png][]

class TwoQueueImplementStack<T>{
        private Queue<T> queue1 = new LinkedList<>();
        private Queue<T> queue2 = new LinkedList<>();
    
        /**
         * push
         * @param data
         */
        public void push(T data){
            //如果队列1不为空就入队1，如果队2为不空就入队2，如果都为空就入队1
            if(!queue1.isEmpty()){
                queue1.offer(data);
            }else if(!queue2.isEmpty()){
                queue2.offer(data);
            }else{
                queue1.offer(data);
            }
        }
    
        /**
         * pop
         * @return
         */
        public T pop(){
            //先找到哪个队列不空，将不空的数据的前n-1个存入另一个空队，然后将最后这个元素弹出返回
            if(!queue1.isEmpty()){
                //将队里只留一个元素，其他存入另一个队
                int size = queue1.size() - 1;
                while(size-- != 0){
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }else{
                int size = queue2.size() - 1;
                while(size-- != 0){
                    queue1.offer(queue2.poll());
                }
                return queue2.isEmpty() ? null : queue2.poll();
            }
        }
    
        /**
         * peek
         * @return
         */
        public T peek(){
            if(!queue1.isEmpty()){
                int size = queue1.size();
                T ret = null;      //定义变量记录每次的数据
                while(size-- != 0){
                    ret = queue1.poll();
                    queue2.offer(ret);
                }
                return ret;
            }else{
                int size = queue2.size();
                T ret = null;
                while(size-- != 0){
                    ret = queue2.poll();
                    queue1.offer(ret);
                }
                return ret;
            }
        }
    }

## 三、最小值栈----可获取栈的最小值 ##

用两个栈实现最小值栈，一个栈用于存放存入的数据从，另一个栈用于存放当前栈的最小值。数据入栈时先进入普通栈，然后再与最小值栈的栈顶元素进行比较，如果小于等于就存入最小值栈里

出栈时普通栈里出来的元素与最小值栈顶元素进行对比，如果一样就一起出

class MinStack<T extends Comparable<T>>{
        private Stack<T> normalStack = new Stack<>();
        private Stack<T> minStack = new Stack<>();
    
        /**
         * push
         * @param data
         */
        public void push(T data){
            //正常入栈
            normalStack.push(data);
    
            //判断是否存入最小值栈
            if(minStack.empty()){
                //如果最小栈为空，存入数据
                minStack.push(data);
            }else if(data.compareTo(minStack.peek()) <= 0){
                //如果比最小值栈顶元素小或者等于就入栈
                minStack.push(data);
            }
        }
    
        /**
         * pop
         * @return
         */
        public T pop(){
            if(normalStack.empty()){
                //如果为空返回null
                return null;
            }
    
            //出栈时与最小值栈顶比较如果相同就一起出
            T normalVal = normalStack.peek();
            T minVal = minStack.peek();
    
            if(minVal.compareTo(normalVal) == 0){
                normalStack.pop();
                minStack.pop();
            }else{
                normalStack.pop();
            }
    
            return normalVal;
        }
    
        /**
         * 获取栈的最小值
         * @return
         */
        public T getMin(){
            //如果空就返回null，如果不为空就获取最小值栈栈顶元素
            return minStack.empty() ? null : minStack.peek();
        }
    }

[0806ad8b5ba64aad9890d829509099dd.png]: https://img-blog.csdnimg.cn/0806ad8b5ba64aad9890d829509099dd.png
[ad45574a44bb4e108a24be14057aafdd.png]: https://img-blog.csdnimg.cn/ad45574a44bb4e108a24be14057aafdd.png
[28f37737a9d04742b4b4d0652dbea59e.png]: https://img-blog.csdnimg.cn/28f37737a9d04742b4b4d0652dbea59e.png
[682b384d3ab143a99d23544c804207da.png]: https://img-blog.csdnimg.cn/682b384d3ab143a99d23544c804207da.png