Implement a stack data structure using a single queue.
Note: A stack is a data structure that follows the LIFO (Last-In-First-Out) approach.
Solutions
Method 1: Using single Queue
In order to implement Stack using a single queue, we need to make a simple change in the push() method. Other methods like pop(), top() and size() will remain the same.
While adding to a queue, elements are inserted in a FIFO manner, i.e., the element inserted last will come out last. This behaviour is just the opposite to a Stack LIFO implementation.
So our task is to make sure that the last added element comes out first.
We can achive this by using a for loop of size()-1 (0 to n-2), remove element from queue and again push back to the queue, hence the most recent element becomes the most former element and vice versa.
Complexity
The time complexity of this solution is O(N) and space complexity is O(N).