算法案例(3)----------用俩个栈构造一个队列

妖狐艹你老母 2023-06-29 11:59 35阅读 0赞

# 零、简介 #

*  记录 左程云 大神的  程序员代码面试指南 一书里面的算法实现。
 *  代码路径： [https://github.com/1956025812/algorithm][https_github.com_1956025812_algorithm] 
 *  2020年开始每周一道算法，成就自己的算法之路~

# 一、题目 #

*  题目： 用俩个栈构造一个队列
 *  要求： 编写一个类，用俩个栈实现队列，支持队列的基本操作(add, peek, poll)

# 二、思考 #

## 2.1 实现思路  ##

*  栈是先进后出，队列是先进先出。由俩个栈正好可以模拟队列。
 *  一个栈做push栈，一个栈做pop栈。
 *  入队操作直接将数据放到push栈。
 *  出队操作，如果push栈内数据不为空，则直接使用push栈的pop/peek操作即可；出队操作，如果push栈内数据为空，则把push栈的数据 全部 挪到push栈中，然后push栈进行出队。

## 2.2 图形说明 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjYx_size_16_color_FFFFFF_t_70][]

# 三、案例 #

## 3.1 代码 ##

package day20200112;
    
    import java.util.Stack;
    
    /**
     * 题目：  由俩个栈组成的队列
     * 要求：  编写一个类，用俩个栈实现队列，支持队列的基本操作(add, peek, poll)
     * <p>
     * 思路：
     * 1. 栈是先进后出，队列是先进先出。由俩个栈正好可以模拟队列。
     * 2. 一个栈做push栈，一个栈做pop栈。
     * 3. 入队操作直接将数据放到push栈。
     * 4. 出队操作，如果push栈内数据不为空，则直接使用push栈的pop/peek操作即可；
     * 5. 出队操作，如果push栈内数据为空，则把push栈的数据 全部 挪到push栈中，然后push栈进行出队。
     * <p>
     **/
    
    public class Stack2Queue {
    
        private Stack<Integer> pushStack;
        private Stack<Integer> popStack;
    
    
        public Stack2Queue() {
            this.pushStack = new Stack<>();
            this.popStack = new Stack<>();
        }
    
    
        /**
         * add操作
         *
         * @param data
         */
        public void add(Integer data) {
            pushStack.push(data);
        }
    
    
        /**
         * peek操作
         *
         * @return 对头元素
         */
        public Integer peek() {
            if (pushStack.isEmpty() && popStack.isEmpty()) {
                throw new RuntimeException("队列内没有元素");
            } else if (popStack.isEmpty()) {
                while (!pushStack.isEmpty()) {
                    popStack.push(pushStack.pop());
                }
            }
    
            return popStack.peek();
        }
    
    
        /**
         * poll操作
         *
         * @return
         */
        public Integer poll() {
            if (pushStack.isEmpty() && popStack.isEmpty()) {
                throw new RuntimeException("队列内没有元素");
            } else if (popStack.isEmpty()) {
                while (!pushStack.isEmpty()) {
                    popStack.push(pushStack.pop());
                }
            }
    
            return popStack.pop();
        }
    
    
        public static void main(String[] args) {
            Stack2Queue stack2Queue = new Stack2Queue();
            stack2Queue.add(1);
            stack2Queue.add(2);
            stack2Queue.add(3);
            stack2Queue.add(4);
            stack2Queue.add(5);
            System.out.println(stack2Queue.peek());
            System.out.println(stack2Queue.poll());
        }
    
    
    }

## 3.2 测试 ##

1
    1

[https_github.com_1956025812_algorithm]: https://github.com/1956025812/algorithm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjYx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200112204402155.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MjA2MjYx,size_16,color_FFFFFF,t_70