由两个栈组成的队列-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

由两个栈组成的队列

简介: <pre code_snippet_id="1552910" snippet_file_name="blog_20160109_1_31286" name="code" class="java">package stackAndQueue; import java.util.Stack; import org.junit.Test; /** * 由两个栈组成的队列:TwoStack
package stackAndQueue;

import java.util.Stack;

import org.junit.Test;

/**
 * 由两个栈组成的队列:TwoStackQueue【2】
 * 
 * 【编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek)】
 * 
 * 设计思路:栈-先进后出,队列-先进先出。用两个栈把顺序反过来。
 * 
 * stackPush只管进栈,stackPop只管出栈且【仅当】其为空时,将stackPush的元素【全部】转移到stackPop。
 * 
 * @author xiaofan
 */
public class TwoStackQueue {
    private Stack<Integer> stackPush;

    private Stack<Integer> stackPop;

    public TwoStackQueue() {
        this.stackPush = new Stack<Integer>();
        this.stackPop = new Stack<Integer>();
    }

    public void add(int e) {
        this.stackPush.push(e);
    }

    public int poll() {
        tranfer();
        return this.stackPop.pop();
    }

    public int peek() {
        tranfer();
        return this.stackPop.peek();
    }

    private void tranfer() {
        if (this.stackPop.empty()) {
            if (this.stackPush.isEmpty()) { // isEmpty是Stack继承的Vector的方法
                throw new RuntimeException("Your queue is empty.");
            }
            while (!this.stackPush.empty()) { // empty是Stack自带的方法
                this.stackPop.push(this.stackPush.pop());
            }
        }
    }

    /////// 测试方法//////
    @Test
    public void test() {
        TwoStackQueue queue = new TwoStackQueue();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(3);
        queue.add(4);
        System.out.println("peek:" + queue.peek());
        while (true) { // 未重写empty方法,只能这样遍历
            try {
                System.out.println(queue.poll());
            } catch (Exception e) {
                break;
            }
        }
        TwoStackQueue queue1 = new TwoStackQueue();
        queue1.peek(); // java.lang.RuntimeException: Your queue is empty.
    }
}


代码地址:https://github.com/zxiaofan/Algorithm/tree/master/src/stackAndQueue


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: