倒队-yiteyi-C++库

给出一个逆转队列Q的算法。只允许对队列执行以下标准操作。

null

排队（x）：在队列后面添加一个项目x。
dequeue（）：从队列前面移除项目。
empty（）：检查队列是否为空。

例如：

Input :  Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]Output : Q = [100, 90, 80, 70, 60, 50, 40, 30, 20, 10]Input : [1, 2, 3, 4, 5]Output : [5, 4, 3, 2, 1]

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法： 要反转队列，一种方法是将队列的元素存储在临时数据结构中，这样，如果我们在队列中重新插入元素，它们将以相反的顺序插入。因此，我们现在的任务是选择这样的数据结构，可以达到这个目的。根据这种方法，数据结构应该具有“后进先出”的属性，因为插入数据结构的最后一个元素实际上应该是反向队列的第一个元素。堆栈可以帮助解决这个问题。这将是一个分为两步的过程：

从队列中弹出元素并插入堆栈。（堆栈最上面的元素是队列的最后一个元素）
弹出堆栈中的元素以重新插入队列。（最后一个元素是要插入队列的第一个元素）

C++

                         // CPP program to reverse a Queue                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Utility function to print the queue                       
                         void                                     Print(queue<                                     int                                     >& Queue)                       
                         {                       
                                                 while                                     (!Queue.empty()) {                       
                                                 cout << Queue.front() <<                                     " "                                     ;                       
                                                 Queue.pop();                       
                                                 }                       
                         }                       
           
                         // Function to reverse the queue                       
                         void                                     reverseQueue(queue<                                     int                                     >& Queue)                       
                         {                       
                                                 stack<                                     int                                     > Stack;                       
                                                 while                                     (!Queue.empty()) {                       
                                                 Stack.push(Queue.front());                       
                                                 Queue.pop();                       
                                                 }                       
                                                 while                                     (!Stack.empty()) {                       
                                                 Queue.push(Stack.top());                       
                                                 Stack.pop();                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 queue<                                     int                                     > Queue;                       
                                                 Queue.push(10);                       
                                                 Queue.push(20);                       
                                                 Queue.push(30);                       
                                                 Queue.push(40);                       
                                                 Queue.push(50);                       
                                                 Queue.push(60);                       
                                                 Queue.push(70);                       
                                                 Queue.push(80);                       
                                                 Queue.push(90);                       
                                                 Queue.push(100);                       
           
                                                 reverseQueue(Queue);                       
                                                 Print(Queue);                       
                         }                       

JAVA

                         // Java program to reverse a Queue                       
                         import                                     java.util.LinkedList;                       
                         import                                     java.util.Queue;                       
                         import                                     java.util.Stack;                       
           
                         // Java program to reverse a queue                       
                         public                                     class                                     Queue_reverse {                       
                                   
                                                 static                                     Queue<Integer> queue;                       
           
                                                 // Utility function to print the queue                       
                                                 static                                     void                                     Print()                       
                                                 {                       
                                                 while                                     (!queue.isEmpty()) {                       
                                                 System.out.print( queue.peek() +                                     ", "                                     );                       
                                                 queue.remove();                       
                                                 }                       
                                                 }                       
           
                                                 // Function to reverse the queue                       
                                                 static                                     void                                     reversequeue()                       
                                                 {                       
                                                 Stack<Integer> stack =                                     new                                     Stack<>();                       
                                                 while                                     (!queue.isEmpty()) {                       
                                                 stack.add(queue.peek());                       
                                                 queue.remove();                       
                                                 }                       
                                                 while                                     (!stack.isEmpty()) {                       
                                                 queue.add(stack.peek());                       
                                                 stack.pop();                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 queue =                                     new                                     LinkedList<Integer>();                       
                                                 queue.add(                                     10                                     );                       
                                                 queue.add(                                     20                                     );                       
                                                 queue.add(                                     30                                     );                       
                                                 queue.add(                                     40                                     );                       
                                                 queue.add(                                     50                                     );                       
                                                 queue.add(                                     60                                     );                       
                                                 queue.add(                                     70                                     );                       
                                                 queue.add(                                     80                                     );                       
                                                 queue.add(                                     90                                     );                       
                                                 queue.add(                                     100                                     );                       
           
                                                 reversequeue();                       
                                                 Print();                       
                                                 }                       
                         }                       
                         //This code is contributed by Sumit Ghosh                       

Python3

                         # Python3 program to reverse a queue                       
                         from                                     queue                                     import                                     Queue                       
           
                         # Utility function to print the queue                       
                         def                                     Print                                     (queue):                       
                                                 while                                     (                                     not                                     queue.empty()):                       
                                                 print                                     (queue.queue[                                     0                                     ], end                                     =                                     ", "                                     )                       
                                                 queue.get()                       
           
                         # Function to reverse the queue                       
                         def                                     reversequeue(queue):                       
                                                 Stack                                     =                                     []                       
                                                 while                                     (                                     not                                     queue.empty()):                       
                                                 Stack.append(queue.queue[                                     0                                     ])                       
                                                 queue.get()                       
                                                 while                                     (                                     len                                     (Stack) !                                     =                                     0                                     ):                       
                                                 queue.put(Stack[                                     -                                     1                                     ])                       
                                                 Stack.pop()                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 queue                                     =                                     Queue()                       
                                                 queue.put(                                     10                                     )                       
                                                 queue.put(                                     20                                     )                       
                                                 queue.put(                                     30                                     )                       
                                                 queue.put(                                     40                                     )                       
                                                 queue.put(                                     50                                     )                       
                                                 queue.put(                                     60                                     )                       
                                                 queue.put(                                     70                                     )                       
                                                 queue.put(                                     80                                     )                       
                                                 queue.put(                                     90                                     )                       
                                                 queue.put(                                     100                                     )                       
           
                                                 reversequeue(queue)                       
                                                 Print                                     (queue)                       
           
                         # This code is contributed by PranchalK                       

C#

                         // c# program to reverse a Queue                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         public                                     class                                     GFG                       
                         {                       
           
                         public                                     static                                     LinkedList<                                     int                                     > queue;                       
           
                         // Utility function to print the queue                       
                         public                                     static                                     void                                     Print()                       
                         {                       
                                                 while                                     (queue.Count > 0)                       
                                                 {                       
                                                 Console.Write(queue.First.Value +                                     ", "                                     );                       
                                                 queue.RemoveFirst();                       
                                                 }                       
                         }                       
           
                         // Function to reverse the queue                       
                         public                                     static                                     void                                     reversequeue()                       
                         {                       
                                                 Stack<                                     int                                     > stack =                                     new                                     Stack<                                     int                                     >();                       
                                                 while                                     (queue.Count > 0)                       
                                                 {                       
                                                 stack.Push(queue.First.Value);                       
                                                 queue.RemoveFirst();                       
                                                 }                       
                                                 while                                     (stack.Count > 0)                       
                                                 {                       
                                                 queue.AddLast(stack.Peek());                       
                                                 stack.Pop();                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main(                                     string                                     [] args)                       
                         {                       
                                                 queue =                                     new                                     LinkedList<                                     int                                     >();                       
                                                 queue.AddLast(10);                       
                                                 queue.AddLast(20);                       
                                                 queue.AddLast(30);                       
                                                 queue.AddLast(40);                       
                                                 queue.AddLast(50);                       
                                                 queue.AddLast(60);                       
                                                 queue.AddLast(70);                       
                                                 queue.AddLast(80);                       
                                                 queue.AddLast(90);                       
                                                 queue.AddLast(100);                       
           
                                                 reversequeue();                       
                                                 Print();                       
                         }                       
                         }                       
           
                         // This code is contributed by Shrikant13                       

Javascript

                         <script>                       
                                                 // Javascript program to reverse a Queue                       
                                   
                                                 let queue = [];                       
                                   
                                                 // Utility function to print the queue                       
                                                 function                                     Print()                       
                                                 {                       
                                                 while                                     (queue.length > 0) {                       
                                                 document.write( queue[0] +                                     ", "                                     );                       
                                                 queue.shift();                       
                                                 }                       
                                                 }                       
                                   
                                                 // Function to reverse the queue                       
                                                 function                                     reversequeue()                       
                                                 {                       
                                                 let stack = [];                       
                                                 while                                     (queue.length > 0) {                       
                                                 stack.push(queue[0]);                       
                                                 queue.shift();                       
                                                 }                       
                                                 while                                     (stack.length > 0) {                       
                                                 queue.push(stack[stack.length - 1]);                       
                                                 stack.pop();                       
                                                 }                       
                                                 }                       
                                   
                                                 queue = []                       
                                                 queue.push(10);                       
                                                 queue.push(20);                       
                                                 queue.push(30);                       
                                                 queue.push(40);                       
                                                 queue.push(50);                       
                                                 queue.push(60);                       
                                                 queue.push(70);                       
                                                 queue.push(80);                       
                                                 queue.push(90);                       
                                                 queue.push(100);                       
           
                                                 reversequeue();                       
                                                 Print();                       
                                   
                         </script>                       

输出：

100, 90, 80, 70, 60, 50, 40, 30, 20, 10

复杂性分析：

时间复杂性： O（n）。因为我们需要将所有元素插入堆栈，然后再插入队列。
辅助空间： O（N）。使用堆栈存储值。

本文由 拉加夫·夏尔马 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章