Implementing Queue using Stacks

Board Infinity
Board Infinity
Implementing Queue using Stacks

    Data Structures: Foundation of Effective Programming

    10 Common Data Structures Every Programmer Must Know

    Quick Guide to Abstract Data Types

    A Simple Introduction to Recursion

    Arrays vs Linked List

    Stack in Data Structure

    Complete Walkthrough of Stacks in Data Structure

    Working on Queue using STL

    Implementing Queue using Stacks

    A Detailed walkthrough of the Doubly Linked List

    How to Reverse a Linked List?

    Binary Tree Code Implementation

    Complete Walkthrough of AVL Trees

    Heap Data Structure

    Trie Data Structure: Explanation and Examples

Introduction

The FIFO (First In First Out) principle, which dictates that insertion takes place from the back and deletion takes place from the front, is followed by the queue, a linear data structure. A linear data structure called a stack implements the LIFO (Last In First Out) principle, which states that insertion and deletion must always start at the top of the stack.

Problem Statement

Here, you must use stacks to implement a first-in, first-out queue. All functions, including push, pop, and peek, ought to be supported by the queue.

Examples

Input

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

Output

[null, null, null, 1, 1, false]

Explanation

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false 

Let's first clarify the fundamental distinction between Stack and Queue before moving on to the solution.

The data structure for the stack is Last in First Out. Only the top of the stack is used for push and pop operations (). Push, pop, and peek operations are supported.

First In First Out (Queue) is a data structure. Two endpoints of the queue are used for push and pop operations. Enqueue, Dequeue, and Peek operations are supported.

You can see that in order to implement the queue, we would need two stacks: one for the en queue operation and one for the de queue action.

Approach: Making enqueue operation costly

As was mentioned above, we are aware that the queue operates according to a FIFO order, meaning that the element that enters first exits first. As a result, we must come up with a method involving stacks that ensures the element being pushed stays at the top. As a result, we will apply the same to a second stack.

Algorithm

For enqueue

  • Initialize the S1 and S2 stacks.
  • Insert the element into S2 if S1 is empty.
  • Otherwise, move all of the components from S1 to S2.
  • Put the required component into S1 by pushing it there.
  • Return all of the components from S2 to S1.

For dequeue

  • Return -1 if stack S1 is bare.
  • Return the stack's top element if not.

C++ Code

struct Queue {
  stack < int > s1, s2;
  void enQueue(int x) {
    while (!s1.empty()) {
      s2.push(s1.top());
      s1.pop();
    }
    s1.push(x);
    while (!s2.empty()) {
      s1.push(s2.top());
      s2.pop();
    }
  }
  int deQueue() {
    if (s1.empty()) {
      cout << "Q is Empty";
      exit(0);
    }
    int x = s1.top();
    s1.pop();
    return x;
  }
};

write your code here: Coding Playground

Time Complexity: O(1) for pop, O(N) for enqueue operations

Space Complexity: O(N)