Implementation of Stack using Queues

The Stack class is used to manage a collection of objects in a last-in-first-out (LIFO) manner. LIFO means that the last inserted element is the first to be removed. The operation include adding items to the stack (push), removing items from the stack (pop), viewing the top item without removing it (peek), checking if the stack is empty, and searching for an item in the stack and determining its position relative to the top.

One real-life example of a stack is a stack of plates in a canteen. The plate on top is the first one to be taken, while the plate at the bottom remains in the stack the longest. Another real-life example of a stack is a deck of cards, piles of books, piles of money, and many more. This demonstrates the Last In First Out (LIFO) or First In Last Out (FILO) order.

In this discussion, we will explore how to implement a Stack using Queue. There are two approaches to implementing a stack using Queue:

• Making the push operation costly
• Making the pop operation costly

Making the push operation costly:

The approach involves simulating a stack using two queues, where the push operation is made costly. Elements are moved between the two queues to achieve the stack behavior, resulting in a costly push but efficient pop operation.

Making the pop operation costly:

In this approach, the push operation takes O(1) time as the new elements are added at the end of the queue. However, the pop operation takes O(n) time, as all elements except the last one need to be moved to Queue2, and the last element is removed. Then, all elements from Queue2 are moved back to Queue1.

geeksforgeeks

Steps for Implementing Stack Data Structure using two Queues

To start with, we will create a class called Stack that will contain two queue objects — q1 and q2.

Step 1:
Define the Stack Class with fundamental operations push, pop, top, empty

Step 2:
Implement the Push Operation and Pop Operation

push(int x)

This method adds a new element x to the "top" of the stack. However, because q1 is used as the main queue that holds elements in stack order, we need to reorder it each time a new element is pushed. Here’s the step-by-step process:

Push New Element to q2:
The new element x is pushed to q2, which serves as a temporary holding queue.

• topElement is updated to x, keeping track of the current top element for future reference.

Transfer Elements from q1 to q2:
The function moves all elements from q1 to q2. This ensures the newly added element x remains at the front of q2, preserving stack order (last-in, first-out).

Swap q1 and q2:
Finally, q1 is set to q2 (using std::move to avoid copying), so q1 now holds the correct stack order, with x at the front.

• q2 is emptied in this step, ready to act as a temporary queue for the next push operation.

Effectively, the push operation is made "costly" by reordering q1 each time a new element is added. The most recently pushed element is always at the front of q1.

Step 3:
Implement the Top Operation

Step 4:
Implement the IsEmpty Operation and the size Operation

We can find the complete solution for Implementing a Stack Data Structure using Two Queues in C++ by clicking GitHub link.

Conclusion

A queue-based stack is a clever way of combining queues and stacks in data structures. It uses two queues to perform stack operations like adding and removing elements. Stacks work on the principle of Last-In-First-Out (LIFO), while queues follow First-In-First-Out (FIFO). Stacks support actions like push, pop, top, empty, and size, while queues handle enqueue (push), dequeue (pop), front, back, empty, and size operations. This combination of stack and queue features offers a versatile and efficient approach to managing data in computer systems.

More Reads:
If you’re looking for the code to implement a stack data structure using queue in C++, you can find it by clicking on the link provided.

You Might Like:

1. Implementing a Queue using a Vector in C++
2. Implementing a Stack Using a Vector in C++
3. Different Types of Queues and its Applications