Implement the following operations of a queue using stacks.

push(x) — Push element x to the back of queue.

pop() — Removes the element from in front of queue.

peek() — Get the front element.

empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.

Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

利用栈来实现队列的功能.

实现

java

因为 java 的 Stack 集成了 Vector,利用现有的 api 即可实现基本的队列功能.

class  {

   private Stack<Integer> stack;

   
   public () {
     stack = new Stack<>();
   }

   /** Push element x to the back of queue. */
   public void push(int x) {
     stack.add(x);
   }

   /** Removes the element from in front of queue and returns that element. */
   public int pop() {
      if (!empty()){
        return stack.remove(0);
      }
      return -1;
   }

   /** Get the front element. */
   public int peek() {
    return stack.firstElement();
   }

   /** Returns whether the queue is empty. */
   public boolean empty() {
     return stack.isEmpty();
   }
 }

java

利用两个栈来处理入队和出队的问题.

class  {

  Stack<Integer> input = new Stack();
  Stack<Integer> output = new Stack();
  public void push(int x) {
    input.push(x);
  }

  public int pop() {
    peek();
    return output.pop();
  }

  public int peek() {
    if (output.empty()){
      while (!input.empty()){
        output.push(input.pop());
      }
    }
    return output.peek();
  }

  public boolean empty() {
    return input.empty() && output.empty();
  }
}

参考

implement-queue-using-stacks

232. implement queue using stacks 实现参考

实现

参考

近期文章

近期评论

标签

热门

文章归档

分类目录

功能