寫在前面的聲明:
1,棧是先入后出的數(shù)據(jù)結(jié)構(gòu)(就像將書裝入箱子，壓箱底的書總是要最后才能取出來)
2,隊(duì)列是先入先出的數(shù)據(jù)結(jié)構(gòu)(就像排隊(duì)買票，先排隊(duì)的先買票，后來的后買)

小白版

• 初始化兩個(gè)棧S1和S2。
• S1作為元素的存儲(chǔ)空間，S2作為數(shù)據(jù)的臨時(shí)緩沖區(qū)
• 入隊(duì)的時(shí)候，將數(shù)據(jù)壓入棧S1中
• 出隊(duì)的時(shí)候，將S1中的元素依次出棧，并且壓入棧S2中，然后將S2中的棧頂元素出棧。
• 出隊(duì)之后，將S2中的數(shù)據(jù)元素倒回到棧S1中

Paste_Image.png

升級(jí)版

• 入隊(duì)時(shí)，先判斷S1是否為空，如不為空，說明所有元素都在S1，此時(shí)將入隊(duì)元素直接壓入S1；如為空，要將S2的元素逐個(gè)“倒回”S1，再壓入入隊(duì)元素。

• 出隊(duì)時(shí)，先判斷S2是否為空，如不為空，直接彈出S2的頂元素并出隊(duì)；如為空，將S1的元素逐個(gè)“倒入”S2，把最后一個(gè)元素彈出并出隊(duì)。

這種升級(jí)版可以在每次出隊(duì)之后不用將棧S2中的元素倒回到棧S1中，對(duì)于頻繁的出隊(duì)操作效率更高。

大師版

• 入隊(duì)時(shí)，將元素壓入s1。
• 出隊(duì)時(shí)，判斷s2是否為空，如不為空，則直接彈出頂元素；如為空，則將s1的元素逐個(gè)“倒入”s2，把最后一個(gè)元素彈出并出隊(duì)。

這個(gè)大師版，避免了反復(fù)“倒”棧，僅在需要時(shí)才“倒”一次

java實(shí)現(xiàn)如下

import java.util.Stack;
 
public class StackToQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        //入對(duì)的時(shí)候?qū)?shù)據(jù)元素壓入棧S1中
        stack1.push(node);
    }
     
    public int pop() {
        //如果S1不為空，將S1出棧的元素一次入棧到S2中
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        //將S2的棧頂元素出棧，即出隊(duì)。
        int first=stack2.pop();
        //如果S2不為空，將S2中的元素出棧，然后入棧到S1中
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return first;
    }
}