反转队列


难度级别 易得奖学金
经常问 ol石 Coursera 德里韦里 事实集 GreyOrange 百会
拉森和图布罗 队列

在反转队列问题中,我们给出了一个 队列,写一个 算法 反转队列。

例子

输入
队列= 10-> 8-> 4-> 23
输出
队列= 23-> 4-> 8-> 10

输入
队列= 11-> 98-> 31-> 42-> 73-> 6
输出
队列= 6-> 73-> 42-> 31-> 98-> 11

输入
队列= 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9
输出
队列= 9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1

反转队列算法

可以使用 ,

  1. 从队列中删除所有元素,然后将它们推入堆栈。
  2. 从堆栈中弹出所有元素,然后将它们推回队列。
  3. 队列得到尊敬,打印队列中的元素。

反转队列的说明

考虑一个例子,
队列= 10-> 8-> 4-> 23

步骤

逐一从队列中删除元素,并将其推入堆栈。
队列= 10-> 8-> 4-> 23且stack = null
迭代1
队列= 8-> 4-> 23且堆栈= 10
迭代2
队列= 4-> 23,堆栈= 8-> 10
迭代3
队列= 23和堆栈= 4-> 8-> 23
迭代4
队列= null和堆栈= 23-> 4-> 8-> 23

步骤

从堆栈中弹出所有元素,然后将它们推回队列。
队列=空和堆栈= 23-> 4-> 8-> 10
迭代1
队列= 23和堆栈= 4-> 8-> 10
迭代2
队列= 23-> 4,堆栈= 8-> 10
迭代3
队列= 23-> 4-> 8且堆栈= 10
迭代4
队列= 23-> 4-> 8-> 10且堆栈= null

队列被反转。 请参阅下图以进行澄清。

反转队列

反转队列的JAVA代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReversingAQueue {
    private static void reverseQueue(Queue<Integer> queue) {
        int n = queue.size();

        Stack<Integer> stack = new Stack<>();
        // Remove all the elements from queue and push them to stack
        for (int i = 0; i < n; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }

        // Pop out elements from the stack and push them back to queue
        for (int i = 0; i < n; i++) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Print the reversed queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(8);
        q1.add(4);
        q1.add(23);
        reverseQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(11);
        q2.add(98);
        q2.add(31);
        q2.add(42);
        q2.add(73);
        q2.add(6);
        reverseQueue(q2);
    }
}
23 4 8 10 
6 73 42 31 98 11

用于反转队列的C ++代码

#include<bits/stdc++.h> 
using namespace std;

void reverseQueue(queue<int> &queue) {
    int n = queue.size();
    
    stack<int> st;
    // Remove all the elements from queue and push them to stack
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from the stack and push them back to queue
    for (int i = 0; i < n; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Print the reversed queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    int k1 = 3;
    q1.push(10);
    q1.push(8);
    q1.push(4);
    q1.push(23);
    reverseQueue(q1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(11);
    q2.push(98);
    q2.push(31);
    q2.push(42);
    q2.push(73);
    q2.push(6);
    reverseQueue(q2);
}
23 4 8 10 
6 73 42 31 98 11

复杂度分析

时间复杂度= O(N)
空间复杂度= O(N) 
其中n是队列中的节点数。

參考資料