Java面试必知必会

「Java面试必会」两个栈如何实现一个队列

2019-01-03  本文已影响53人  花生无翼

面试中,算法题是无法回避的,问的太深似乎没必要,毕竟应聘的不是算法岗位,如果问到算法题了,那一般肯定会是常见的,你听过,但是又不是很熟悉的东西。我们要做的就是把不熟悉的东西搞熟悉了,不会的东西搞会了,做好充分的准备。

下面这个题就比较有意思了,考的是对数据结构的基本理解,看下怎么实现。两个栈如何实现一个队列?

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class QueueImplementByTwoStacks {

     private Stack<Integer> stack1;
     private Stack<Integer> stack2;

     QueueImplementByTwoStacks() {
           stack1 = new Stack<Integer>();
           stack2 = new Stack<Integer>();
     }

     public Integer poll() {
          Integer it = null;
           if (!stack2 .empty()) {
               it = stack2.pop();
          } else {
               while (!stack1 .empty()) {
                    it = stack1.pop();
                    stack2.push( it);
              }
               if (!stack2 .empty()) {
                    it = stack2.pop();
              }
          }
           return it ;
     }

     public Integer offer(int o ) {
           stack1.push( o);
           return o ;
     }

     public static void main(String[] args) {
          QueueImplementByTwoStacks queue = new QueueImplementByTwoStacks();
          List<Integer> list = new ArrayList<Integer>();
           queue.offer(1);
           queue.offer(2);
           queue.offer(3);
           list.add( queue.poll());
          System. out.println(list .toString());
     
           queue.offer(4);
           list.add( queue.poll());
          System. out.println(list .toString());
           queue.offer(5);
          
          System. out.println(list .toString());
           list.add( queue.poll());
           /*list.add(queue.poll());
          list.add(queue.poll());*/
          System. out.println(list .toString());
     }
}

上一篇下一篇

猜你喜欢

热点阅读