Java 棧和隊(duì)列的相互轉(zhuǎn)換詳解

更新時間：2022年02月14日 11:43:47 作者：Word碼鴨

棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯壿嬯P(guān)系為 "一對一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解

用棧實(shí)現(xiàn)隊(duì)列—力扣232題

題目要求：僅使用兩個棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作

使用雙棧來實(shí)現(xiàn)隊(duì)列，我們就可以讓一個棧儲存具體元素，另一個棧做輔助?

上圖可以看到，新元素進(jìn)棧時，要確保該棧為空。進(jìn)入棧的元素按順序存到輔助棧中，等新元素進(jìn)入棧之后，再將輔助棧中的元素按順序出到該棧中。這樣操作之后，棧中元素存放的順序就和隊(duì)列的一樣啦

代碼實(shí)現(xiàn)：

 
//雙棧模擬隊(duì)列
public class MyQueue{
    //實(shí)際存儲元素的棧
    private Stack<Integer> s1 = new Stack<>();
    //輔助棧
    private Stack<Integer> s2 = new Stack<>();
 
    public MyQueue() {
 
    }
 
    //將元素 x 推到隊(duì)列的末尾
    public void push(int x) {
        if (s1.empty()){//棧為空，直接放入x
            s1.push(x);
        }else {
            //此時不為空
            //先把s1所有元素彈出放入s2
            while (!s1.empty()){
                s2.push(s1.pop());//s2放入的值就是s2彈出的值
                //以下兩句和上一句相同
//                int val = s1.pop();
//                s2.push(val);
            }
            //將新元素直接放入s1，此時新元素就處在s1的棧頂
            s1.push(x);
            //再次將s2的所有值依次彈出放入s1
            while (!s2.empty()){
                s1.push(s2.pop());
            }
        }
 
    }
 
    //從隊(duì)列的開頭移除并返回元素
    public int pop() {
       return s1.pop();
    }
 
    //返回隊(duì)列開頭的元素
    public int peek() {
        return s1.peek();
    }
 
    //判斷隊(duì)列是否為空
    public boolean empty() {
        return s1.empty();
    }
}

用隊(duì)列實(shí)現(xiàn)?！?25題?

題目要求：僅使用兩個隊(duì)列實(shí)現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作

1. 雙隊(duì)列實(shí)現(xiàn)棧

使用雙隊(duì)列實(shí)現(xiàn)棧， q1是存儲元素的隊(duì)列，保證q2添加元素之后永遠(yuǎn)為空隊(duì)列（新元素直接入q2），保證新元素處在隊(duì)首。這樣的話，新元素入隊(duì)之后，另外一個隊(duì)列的元素依次出隊(duì)然后入隊(duì)，這樣就實(shí)現(xiàn)了一個棧。

代碼實(shí)現(xiàn)：

public class MyStack {
    //q1是存儲元素的隊(duì)列
    private Queue<Integer> q1 = new LinkedList<>();
    //q2是輔助隊(duì)列
    //添加元素后保證q2永遠(yuǎn)為空
    private Queue<Integer> q2 = new LinkedList<>();
    public MyStack () {
 
    }
 
    //將元素 x 壓入棧頂
    public void push(int x) {
        //新入隊(duì)元素直接入q2，成為q2隊(duì)首
        q2.offer(x);
        //將q1中的所有元素依次出隊(duì)，入q2
        while (!q1.isEmpty()){
            q2.offer(q1.poll());
        }
 
        //q1為空，q2為存儲元素的隊(duì)列，互換引用指向
        //互換之后，q1任然是存儲元素的隊(duì)列，q2為空
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
 
    // 移除并返回棧頂元素
    public int pop() {
        return q1.poll();
    }
 
    //返回棧頂元素
    public int top() {
        return q1.peek();
    }
 
    //判斷棧是否為空
    public boolean empty() {
        return q1.isEmpty();
    }
}

2.一個隊(duì)列實(shí)現(xiàn)棧

先將元素入隊(duì)，再將之前的元素依次出隊(duì)再入隊(duì)即可！也就是說，保證新元素在隊(duì)首

代碼實(shí)現(xiàn)：

public class MyStack {
    private Queue<Integer> queue = new LinkedList<>();
    public MyStack() {
    }
 
    public void push(int x) {
        //記錄之前元素的個數(shù)
        int size = queue.size();
        //將新元素入隊(duì)
        queue.offer(x);
        //將之前的元素依次出隊(duì)再入隊(duì),新元素就在隊(duì)首位置
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
 
    }
 
    public int pop() {
        return queue.poll();
    }
 
    public int top() {
        return queue.peek();
    }
 
    public boolean empty() {
        return queue.isEmpty();
    }
}