[名企面试知识点][Java]用两个栈实现队列
发布于 2017-03-07 13:12 1145 次浏览 0 赞 来自 笔试面试  

题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

题目分析

  用两个栈实现FIFO

  情况一:如果出栈时stack2为空,则直接把stack1全部出栈到stack2之后,返回stack2.pop()就可以得出 出栈结果。

  情况二:已经出栈过,stack2中有数据。stack1中也有数据,现在要出栈。就要先把stack1的全部数据出栈到stack2,然后再返回stack2.pop()的值就行。

  实现代码:

> 运行时间:27ms       占用内存:503k
import java.util.Stack;

public class Solution {
   Stack<Integer> stack1 = new Stack<Integer>();
   Stack<Integer> stack2 = new Stack<Integer>();

   public void push(int node) {
       stack1.push(node);
   }

   public int pop() {
       if(stack2.isEmpty()){
           while(!stack1.isEmpty()){
              stack2.push(stack1.pop());
           }
         }
         return stack2.pop();  
   }
}

 值得注意的是:

  isEmpty()是 stack父类vector中的方法,stack中判空的函数是 empty(),虽然都是判断当前集合的元素个数是否为0。但是isEmpty()是同步的方法,empty()不是线程同步的。并且用isEmpty()的时间效率更高!


添加回复
回到顶部