美文网首页
两个栈实现一个堆

两个栈实现一个堆

作者: 响响月月 | 来源:发表于2018-10-18 10:16 被阅读0次

    终极版

    1. 入栈push:push到stack1中,如果满了,报错。
    2. 出栈pop: 若stack1,stack2都空,报错;
      若stack2不为空,从stack2中pop一个;
      若stack2空,将stack1倒入stack2,将最后一个pop出来。

    图示

    Java代码实现

    class StackQueue {
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();
            public void push(int item) {
                stack1.push(item);
            }
            public Integer pop() throws Exception{
                if (stack1.empty() && stack2.empty()) {
                    System.out.println("empty");
                    throw new Exception();
                }
                if (stack2.empty()) {
                    while (stack1.size() > 1) {
                        stack2.push(stack1.pop());
                    }
                    return stack1.pop();
                } else {
                    return stack2.pop();
                }
            }
        }
    
    + push 1, 2, 3
    stack1=[1, 2, 3], stack2=[]
    - pop: 1
    stack1=[1], stack2=[3, 2]  //stack1倒入stack1, 把stack1最后一个pop
    stack1=[], stack2=[3, 2]
    + push 4, 5
    stack1=[4, 5], stack2=[3, 2]
    - pop: 2
    stack1=[4, 5], stack2=[3]
    - pop: 3
    stack1=[4, 5], stack2=[]
    - pop: 4
    stack1=[4], stack2=[5]  //stack1倒入stack1, 把stack1最后一个pop
    stack1=[], stack2=[5]
    - pop: 5
    stack1=[], stack2=[]
    - pop: empty
    

    相关文章

      网友评论

          本文标题:两个栈实现一个堆

          本文链接:https://www.haomeiwen.com/subject/nfdjzftx.html