Implement Queue using 2 Stacks

Implementing a queue using two stacks is a classic computer science problem that demonstrates how two fundamental data structures, stacks and queues, can be combined to achieve efficient queue operations.

In this approach, you use one stack for enqueue (insertion) operations and the other stack for dequeue (removal) operations, effectively simulating the behavior of a queue.

The key idea here is that you defer the reversal of elements until it is necessary (i.e., during pop or peek operations). This allows you to maintain the FIFO (First-In-First-Out) order of a queue while using two stacks.

Here’s how you can implement a queue using two stacks in C++:

#include <stack>
using namespace std;

class MyQueue {
private:
  stack<int> input;
  stack<int> output;

public:
  MyQueue() {}

  void push(int x) { 
    input.push(x); 
  }

  int pop() {
    if (output.empty()) {
      while (!input.empty()) {
        output.push(input.top());
        input.pop();
      }
    }
    int front = output.top();
    output.pop();
    return front;
  }

  int peek() {
    if (output.empty()) {
      while (!input.empty()) {
        output.push(input.top());
        input.pop();
      }
    }
    return output.top();
  }

  bool empty() { 
    return input.empty() && output.empty(); 
  }
}

When we need to pop or peek an element, we check if the output list is empty. If it is, we transfer all elements from the input list to the output list by repeatedly popping from the input list and appending to the output list. This way, the order of elements is reversed and we can get the front element of the queue from the last element of the output list.

The time complexity of this solution is O(1) amortized for each operation, and the space complexity is O(n) where n is the number of elements in the queue.

Learn more about Queue

A queue is a fundamental abstract data type (ADT) in computer science and programming that represents a collection of elements with two main characteristics:

1. Order: A queue follows a specific order for processing elements. It adheres to the First-In-First-Out (FIFO) principle, meaning that the first element added to the queue will be the first one to be removed. In other words, the element that has been in the queue the longest gets processed first.
2. Collection of Elements: A queue is a collection of elements, often of the same data type. Each element in the queue is referred to as an “item” or “entry.”

Common Operations on a Queue:

1. Enqueue: This operation is used to add (or “enqueue”) an element to the back of the queue. It is the process of inserting an item into the queue. The newly added element becomes the last one in the queue.
2. Dequeue: This operation is used to remove (or “dequeue”) the front element from the queue. It represents the process of extracting and removing the element that has been in the queue the longest. The element is removed from the front, and the second element in line becomes the new front.
3. Peek (Front): The “peek” operation allows you to examine the front element of the queue without removing it. It returns the element at the front of the queue but does not modify the queue itself.
4. IsEmpty: This operation checks whether the queue is empty or not. It returns a boolean value (true or false) to indicate whether there are any elements in the queue.
5. Size: The “size” operation returns the number of elements currently in the queue. It provides the count of items in the queue.

Queues are widely used in various computer science applications and algorithms. Some common use cases include:

• Task scheduling: In operating systems and multi-threaded applications, queues are used to manage and schedule tasks or processes in the order they should be executed.
• Breadth-First Search (BFS): BFS traversal of graphs and trees often uses a queue to keep track of the nodes to be visited next.
• Print Queue: In printing systems, print jobs are added to a queue, and the printer processes them in the order they were added.
• Data Buffering: Queues are used in data buffering scenarios to manage the flow of data between producers and consumers, ensuring data is processed in the correct order.
• Job Scheduling: In job scheduling systems, queues are used to manage and execute tasks or jobs based on their priority and order of arrival.

Overall, queues are a fundamental data structure that plays a crucial role in various computer science and programming scenarios where maintaining a specific order of elements is essential.

Learn more about Stack

A stack is a fundamental abstract data type (ADT) in computer science and programming that represents a collection of elements with two main characteristics:

1. Order: A stack follows a specific order for processing elements. It adheres to the Last-In-First-Out (LIFO) principle, meaning that the last element added to the stack will be the first one to be removed. In other words, the element that has been most recently added gets processed first.
2. Collection of Elements: A stack is a collection of elements, often of the same data type. Each element in the stack is referred to as a “pushed” item or “pushed” element.

Common Operations on a Stack:

1. Push: This operation is used to add (or “push”) an element onto the top of the stack. It represents the process of inserting an item into the stack. The newly pushed element becomes the top element of the stack.
2. Pop: This operation is used to remove (or “pop”) the top element from the stack. It represents the process of extracting and removing the most recently added element. The element is removed from the top, and the element below it becomes the new top.
3. Peek (Top): The “peek” operation allows you to examine the top element of the stack without removing it. It returns the element at the top of the stack but does not modify the stack itself.
4. IsEmpty: This operation checks whether the stack is empty or not. It returns a boolean value (true or false) to indicate whether there are any elements in the stack.
5. Size: The “size” operation returns the number of elements currently in the stack. It provides the count of items in the stack.

Stacks are widely used in various computer science applications and algorithms. Some common use cases include:

• Function Calls and Call Stack: In many programming languages, function calls and their associated variables and return addresses are managed using a call stack.
• Expression Evaluation: Stacks are used to evaluate expressions, such as arithmetic expressions, by maintaining operands and operators in the correct order.
• Backtracking Algorithms: In algorithms like depth-first search (DFS) and recursive algorithms, a stack can be used to keep track of states or function calls.
• Undo and Redo Functionality: Stacks can be used to implement undo and redo functionality in applications by keeping track of the history of actions.
• Parsing: Stacks are often used in parsing algorithms to track the structure of expressions, XML, and other data formats.
• Memory Management: Stacks are used in low-level memory management, such as managing the call stack and managing memory for function calls and local variables.

Overall, stacks are a fundamental data structure that plays a crucial role in various computer science and programming scenarios, particularly when managing elements in a last-in-first-out (LIFO) order is necessary.