Implement Queue using Arrays

Stack / Queues Implementation Easy

Implement a First-In-First-Out (FIFO) queue using an array. The implemented queue should support the following operations: push, dequeue, pop, and isEmpty.

Implement the ArrayQueue class:

void push(int x): Adds element x to the end of the queue.

int pop(): Removes and returns the front element of the queue.

int peek(): Returns the front element of the queue without removing it.

boolean isEmpty(): Returns true if the queue is empty, false otherwise.

Examples:

Input:

["ArrayQueue", "push", "push", "peek", "pop", "isEmpty"]

[[], [5], [10], [], [], []]

Output: [null, null, null, 5, 5, false]

Explanation:

ArrayQueue queue = new ArrayQueue();

queue.push(5);

queue.push(10);

queue.peek(); // returns 5

queue.pop(); // returns 5

queue.isEmpty(); // returns false

Input:

["ArrayQueue", "isEmpty"]

[[]]

Output:[null, true]

Explanation:

ArrayQueue queue = new ArrayQueue();

queue.isEmpty(); // returns true

Input:

["ArrayQueue", "push", "pop", "isEmpty"]

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

Constraints

1 <= numbers of calls made <= 100
1 <= x <= 100

Hints

Think of it as a line at a checkout counter where the first person in line gets served first.

Company Tags

Boston Consulting Group Nutanix Morgan Stanley Wayfair Pinterest PayPal Visa Medtronic HashiCorp Johnson & Johnson Snowflake Cloudflare Ernst & Young Siemens Healthineers Texas Instruments NVIDIA Riot Games Epic Systems American Express Chewy Robinhood Flipkart Bloomberg Rockstar Games Dropbox Google Microsoft Amazon Meta Apple Netflix Adobe TCS Cognizant Accenture Infosys Capgemini Wipro

Intuition :

Imagine you're managing a ticket counter at a busy theater. You have a limited number of tickets to sell, and you want to ensure the process is efficient and fair. To do this, you use a special system to keep track of which tickets have been sold and which are available, without having to rearrange them constantly. This system operates like a circular queue.

The Ticket Counter (Queue): You have a counter with a fixed number of ticket slots, say 5 slots, arranged in a circle. Each slot can hold one ticket.

Selling a Ticket (Enqueue Operation): When a customer arrives to buy a ticket, you place the ticket in the next available slot. Keep track of the position where the next ticket should be placed using a variable called rear. For example, if you have sold tickets to 3 customers, your counter might look like this: [T1, T2, T3, _, _], where T1, T2, and T3 represent sold tickets, and the next ticket will be placed in the fourth slot.

Customer Leaving with a Ticket (Dequeue Operation): When a customer takes a ticket, you remove it from the slot at the front of the queue. Instead of shifting all the tickets forward, you just move the front pointer to the next slot. Continuing with our example, if the first customer takes their ticket, your counter now looks like this: [_, T2, T3, _, _], with the front pointing to the second slot.

Handling Wrap-Around (Circular Array): When the rear or front reaches the end of the array, it wraps around to the beginning. This ensures that you make efficient use of the available slots without needing to shift tickets around. If you sell more tickets and the rear reaches the end, it wraps around like this: [T4, T5, T3, _, T1] with the rear and front properly adjusted using modular arithmetic.

Checking Availability (IsEmpty and IsFull Operations): You need to check if there are any tickets left or if your counter is full. These checks ensure you manage the tickets efficiently.

Approach :

Declare an Array of a Particular Size: Declare an array to store the elements of the queue. The size of this array is determined when the queue is initialized.
Define Variables:
- start: Tracks the index of the front element.
- end: Tracks the index of the last element.
- size: Keeps the current number of elements in the queue.
- capacity: The maximum number of elements the queue can hold.
Push Operation (push(int x)): Check if the queue is full by comparing size and capacity. If not full, increment the rear using modular arithmetic to wrap around if necessary, then insert the element at the rear index. Increment the size.
Pop Operation (pop()): Check if the queue is empty by comparing the size with 0. If not empty, return the element at the front index, then increment the front using modular arithmetic to wrap around if necessary. Decrement the size.
Peek Operation (peek()): Check if the queue is empty. If not empty, return the element at the front index.
IsEmpty Operation (isEmpty()): Check if the size is 0 to determine if the queue is empty.

Dry Run:

For a dry run refer to the video.

Solution:

#include <bits/stdc++.h>
using namespace std;

