用队列实现栈

使用队列实现栈的下列操作：

    push(num) -- 元素 num 入栈     pop() -- 移除栈顶元素     top() -- 获取栈顶元素     empty() -- 返回栈是否为空

栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。 队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。

注意:     你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。     你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。     你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

第一种方法 package com.loo;

import java.util.Queue; import java.util.LinkedList;

public class QueueImplStack {     private Queue<Integer> q1 = null;     private Queue<Integer> q2 = null;     public static void main(String[] args) {         QueueImplStack q = new QueueImplStack();         System.out.println("1 isEmpty:" + q.isEmpty());         q.push(6);         System.out.println("2 isEmpty:" + q.isEmpty());         q.push(1);         System.out.println("3 isEmpty:" + q.isEmpty() + ",top:" + q.top());         q.push(19);         q.push(13);         q.push(18);         System.out.println("4 isEmpty:" + q.isEmpty() + ",top:" + q.top());         System.out.println("5 pop:" + q.pop());         System.out.println("6 isEmpty:" + q.isEmpty() + ",top:" + q.top());         q.push(11);         System.out.println("7 isEmpty:" + q.isEmpty() + ",top:" + q.top());     }

    public QueueImplStack() {         q1 = new LinkedList<Integer>();         q2 = new LinkedList<Integer>();     }     public void push(int num) { /*入栈操作时，首先将元素入队到 q2​，然后将 q1​ 的全部元素依次出队并入队到 q2​，此时 q2​ 的前端的元素即为新入栈的元素，再将 q1​ 和 q2​ 互换，则 q1​ 的元素即为栈内的元素，q1​ 的前端和后端分别对应栈顶和栈底。*/         q2.offer(num);         while (!q1.isEmpty()) {             q2.offer(q1.poll());         }         Queue<Integer> tmp = q1;         q1 = q2;         q2 = tmp;     }

    public int pop() {         return q1.poll();     }

    public int top() {         return q1.peek();     }

    public boolean isEmpty() {         return q1.isEmpty();     } }

第二种方法 package com.loo;

import java.util.Queue; import java.util.LinkedList;

public class QueueImplStack2 {     private Queue<Integer> q1 = null;     public static void main(String[] args) {         QueueImplStack2 q = new QueueImplStack2();         System.out.println("1 isEmpty:" + q.isEmpty());         q.push(6);         System.out.println("2 isEmpty:" + q.isEmpty());         q.push(1);         System.out.println("3 isEmpty:" + q.isEmpty() + ",top:" + q.top());         q.push(19);         q.push(13);         q.push(18);         System.out.println("4 isEmpty:" + q.isEmpty() + ",top:" + q.top());         System.out.println("5 pop:" + q.pop());         System.out.println("6 isEmpty:" + q.isEmpty() + ",top:" + q.top());         q.push(11);         System.out.println("7 isEmpty:" + q.isEmpty() + ",top:" + q.top());     }

    public QueueImplStack2() {         q1 = new LinkedList<Integer>();     } /* 入栈操作时，首先获得入栈前的元素个数 size，然后将元素入队到队列，再将队列中的前 size 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。 */     public void push(int num) {         int size = q1.size();         q1.offer(num);         for (int i=0;i<size;i++) {             q1.offer(q1.poll());         }     }

    public int pop() {         return q1.poll();     }

    public int top() {         return q1.peek();     }

    public boolean isEmpty() {         return q1.isEmpty();     } }