兩個棧實現佇列 兩個佇列實現棧—-java

                                           兩個棧實現佇列 兩個佇列實現棧—-java

一.兩個棧實現一個佇列

思路:所有元素進stack1,然後全部出stack1並進入stack2.實現佇列的先進先出即:若stack2非空,我們需要的恰好再棧頂,出棧;若要給佇列新增元素,即先進sack1,要出隊時,若stack2不為空就出棧,為空時就把stack1全部進棧到stack2

package com.sheepmu;
import java.util.Stack;
public class StacksToQueue 
{
Stack<Integer> stack1=new Stack<Integer>() ;
Stack<Integer> stack2=new Stack<Integer>();
public void addToTail(int x)//新增元素到隊尾   --進隊---
{
stack1.push(x);
}
public int deleteHead()//刪除對首      --出隊---    不需是隊不為空才能刪除呀~~~~
{
if( pSize()!=0)//佇列不為空
{
if(stack2.isEmpty())//若stack2為空,則把stack1全部加入stack2
stack1ToStack2(); 
return  stack2.pop();
}
else
{
System.out.println("佇列已經為空,不能執行從隊頭出隊");
return -1;
}
}
public void stack1ToStack2()//把stack1全部放入stack2
{
while(!stack1.isEmpty()) 
stack2.push(stack1.pop());
}
public int pSize()//佇列size()
{
return  stack1.size() stack2.size();//兩個都為空佇列才是空
}
public static void main(String[] args)
{
StacksToQueue  q=new StacksToQueue ();
q.addToTail(1);
q.addToTail(2);
q.addToTail(3);
q.addToTail(4);
System.out.println(q.deleteHead());
System.out.println(q.deleteHead());
q.addToTail(5);
System.out.println(q.deleteHead());
System.out.println(q.deleteHead());
System.out.println(q.deleteHead());
System.out.println(q.deleteHead());
}
}

輸出:

1
2
3
4
5
佇列已經為空,不能執行從隊頭出隊
-1

二.兩個佇列實現一個棧

思路:所有元素進入q1,因為我們的目的是棧,也就是最先出c,兒隊是從隊頭開始出,所有先把ab出q1併入q2,此時目標c跑到了隊頭,出q1。此時q1已經為空,下一個要出的是b,把a從q2出隊並進q1,此時目標b在q2隊頭,出隊……..

即:把非空佇列的n-1個壓人空對列,剩的第n個出隊…即總有一個佇列為空。

ps:圖片原創於劍橋offer,來自網路

package com.sheepmu;
import java.util.LinkedList;
public class QueuesToStack 
{
LinkedList<Integer> queue1=new LinkedList<Integer>();
LinkedList<Integer> queue2=new LinkedList<Integer>();
public void push(int value)//入棧
{
queue1.addLast(value);
}
public int pop()//出棧     必須是非空的棧才能出棧啊
{
if(sSize()!=0)//棧不為空
{
//移動一個隊的n-1個到另一箇中
if(!queue1.isEmpty())//q1 空
{
putN_1ToAnthor();
return queue1.removeFirst();
}
else  //q2 空
{
putN_1ToAnthor();
return queue2.removeFirst();
}		 
}
else
{
System.out.println("棧已經為空啦,不能出棧");
return -1;
}
}
public int sSize()
{
return queue1.size() queue2.size();
}
public void putN_1ToAnthor()//從非空中出隊n-1個到另一個佇列   因為佇列總是一空一非空
{
if(!queue1.isEmpty())
{
while(queue1.size()>1)
{
queue2.addLast(queue1.removeFirst());
}
}
else if(!queue2.isEmpty())
{
while(queue2.size()>1)
{
queue1.addLast(queue2.removeFirst());
}
}
}
public static void main(String[] args)
{
QueuesToStack stack=new QueuesToStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop());
System.out.println(stack.pop());
stack.push(5);
stack.push(6);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}

輸出:

4
3
6
5
2
1
棧已經為空啦,不能出棧
-1