// Class implementing Queue using Arrays
class ArrayQueue {
    // Array to store queue elements
    int* arr;
    // Indices for start and end of the queue
    int start, end;
    // Current size and maximum size of the queue
    int currSize, maxSize;

public:
    // Constructor
    ArrayQueue() {
        arr = new int[10];
        start = -1;
        end = -1;
        currSize = 0;
        maxSize = 10;
    }

    // Method to push an element into the queue
    void push(int x) {
        // Check if the queue is full
        if (currSize == maxSize) {
            cout << "Queue is full\nExiting..." << endl;
            exit(1);
        }
        
        // If the queue is empty, initialize start and end
        if (end == -1) {
            start = 0;
            end = 0;
        } 
        else {
            // Circular increment of end
            end = (end + 1) % maxSize;
        }
            
        arr[end] = x;
        currSize++;
    }

    // Method to pop an element from the queue
    int pop() {
        // Check if the queue is empty
        if (start == -1) {
            cout << "Queue Empty\nExiting..." << endl;
            exit(1);
        }
        int popped = arr[start];
        
        // If the queue has only one element, reset start and end
        if (currSize == 1) {
            start = -1;
            end = -1;
        }
        else {
            // Circular increment of start
            start = (start + 1) % maxSize;
        }
        
        currSize--;
        return popped;
    }

    // Method to get the front element of the queue
    int peek() {
        // Check if the queue is empty
        if (start == -1) {
            cout << "Queue is Empty" << endl;
            exit(1);
        }
        return arr[start];
    }

    // Method to determine whether the queue is empty
    bool isEmpty() {
        return (currSize == 0);
    }
};

int main() {
    ArrayQueue queue;
    vector<string> commands = {"ArrayQueue", "push", "push", 
                               "peek", "pop", "isEmpty"};
    vector<vector<int>> inputs = {{}, {5}, {10}, {}, {}, {}};

    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            queue.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << queue.pop() << " ";
        } else if (commands[i] == "peek") {
            cout << queue.peek() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (queue.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "ArrayQueue") {
            cout << "null ";
        }
    }

    return 0;
}
import java.util.*;

// Class implementing Queue using Arrays
class ArrayQueue {
    // Array to store queue elements
    int[] arr;
    // Indices for start and end of the queue
    int start, end;
    // Current size and maximum size of the queue
    int currSize, maxSize;

    // Constructor
    public ArrayQueue() {
        arr = new int[10];
        start = -1;
        end = -1;
        currSize = 0;
        maxSize = 10;
    }

    // Method to push an element into the queue
    public void push(int x) {
        // Check if the queue is full
        if (currSize == maxSize) {
            System.out.println("Queue is full\nExiting...");
            System.exit(1);
        }

        // If the queue is empty, initialize start and end
        if (end == -1) {
            start = 0;
            end = 0;
        } 
        else {
            // Circular increment of end
            end = (end + 1) % maxSize;
        }

        arr[end] = x;
        currSize++;
    }

    // Method to pop an element from the queue
    public int pop() {
        // Check if the queue is empty
        if (start == -1) {
            System.out.println("Queue Empty\nExiting...");
            System.exit(1);
        }
        int popped = arr[start];

        // If the queue has only one element, reset start and end
        if (currSize == 1) {
            start = -1;
            end = -1;
        } 
        else {
            // Circular increment of start
            start = (start + 1) % maxSize;
        }

        currSize--;
        return popped;
    }

    // Method to get the front element of the queue
    public int peek() {
        // Check if the queue is empty
        if (start == -1) {
            System.out.println("Queue is Empty");
            System.exit(1);
        }
        return arr[start];
    }

    // Method to determine whether the queue is empty
    public boolean isEmpty() {
        return (currSize == 0);
    }
}

class Main {
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue();

        String[] commands = {"ArrayQueue", "push", "push", 
                             "peek", "pop", "isEmpty"};
        int[][] inputs = {{}, {5}, {10}, {}, {}, {}};

