ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Implement Queue using Stacks

TSX

Goal -- WPM

Ready
Exercise Algorithm Area
1class QueueUsingStacks {

2private stack1: number[]; // Primary stack for enqueue operations

3private stack2: number[]; // Secondary stack for dequeue operations

4

5constructor() {

6this.stack1 = [];

7this.stack2 = [];

8}

9

10/**

11* Adds an element to the back of the queue.

12* @param x The element to enqueue.

13*/

14enqueue(x: number): void {

15// Simply push the new element onto stack1.

16// This is an O(1) operation.

17this.stack1.push(x);

18}

19

20/**

21* Removes and returns the element from the front of the queue.

22* @returns The element at the front of the queue, or undefined if the queue is empty.

23*/

24dequeue(): number | undefined {

25// If stack2 is empty, we need to transfer elements from stack1.

26// This ensures that the elements are in the correct FIFO order for dequeueing.

27if (this.stack2.length === 0) {

28// Transfer all elements from stack1 to stack2.

29// The top of stack1 becomes the bottom of stack2, and vice-versa.

30// This reversal effectively creates the queue order in stack2.

31while (this.stack1.length > 0) {

32const element = this.stack1.pop();

33if (element !== undefined) {

34this.stack2.push(element);

35}

36}

37}

38

39// Now, pop from stack2. If stack2 is still empty, the queue is empty.

40// This is an amortized O(1) operation because each element is pushed

41// and popped from stack1 and stack2 at most once.

42return this.stack2.pop();

43}

44

45/**

46* Returns the element at the front of the queue without removing it.

47* @returns The element at the front of the queue, or undefined if the queue is empty.

48*/

49peek(): number | undefined {

50// Similar logic to dequeue, but we don't pop from stack2.

51if (this.stack2.length === 0) {

52while (this.stack1.length > 0) {

53const element = this.stack1.pop();

54if (element !== undefined) {

55this.stack2.push(element);

56}

57}

58}

59// Return the top element of stack2 without removing it.

60return this.stack2.length > 0 ? this.stack2[this.stack2.length - 1] : undefined;

61}

62

63/**

64* Checks if the queue is empty.

65* @returns True if the queue is empty, false otherwise.

66*/

67isEmpty(): boolean {

68// The queue is empty if both stacks are empty.

69return this.stack1.length === 0 && this.stack2.length === 0;

70}

71}
Algorithm description viewbox

Implement Queue using Stacks

Algorithm description:

This implementation demonstrates how to create a Queue data structure using only two Stacks. A queue follows a First-In, First-Out (FIFO) principle, while stacks follow a Last-In, First-Out (LIFO) principle. This is a classic problem that tests understanding of data structure manipulation. It's useful in scenarios where you need to simulate queue behavior but are restricted to stack operations, such as in certain algorithm implementations or system-level programming.

Algorithm explanation:

The QueueUsingStacks class uses two stacks: `stack1` for enqueuing and `stack2` for dequeuing. When an element is enqueued, it's simply pushed onto `stack1`. When an element needs to be dequeued, the algorithm first checks if `stack2` is empty. If it is, all elements from `stack1` are popped and pushed onto `stack2`. This reversal process ensures that the elements in `stack2` are now in the correct FIFO order for dequeueing. The `dequeue` operation then pops from `stack2`. The `peek` operation works similarly to `dequeue` but does not remove the element. The `isEmpty` operation checks if both stacks are empty. The time complexity for `enqueue` is O(1). The `dequeue` and `peek` operations have an amortized time complexity of O(1), as each element is pushed and popped from each stack at most once over the lifetime of the queue. The space complexity is O(n), where n is the number of elements in the queue, due to the storage required by the two stacks.

Pseudocode:

class QueueUsingStacks:
    stack1 = empty stack
    stack2 = empty stack

    method enqueue(x):
        push x onto stack1

    method dequeue():
        if stack2 is empty:
            while stack1 is not empty:
                pop element from stack1
                push element onto stack2
        if stack2 is not empty:
            return pop from stack2
        else:
            return undefined (queue is empty)

    method peek():
        if stack2 is empty:
            while stack1 is not empty:
                pop element from stack1
                push element onto stack2
        if stack2 is not empty:
            return top element of stack2
        else:
            return undefined (queue is empty)

    method isEmpty():
        return stack1 is empty AND stack2 is empty