Given a stack St of M elements and a queue Q of N elements. The task is to put every element of stack into the queue and every element of the queue into the stack without changing their order.
Examples:
Input: St = {4, 3, 2, 1}, Q = {8, 7, 6, 5}
Output: St = {8, 7, 6, 5}, Q = {1, 2, 3, 4}Input: St = {0, 1}, Q = {2, 3}
Output: St = {2, 3}, Q = {0, 1}
Naive Approach: The basic approach is to store the elements of the stack and the queue in a separate array and then put them again into the queue and the stack.
Time Complexity: O(N + M)
Auxiliary Space: O(N + M)
Optimized Approach: This problem can be solved without using any extra space by using the last-in-first-out and first-in-first-out properties of stack and queue.
Follow the steps to solve the problem:
- Put every element of the queue into the stack.
- Put extra elements of the stack into the queue again, the extra element of the stack is the element coming from the queue. Now, the queue is reversed.
- Now, put every element of the stack into the queue.
- At last, put original elements of the queue into the stack.
- Now repeat the first and second step again to maintain the order of the stack elements in the queue.
Follow the illustrations below for a better understanding of the approach:
Illustrations:
Consider the stack = [1, 2, 3, 4] where 1 is at the top and the queue = [8, 7, 6, 5] where 8 is at the front.
In first step:
One by one pop the element from the queue(i.e., all the elements of queue) and push into stack.
After First Iteration, Stack = [8, 1, 2, 3, 4] and queue = [7, 6, 5]
After Second Iteration, Stack = [7, 8, 1, 2, 3, 4] and queue = [6, 5]
After Third Iteration, Stack = [6, 7, 8, 1, 2, 3, 4] and queue = [5]
After Fourth Iteration, Stack = [5, 6, 7, 8, 1, 2, 3, 4] and queue = []In second step:
One by one pop the element from the stack(i.e., coming from queue) and push into queue.
After First Iteration, Stack = [6, 7, 8, 1, 2, 3, 4] and queue = [5]
After Second Iteration, Stack = [7, 8, 1, 2, 3, 4] and queue = [5, 6]
After Third Iteration, Stack = [8, 1, 2, 3, 4] and queue = [5, 6, 7]
After Fourth Iteration, Stack = [1, 2, 3, 4] and queue = [5, 6, 7, 8]In third step:
One by one pop the element from the stack(i.e., remaining all the elements) and push into queue.
After First Iteration, Stack = [2, 3, 4] and queue = [5, 6, 7, 8, 1]
After Second Iteration, Stack = [3, 4] and queue = [5, 6, 7, 8, 1, 2]
After Third Iteration, Stack = [4] and queue = [5, 6, 7, 8, 1, 2, 3]
After Fourth Iteration, Stack = [] and queue = [5, 6, 7, 8, 1, 2, 3, 4]In fourth step:
One by one pop the element from the queue(i.e., only element of queue before first step) and push into stack.
After First Iteration, Stack = [5] and queue = [6, 7, 8, 1, 2, 3, 4]
After Second Iteration, Stack = [6, 5] and queue = [7, 8, 1, 2, 3, 4]
After Third Iteration, Stack = [7, 6, 5] and queue = [8, 1, 2, 3, 4]
After Fourth Iteration, Stack = [8, 7, 6, 5] and queue = [1, 2, 3, 4]Now repeat first and second step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to Put every element of stack// into queue and queue into stack// without changing its ordervoid changeElement(stack<int>& St, queue<int>& Q){ // Calculate size of queue Q int Size = Q.size(); int Temp = Size; int N = St.size(); // Put every element of queue into stack while (!Q.empty()) { St.push(Q.front()); Q.pop(); } // Put extra element of stack into // queue again, extra element of stack // is the element coming from queue. // Now, the queue is reversed while (Size != 0) { Q.push(St.top()); St.pop(); Size--; } // Put every element of stack into queue while (!St.empty()) { Q.push(St.top()); St.pop(); } Size = Temp; // Put initial element of queue // into stack while (Size != 0) { St.push(Q.front()); Q.pop(); Size--; } // Repeat the first and second steps while (!Q.empty()) { St.push(Q.front()); Q.pop(); } while (N != 0) { Q.push(St.top()); St.pop(); N--; }}// Function to traverse till stack is// not empty and print the element in itvoid printStack(stack<int>& St){ while (!St.empty()) { cout << St.top() << " "; St.pop(); } cout << endl;}// Function to traverse till queue is not// empty and print the element in itvoid printQueue(queue<int>& Q){ while (!Q.empty()) { cout << Q.front() << " "; Q.pop(); } cout << endl;}// Driver Codeint main(){ stack<int> St; queue<int> Q; // Fill element into stack St.push(4); St.push(3); St.push(2); St.push(1); // Fill element into queue Q.push(8); Q.push(7); Q.push(6); Q.push(5); changeElement(St, Q); cout << "Stack = "; printStack(St); cout << "Queue = "; printQueue(Q); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;public class GFG { // Function to Put every element of stack // into queue and queue into stack // without changing its order static void changeElement(Stack<Integer> St, Deque<Integer> Q) { // Calculate size of queue Q int Size = Q.size(); int Temp = Size; int N = St.size(); // Put every element of queue into stack while (Q.size() > 0) { St.push(Q.element()); Q.remove(); } // Put extra element of stack into // queue again, extra element of stack // is the element coming from queue. // Now, the queue is reversed while (Size > 0) { Q.add(St.peek()); St.pop(); Size--; } // Put every element of stack into queue while (St.size() > 0) { Q.add(St.peek()); St.pop(); } Size = Temp; // Put initial element of queue // into stack while (Size > 0) { St.push(Q.element()); Q.remove(); Size--; } // Repeat the first and second steps while (Q.size() > 0) { St.push(Q.element()); Q.remove(); } while (N > 0) { Q.add(St.peek()); St.pop(); N--; } } // Function to traverse till stack is // not empty and print the element in it static void printStack(Stack<Integer> St) { while (St.size() > 0) { System.out.print(St.peek() + " "); St.pop(); } System.out.println(); } // Function to traverse till queue is not // empty and print the element in it static void printQueue(Deque<Integer> Q) { while (Q.size() > 0) { System.out.print(Q.removeLast() + " "); } } // Driver Code public static void main(String[] args) { Stack<Integer> St = new Stack<>(); Deque<Integer> Q = new LinkedList<>(); // Fill element into stack St.push(4); St.push(3); St.push(2); St.push(1); // Fill element into queue Q.add(8); Q.add(7); Q.add(6); Q.add(5); changeElement(St, Q); System.out.print("Stack = "); printStack(St); System.out.print("Queue = "); printQueue(Q); }}// This code is contributed by phasing17 |
Python3
# python3 program for the above approachimport collections# Function to Put every element of stack# into queue and queue into stack# without changing its orderdef changeElement(St, Q): # Calculate size of queue Q Size = len(Q) Temp = Size N = len(St) # Put every element of queue into stack while (len(Q) != 0): St.append(Q.popleft()) # Put extra element of stack into # queue again, extra element of stack # is the element coming from queue. # Now, the queue is reversed while (Size != 0): Q.append(St.pop()) Size -= 1 # Put every element of stack into queue while (len(St) != 0): Q.append(St.pop()) Size = Temp # Put initial element of queue # into stack while (Size != 0): St.append(Q.popleft()) Size -= 1 # Repeat the first and second steps while (len(Q) != 0): St.append(Q.popleft()) while (N != 0): Q.append(St.pop()) N -= 1# Function to traverse till stack is# not empty and print the element in itdef printStack(St): while (len(St) != 0): print(St.pop(), end=" ") print()# Function to traverse till queue is not# empty and print the element in itdef printQueue(Q): while (len(Q) != 0): print(Q.popleft(), end=" ") print()# Driver Codeif __name__ == "__main__": St = collections.deque() Q = collections.deque() # Fill element into stack St.append(4) St.append(3) St.append(2) St.append(1) # Fill element into queue Q.append(8) Q.append(7) Q.append(6) Q.append(5) changeElement(St, Q) print("Stack = ", end="") printStack(St) print("Queue = ", end="") printQueue(Q) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections;public class GFG{ // Function to Put every element of stack // into queue and queue into stack // without changing its order static void changeElement(Stack St, Queue Q) { // Calculate size of queue Q int Size = Q.Count; int Temp = Size; int N = St.Count; // Put every element of queue into stack while (Q.Count > 0) { St.Push(Q.Peek()); Q.Dequeue(); } // Put extra element of stack into // queue again, extra element of stack // is the element coming from queue. // Now, the queue is reversed while (Size != 0) { Q.Enqueue(St.Peek()); St.Pop(); Size--; } // Put every element of stack into queue while (St.Count > 0) { Q.Enqueue(St.Peek()); St.Pop(); } Size = Temp; // Put initial element of queue // into stack while (Size != 0) { St.Push(Q.Peek()); Q.Dequeue(); Size--; } // Repeat the first and second steps while (Q.Count > 0) { St.Push(Q.Peek()); Q.Dequeue(); } while (N != 0) { Q.Enqueue(St.Peek()); St.Pop(); N--; } } // Function to traverse till stack is // not empty and print the element in it static void printStack(Stack St) { while (St.Count > 0) { Console.Write(St.Peek() + " "); St.Pop(); } Console.WriteLine(); } // Function to traverse till queue is not // empty and print the element in it static void printQueue(Queue Q) { while (Q.Count > 0) { Console.Write(Q.Peek() + " "); Q.Dequeue(); } } // Driver Code static public void Main (){ Stack St = new Stack(); Queue Q = new Queue(); // Fill element into stack St.Push(4); St.Push(3); St.Push(2); St.Push(1); // Fill element into queue Q.Enqueue(8); Q.Enqueue(7); Q.Enqueue(6); Q.Enqueue(5); changeElement(St, Q); Console.Write( "Stack = "); printStack(St); Console.Write("Queue = "); printQueue(Q); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script>// JavaScript program for the above approach// Function to Put every element of stack// into queue and queue into stack// without changing its orderfunction changeElement(St, Q){ // Calculate size of queue Q let Size = Q.length; let Temp = Size; let N = St.length; // Put every element of queue into stack while (Q.length !== 0) { St.push(Q.shift()); } // Put extra element of stack into // queue again, extra element of stack // is the element coming from queue. // Now, the queue is reversed while (Size != 0) { Q.push(St.pop()); Size--; } // Put every element of stack into queue while (St.length !== 0) { Q.push(St.pop()); } Size = Temp; // Put initial element of queue // into stack while (Size != 0) { St.push(Q.shift()); Size--; } // Repeat the first and second steps while (Q.length !== 0) { St.push(Q.shift()); } while (N != 0) { Q.push(St.pop()); N--; }}// Function to traverse till stack is// not empty and print the element in itfunction printStack(St){ while (St.length !== 0) { document.write(St.pop()," "); } document.write("</br>");}// Function to traverse till queue is not// empty and print the element in itfunction printQueue(Q){ while (Q.length !== 0) { document.write(Q.shift()," "); } document.write("</br>");}// Driver Codelet St = [];let Q = [];// Fill element into stackSt.push(4);St.push(3);St.push(2);St.push(1);// Fill element into queueQ.push(8);Q.push(7);Q.push(6);Q.push(5);changeElement(St, Q);document.write("Stack = ");printStack(St);document.write("Queue = ");printQueue(Q);// This code is contributed by shinjanpatra</script> |
Stack = 8 7 6 5 Queue = 1 2 3 4
Time Complexity: O(M+N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
