隊列的簡單學習

<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，如需轉載請自行聯系原作者