        for (int i = 0; i < commands.length; ++i) {
            switch (commands[i]) {
                case "push":
                    queue.push(inputs[i][0]);
                    System.out.print("null ");
                    break;
                case "pop":
                    System.out.print(queue.pop() + " ");
                    break;
                case "peek":
                    System.out.print(queue.peek() + " ");
                    break;
                case "isEmpty":
                    System.out.print(queue.isEmpty() ? "true " : "false ");
                    break;
                case "ArrayQueue":
                    System.out.print("null ");
                    break;
            }
        }
    }
}
# Class implementing Queue using Arrays
class ArrayQueue:
    # Constructor
    def __init__(self):
        # Array to store queue elements
        self.arr = [0] * 10
        # Indices for start and end of the queue
        self.start = -1
        self.end = -1
        # Current size and maximum size of the queue
        self.currSize = 0
        self.maxSize = 10

    # Method to push an element into the queue
    def push(self, x):
        # Check if the queue is full
        if self.currSize == self.maxSize:
            print("Queue is full\nExiting...")
            exit(1)

        # If the queue is empty, initialize start and end
        if self.end == -1:
            self.start = 0
            self.end = 0
        else:
            # Circular increment of end
            self.end = (self.end + 1) % self.maxSize

        self.arr[self.end] = x
        self.currSize += 1

    # Method to pop an element from the queue
    def pop(self):
        # Check if the queue is empty
        if self.start == -1:
            print("Queue Empty\nExiting...")
            exit(1)
        popped = self.arr[self.start]

        # If the queue has only one element, reset start and end
        if self.currSize == 1:
            self.start = -1
            self.end = -1
        else:
            # Circular increment of start
            self.start = (self.start + 1) % self.maxSize

        self.currSize -= 1
        return popped

    # Method to get the front element of the queue
    def peek(self):
        # Check if the queue is empty
        if self.start == -1:
            print("Queue is Empty")
            exit(1)
        return self.arr[self.start]

    # Method to determine whether the queue is empty
    def isEmpty(self):
        return self.currSize == 0


if __name__ == "__main__":
    queue = ArrayQueue()
    commands = ["ArrayQueue", "push", "push", "peek", "pop", "isEmpty"]
    inputs = [[], [5], [10], [], [], []]

    for i in range(len(commands)):
        if commands[i] == "push":
            queue.push(inputs[i][0])
            print("null", end=" ")
        elif commands[i] == "pop":
            print(queue.pop(), end=" ")
        elif commands[i] == "peek":
            print(queue.peek(), end=" ")
        elif commands[i] == "isEmpty":
            print("true" if queue.isEmpty() else "false", end=" ")
        elif commands[i] == "ArrayQueue":
            print("null", end=" ")
// Class implementing Queue using Arrays
class ArrayQueue {
    // Constructor
    constructor() {
        // Array to store queue elements
        this.arr = new Array(10);
        // Indices for start and end of the queue
        this.start = -1;
        this.end = -1;
        // Current size and maximum size of the queue
        this.currSize = 0;
        this.maxSize = 10;
    }

    // Method to push an element into the queue
    push(x) {
        // Check if the queue is full
        if (this.currSize === this.maxSize) {
            console.log("Queue is full\nExiting...");
            process.exit(1);
        }

        // If the queue is empty, initialize start and end
        if (this.end === -1) {
            this.start = 0;
            this.end = 0;
        } 
        else {
            // Circular increment of end
            this.end = (this.end + 1) % this.maxSize;
        }

        this.arr[this.end] = x;
        this.currSize++;
    }

    // Method to pop an element from the queue
    pop() {
        // Check if the queue is empty
        if (this.start === -1) {
            console.log("Queue Empty\nExiting...");
            process.exit(1);
        }
        let popped = this.arr[this.start];

        // If the queue has only one element, reset start and end
        if (this.currSize === 1) {
            this.start = -1;
            this.end = -1;
        } 
        else {
            // Circular increment of start
            this.start = (this.start + 1) % this.maxSize;
        }

        this.currSize--;
        return popped;
    }

    // Method to get the front element of the queue
    peek() {
        // Check if the queue is empty
        if (this.start === -1) {
            console.log("Queue is Empty");
            process.exit(1);
        }
        return this.arr[this.start];
    }

    // Method to determine whether the queue is empty
    isEmpty() {
        return this.currSize === 0;
    }
}

const queue = new ArrayQueue();
const commands = ["ArrayQueue", "push", "push", "peek", "pop", "isEmpty"];
const inputs = [[], [5], [10], [], [], []];

for (let i = 0; i < commands.length; ++i) {
    if (commands[i] === "push") {
        queue.push(inputs[i][0]);
        console.log("null ");
    } else if (commands[i] === "pop") {
        console.log(queue.pop() + " ");
    } else if (commands[i] === "peek") {
        console.log(queue.peek() + " ");
    } else if (commands[i] === "isEmpty") {
        console.log(queue.isEmpty() ? "true " : "false ");
    } else if (commands[i] === "ArrayQueue") {
        console.log("null ");
    }
}

Complexity Analysis:

Time Complexity: O(1) as all individual queue operations are taking constant time. Space Complexity: O(1) as the implementation uses a fixed size array.

Code

Problem List

Implement Queue using Arrays

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition :

Approach :

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code