队列的简单学习

<code>/**</code>

<code>     </code><code>* 1.在Java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。</code>

<code>     </code><code>* </code>

<code>     </code><code>* Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取</code>

<code>     </code><code>* 或移除的元素。他们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。</code>

<code>     </code><code>* 如果要使用前端而不移除该元素，使用element()或者peek()方法。</code>

<code>     </code><code>* 值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当初Queue来用。</code>

<code>     </code><code>*/</code>

<code>    </code><code>Queue&lt;String&gt; queue = </code><code>new</code> <code>LinkedList&lt;String&gt;();</code>

<code>    </code><code>queue.offer(</code><code>"1"</code><code>);</code>

<code>    </code><code>queue.offer(</code><code>"2"</code><code>);</code>

<code>    </code><code>queue.offer(</code><code>"3"</code><code>);</code>

<code>    </code><code>System.out.println(</code><code>"队列的大小："</code> <code>+ queue.size());</code>

<code>    </code><code>System.out.println(</code><code>"toString : "</code> <code>+ queue.toString());</code>

<code>    </code> 

<code>    </code><code>//循环队列</code>

<code>    </code><code>for</code><code>(String str : queue) {</code>

<code>        </code><code>System.out.println(</code><code>"队列内容："</code> <code>+ str);</code>

<code>    </code><code>}</code>

<code>    </code><code>boolean</code> <code>offerResult = queue.offer(</code><code>"4"</code><code>);</code>

<code>    </code><code>System.out.println(</code><code>"插入队列的结果："</code> <code>+ offerResult + </code><code>" ,队列的大小："</code> <code>+ queue.size());</code>

<code>    </code><code>String e = queue.poll();</code>

<code>    </code><code>System.out.println(</code><code>"返回删除的头元素 ： "</code> <code>+ e);</code>

<code>    </code><code>e = queue.peek();</code>

<code>    </code><code>System.out.println(</code><code>"返回头元素，不删除头元素 ： "</code> <code>+ e);</code>

<code>    </code><code>e = queue.element();</code>

<code>    </code><code>System.out.println(</code><code>"是否为空队列  ： "</code> <code>+ queue.isEmpty());</code>

<code>    </code><code>System.out.println(</code><code>"队列的大小 ： "</code> <code>+ queue.size());</code>

<code>    </code><code>System.out.println(</code><code>"是否包含相关的元素："</code> <code>+ queue.contains(</code><code>"1"</code><code>));</code>

<code>    </code><code>System.out.println(</code><code>"是否包含相关的元素："</code> <code>+ queue.contains(</code><code>"2"</code><code>));</code>

<code>    </code><code>queue.clear();</code>

2.2014-08-10-如果用2两个栈实现一个队列

<code>package</code> <code>com.hanchao.test0810;</code>

<code>import</code> <code>java.util.Stack;</code>

<code>/***********************</code>

<code> </code><code>* 2个栈实现一个队列方法1</code>

<code> </code><code>* @author：han    </code>

<code> </code><code>* @version：1.0        </code>

<code> </code><code>* @created：2014-8-10    </code>

<code> </code><code>***********************</code>

<code> </code><code>*/</code>

