首页 > 代码库 > 如何用两个栈实现一个队列

如何用两个栈实现一个队列

     在数据结构中,我们都学习过队列和栈,我们知道栈的基本特征是后进先出,这个当然也很好理解,用一句歇后语给大家通俗得解释一下,就是: 砌墙的砖瓦——后来居上。很容易明白,就是后面来的反倒在最上面,当然你取的话,是不是得从最上面开始取呀,很容易明白的。再来说说队列,队列的特征是先进先出,就是说先来的先走,生活中的例子就是排队买票,这个大家都很熟悉了,就是先买到票的人先走,后买到票的人后走。

   接下来就进入我们今天的主题,即如何用栈来实现队列?

  在这里我们可以通过两个栈来操作。第一个栈中存放入队列的元素,第二栈中存放出队列的元素,在这里我们定义两个栈,命名为:stack1 stack2

  首先我们可以将入队列的元素放在栈stack1中,如果要出队列的话,就先执行 stack1.push(stack1.pop()) ,这句代码就可以将stack1中的所有元素全部挪到stack2中,并且在stack2中,从栈顶到栈顶恰好就是元素进入队列的顺序,然后执行出队列的操作,即将stack2中的栈顶元素执行 pop() 操作,这时出栈的元素恰好就是出队列的元素。

进行简单分析后,我就上代码了。

 1 package queue;
 2 
 3 import java.util.NoSuchElementException;
 4 import java.util.Stack;
 5 
 6 /**
 7  * 用两个栈来实现一个队列
 8  * @author liuxin
 9  *
10  * @param <E>
11  */
12 public class QueueWithTwoStacks<E> {
13     private Stack<E> stack1;    
14     private Stack<E> stack2;    
15 
16     public QueueWithTwoStacks() {
17         stack1 = new Stack<E>();
18         stack2 = new Stack<E>();
19     }
20 
21    
22     
23 
24     public boolean isEmpty() {
25         return stack1.isEmpty()&&stack2.isEmpty();
26     }
27 
28 
29     
30     public int size() {
31         return stack1.size()+stack2.size();   
32     }
33 
34 
35 
36     public void enQueue(E item) {
37         stack1.push(item);
38     }
39 
40     public E deQueue() {
41         if(stack1.isEmpty())
42         {
43             throw new NoSuchElementException("Queue is Empty!!");
44         }
45         
46         if(stack2.isEmpty())
47         {
48             while(!stack1.isEmpty())
49             {
50                 stack2.push(stack1.pop());
51             }
52         }
53         
54         return stack2.pop() ;
55     }
56 
57  }

这就是我关于用栈实现队列的一些理解,若有疑问,可以留言。

 

如何用两个栈实现一个队列