|
首先需要使用上篇文章（用數(shù)組實(shí)現(xiàn)棧和隊(duì)列）中的棧和隊(duì)列兩個類 1.棧實(shí)現(xiàn)隊(duì)列：思路是有兩個棧，一個用來放數(shù)據(jù)（數(shù)據(jù)棧），一個用來輔助（輔助棧）。數(shù)據(jù)添加時，會依次壓人棧，取數(shù)據(jù)時肯定會取棧頂元素，但我們想模擬隊(duì)列的先進(jìn)先出，所以就得取棧底元素，那么輔助棧就派上用場了，把數(shù)據(jù)棧的元素依次彈出到輔助棧，但保留最后一個元素，最后數(shù)據(jù)棧就剩下了最后一個元素，直接把元素返回，這時數(shù)據(jù)棧已經(jīng)沒有了數(shù)據(jù)。最后呢，把輔助棧的元素依次壓人數(shù)據(jù)棧，這樣，我們成功取到了棧底元素。 代碼如下：  package com.sxt.test.java; public class Stack2Queue { /** * 用棧的入棧和出棧 * 來實(shí)現(xiàn)隊(duì)列的入隊(duì)和出隊(duì) * stack1是入棧的，stack2是出棧的。 入隊(duì)列：直接壓入stack1即可 出隊(duì)列：如果stack2不為空，把stack2中的棧頂元素直接彈出； 否則，把stack1的所有元素全部彈出壓入stack2中，再彈出stack2的棧頂元素 * */ Stack stack1 = new Stack(); Stack stack2 = new Stack(); public void add(Object o) { stack1.push(o); } public Object poll() { Object o = null; if(stack2.length()==0) { //把stack1的數(shù)據(jù)放入stack2，留下最后一個數(shù)據(jù) while(stack1.length()>1) { stack2.push(stack1.pop()); } if(stack1.length()==1) { //把stack1的留下的那個數(shù)據(jù)返回出去 o = stack1.pop(); } }else { o = stack2.pop(); } return o; } public int length() { return stack1.length()+stack2.length(); } }
2.隊(duì)列實(shí)現(xiàn)棧 思路同上：有數(shù)據(jù)隊(duì)列和輔助隊(duì)列，模擬棧的先進(jìn)后出，隊(duì)列是隊(duì)尾進(jìn)隊(duì)頭出，也就是說每次取值要取隊(duì)列的隊(duì)尾元素，數(shù)據(jù)隊(duì)列出隊(duì)到輔助隊(duì)列，留下最后一個元素返回，輔助隊(duì)列再把元素出隊(duì)到數(shù)據(jù)隊(duì)列 代碼如下： package com.sxt.test.java; public class Queue2Stack { /** * 用隊(duì)列的入隊(duì)和出隊(duì) * 來實(shí)現(xiàn)棧的入棧和出棧 * */ Queue queue1 = new Queue();//主要存放數(shù)據(jù) Queue queue2 = new Queue();//輔助 public void push(Object o) { queue1.add(o); } public Object pop() { Object o = null; while(queue1.length()>1) { queue2.add(queue1.poll()); } if(queue1.length()==1) { o = queue1.poll(); while(queue2.length()>0) { queue1.add(queue2.poll()); } } return o; } public int length() { return queue1.length(); } }
3.測試類 /** * 用兩個棧實(shí)現(xiàn)隊(duì)列 * */ Stack2Queue stack2Queue = new Stack2Queue(); stack2Queue.add("a"); stack2Queue.add("b"); stack2Queue.add("c"); stack2Queue.add("d"); stack2Queue.add("e"); while(stack2Queue.length()>0) { System.out.println(stack2Queue.poll()); } /** * 用兩個隊(duì)列實(shí)現(xiàn)棧 * */ Queue2Stack queue2Stack = new Queue2Stack(); queue2Stack.push("a"); queue2Stack.push("c"); queue2Stack.pop(); queue2Stack.push("d"); queue2Stack.push("e"); queue2Stack.push("f"); queue2Stack.push("g"); queue2Stack.push("h"); while(queue2Stack.length()>0) { System.out.println(queue2Stack.pop()); }
|
|
|