<code>public</code> <code>class</code> <code>MyQueue1 {</code>

<code>    </code><code>/**</code>

<code>     </code><code>* 思路： 假设有2个栈s1,s2</code>

<code>     </code><code>* ① 入队时，将元素压入s1</code>

<code>     </code><code>* ② 出队时，将s1的元素逐个“倒入”(弹出并压入)s2,</code>

<code>     </code><code>*      将s2的顶元素弹出作为出队元素，</code>

<code>     </code><code>*   之后再将s2剩下的元素逐个“倒回”s1。</code>

<code>    </code><code>private</code> <code>Stack&lt;String&gt; s1 = </code><code>new</code> <code>Stack&lt;String&gt;();</code>

<code>    </code><code>private</code> <code>Stack&lt;String&gt; s2 = </code><code>new</code> <code>Stack&lt;String&gt;();</code>

<code>     </code><code>* 入队操作</code>

<code>     </code><code>* *******************</code>

<code>     </code><code>* @param str</code>

<code>     </code><code>* @return</code>

<code>     </code><code>* @author：wind</code>

<code>     </code><code>* 2014-8-10 上午11:26:16</code>

<code>    </code><code>public</code> <code>boolean</code> <code>offer(String str) {</code>

<code>        </code><code>if</code><code>(str != </code><code>null</code><code>) {</code>

<code>            </code><code>s1.push(str);</code>

<code>            </code><code>return</code> <code>true</code><code>;</code>

<code>        </code><code>} </code><code>else</code> <code>{</code>

<code>            </code><code>return</code> <code>false</code><code>;</code>

<code>        </code><code>}</code>

<code>     </code><code>* 出队操作</code>

<code>     </code><code>* 2014-8-10 上午11:27:50</code>

<code>    </code><code>public</code> <code>String poll() {</code>

<code>        </code><code>while</code><code>(!s1.empty()) {</code>

<code>            </code><code>//s1不为空,把s1的元素倒入s2</code>

<code>            </code><code>s2.push(s1.pop());</code>

<code>        </code><code>//取出s2栈顶的元素</code>

<code>        </code><code>String str = s2.pop();</code>

<code>        </code><code>//把s2的元素“倒回”s1</code>

<code>        </code><code>while</code><code>(!s2.empty()) {</code>

<code>            </code><code>s1.push(s2.pop());</code>

<code>        </code><code>return</code> <code>str;</code>

<code>     </code><code>* 如果s1,s2同时为空，没有意义</code>

<code>     </code><code>* 2014-8-10 上午11:31:24</code>

<code>    </code><code>public</code> <code>boolean</code> <code>empty() {</code>

<code>        </code><code>if</code><code>(s1.empty() &amp;&amp; s2.empty()) {</code>

<code>        </code><code>return</code> <code>false</code><code>;</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) {</code>

<code>        </code><code>MyQueue1 queue = </code><code>new</code> <code>MyQueue1();</code>

<code>        </code><code>queue.offer(</code><code>"aa"</code><code>);</code>

<code>        </code><code>queue.offer(</code><code>"bb"</code><code>);</code>

<code>        </code><code>queue.offer(</code><code>"cc"</code><code>);</code>

<code>        </code><code>queue.offer(</code><code>"dd"</code><code>);</code>

<code>        </code> 

<code>        </code><code>while</code><code>(!queue.empty()) {</code>

<code>            </code><code>System.out.println(queue.poll());</code>

<code>}</code>

方法2：

<code>package</code> <code>com.hanchao.test0809;</code>

<code> </code><code>* 用两个栈实现一个队列2</code>

<code> </code><code>* @created：2014-8-9    </code>

<code>public</code> <code>class</code> <code>MyQueue {</code>

<code>     </code><code>* 思路：：</code>

<code>     </code><code>* ①入队时，要判断s2是否为空，为空表示没有出队元素，元素都在s1，可以直接入队</code>

<code>     </code><code>* 如果s2不为空，我们要把s2中的元素"倒回"s1，再压入入队元素。  </code>

<code>     </code><code>* ②出队时，要判断s2是否为空，不为空直接弹出s2的顶元素并出队。</code>

<code>     </code><code>*  如果s2为空，判断s1是否为空，不为空把s1“倒入”s2，再把s2的顶元素取出即可。</code>

<code>     </code><code>*       </code>

<code>     </code><code>* 2014-8-10 上午10:04:23</code>

<code>        </code><code>if</code><code>(s2.isEmpty()) {</code>

<code>            </code><code>//如果s2为空，则可以直接向s1添加元素</code>

<code>            </code><code>//如果s2不为空，我们要将s2的元素重新倒入s1中</code>

<code>            </code><code>while</code><code>(!s2.isEmpty()) {</code>

<code>                </code><code>s1.push(s2.pop());</code>

<code>            </code><code>}</code>

<code>            </code><code>//再把新元素加入s1中</code>

<code>        </code><code>return</code> <code>true</code><code>;</code>

<code>     </code><code>* 2014-8-10 上午10:11:29</code>

<code>        </code><code>if</code><code>(!s2.empty()) {</code>

<code>            </code><code>//如果s2不为空，可以直接出队</code>

<code>            </code><code>return</code> <code>s2.pop();</code>

<code>            </code><code>//如果s2为空，要判断s1是否为空，s1不为空时，要把s1的元素“倒入”s2中</code>

<code>            </code><code>/*while(!s1.empty()) {</code>

<code>                </code><code>s2.push(s1.pop());</code>

<code>            </code><code>return s2.pop();*/</code>

<code>            </code> 

<code>            </code><code>/**</code>

<code>             </code><code>* 此处优化一下：在出队时，将s1的元素“倒入”s2时，</code>

<code>             </code><code>* 原在s1栈底的元素，不用“倒入”s2(即只“倒”s1.count() - 1)</code>

<code>             </code><code>* 可以直接弹出作为出队元素返回。这样可以减少一次压栈的操作</code>

<code>             </code><code>*/</code>

<code>            </code><code>int size = s1.size();</code>

<code>            </code><code>if(size &gt; 0) {</code>

<code>                </code><code>for(int i = 0; i &lt; size - 1; i++) {</code>

<code>                    </code><code>s2.push(s1.pop());</code>

<code>                </code><code>}</code>

<code>            </code><code>return s1.pop();</code>

<code>     </code><code>* 如果s1,s2都为空，没有必要出队和入队</code>

<code>     </code><code>* 2014-8-10 上午10:20:11</code>

<code>        </code><code>MyQueue queue = </code><code>new</code> <code>MyQueue();</code>

方法3:

<code> </code><code>* 两个栈实现一个队列：new</code>

<code>public</code> <code>class</code> <code>MyQueueNew {</code>

<code>     </code><code>* 思路：s1是入栈的，s2是出栈的。</code>

<code>     </code><code>*        入队列时：直接压入s1即可。</code>

<code>     </code><code>*        出队列时：如果s2不为空，把s2中的栈顶元素直接弹出；</code>

<code>     </code><code>*        否则，把s1的所有元素全部弹出压入s2中，再把弹出的s2的栈顶元素</code>

<code>     </code><code>* 2014-8-10 上午11:15:12</code>

<code>        </code><code>s1.push(str);</code>

<code>     </code><code>* 2014-8-10 上午11:16:18</code>

<code>        </code><code>/*if(!s2.empty()) {</code>

<code>            </code><code>//如果s2不为空，直接出队</code>

<code>            </code><code>return s2.pop();</code>

<code>        </code><code>} else {</code>

<code>            </code><code>//如果s2为空，要把s1的元素全部倒入s2中</code>

<code>            </code><code>while(!s1.empty()) {</code>

<code>        </code><code>}*/</code>

<code>        </code><code>/**</code>

<code>         </code><code>* 优化一下：</code>

<code>         </code><code>*/</code>

<code>        </code><code>if(s2.empty()) {</code>

<code>        </code><code>return s2.pop();</code>

<code>     </code><code>* 如果s1和s2都为空，没有出队的意义</code>

<code>     </code><code>* 2014-8-10 上午11:19:51</code>

<code>        </code><code>MyQueueNew queue = </code><code>new</code> <code>MyQueueNew();</code>

<code>        </code><code>queue.offer(</code><code>"cc1"</code><code>);</code>

二：用2个队列实现一个栈

<code>import</code> <code>java.util.LinkedList;</code>

<code>import</code> <code>java.util.Queue;</code>

<code> </code><code>* 用2个队列实现一个栈1</code>

<code>public</code> <code>class</code> <code>MyStack1 {</code>

<code>     </code><code>* 思路：队列q1,队列q2</code>

<code>     </code><code>*        q1是专职进出栈的，q2只是一个临时中转站</code>

<code>     </code><code>*  </code>

<code>     </code><code>*  入栈时：直接入队列q1即可</code>

<code>     </code><code>*  出栈时：把q1的除最后一个元素外全部其他元素转移到队列q2中，</code>

<code>     </code><code>*       然后把刚才剩下q1中的那个元素出队列。</code>

<code>     </code><code>*       </code>

<code>     </code><code>*       之后把q2的全部元素转移回q1中。</code>

<code>    </code><code>private</code> <code>Queue&lt;String&gt; q1 = </code><code>new</code> <code>LinkedList&lt;String&gt;();</code>

<code>    </code><code>private</code> <code>Queue&lt;String&gt; q2 = </code><code>new</code> <code>LinkedList&lt;String&gt;();</code>

<code>     </code><code>* 入栈操作</code>

<code>     </code><code>* 2014-8-10 下午12:08:49</code>

<code>    </code><code>public</code> <code>String push(String str) {</code>

<code>        </code><code>q1.offer(str);</code>

<code>     </code><code>* 出栈操作</code>

<code>     </code><code>* 2014-8-10 下午12:09:53</code>

<code>    </code><code>public</code> <code>String pop() {</code>

<code>        </code><code>if</code><code>(!q1.isEmpty()) {</code>

<code>            </code><code>//如果q1不为空,把q1的前n-1个元素倒入q2</code>

<code>            </code><code>while</code><code>(q1.size() &gt; </code><code>1</code><code>) {</code>

<code>                </code><code>q2.offer(q1.poll());</code>

<code>            </code><code>//取得q1的最后一个元素</code>

<code>            </code><code>String str = q1.poll();</code>

<code>            </code><code>//把q2的元素重新倒入q1</code>

<code>            </code><code>while</code><code>(q2.size() &gt; </code><code>0</code><code>) {</code>

<code>                </code><code>q1.offer(q2.poll());</code>

<code>            </code><code>return</code> <code>str;</code>

<code>        </code><code>return</code> <code>null</code><code>;</code>

<code>     </code><code>* 如果q1和q2都为空的话，没有意义</code>

<code>     </code><code>* 2014-8-10 下午12:14:29</code>

<code>        </code><code>if</code><code>(q1.isEmpty() &amp;&amp; q2.isEmpty()) {</code>

<code>        </code><code>MyStack1 stack = </code><code>new</code> <code>MyStack1();</code>

<code>        </code><code>stack.push(</code><code>"aa"</code><code>); </code><code>//栈底</code>

<code>        </code><code>stack.push(</code><code>"bb"</code><code>);</code>

<code>        </code><code>stack.push(</code><code>"cc"</code><code>); </code><code>//栈顶</code>

<code>        </code><code>while</code><code>(!stack.empty()) {</code>

<code>            </code><code>System.out.println(stack.pop());</code>

<code> </code><code>* 2个队列实现一个栈：2</code>

<code>public</code> <code>class</code> <code>MyStack2 {</code>

<code>     </code><code>* 思路：队列q1,q2都可以作为进出栈的队列</code>

<code>     </code><code>* 对于两个队列实现一个栈，如果我要把刚放的东西再取出来，</code>

<code>     </code><code>* 对于队列来说，只能是把之前的东西都先出队，</code>

<code>     </code><code>* 才能把刚才的放的东西出队。</code>

<code>     </code><code>* 故：那就把之前的那些数据先出队列到队列2中。</code>

<code>     </code><code>*       两个队列来回交换数据即可。</code>

<code>     </code><code>* 2014-8-10 下午12:38:33</code>

<code>        </code><code>if</code><code>(q2.isEmpty()) {</code>

<code>            </code><code>//如果q2为空，把元素压入q1中</code>

<code>            </code><code>q1.offer(str);</code>

<code>        </code><code>} </code><code>else</code> <code>if</code><code>(q1.isEmpty()) {</code>

<code>            </code><code>//如果q1为空，把元素压入q2中</code>

<code>            </code><code>q2.offer(str);</code>

<code>     </code><code>* 2014-8-10 下午12:39:05</code>

<code>            </code><code>//如果q1不为空，从q1出最后一个元素，并把其他的元素移入q2中</code>

<code>            </code><code>return</code> <code>q1.poll();</code>

<code>        </code><code>} </code><code>else</code> <code>if</code><code>(!q2.isEmpty()) {</code>

<code>            </code><code>//如果q2不为空，从q2出最后一个元素，并把其他的元素移入q1中</code>

<code>            </code><code>while</code><code>(q2.size() &gt; </code><code>1</code><code>) {</code>

<code>            </code><code>return</code> <code>q2.poll();</code>

<code>     </code><code>* 如果队列q1,q2都为空，没有必要操作</code>

<code>     </code><code>* 2014-8-10 下午12:45:37</code>

<code>        </code><code>MyStack2 stack = </code><code>new</code> <code>MyStack2();</code>

<code>        </code><code>stack.push(</code><code>"aa"</code><code>);</code>

<code>        </code><code>stack.push(</code><code>"cc"</code><code>);</code>

<code>        </code><code>stack.push(</code><code>"dd"</code><code>);</code>

<code></code>

     本文转自韩立伟 51CTO博客，原文链接：http://blog.51cto.com/hanchaohan/1426863，如需转载请自行联系原作者