ℹ️ 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

TypeScript

Goal -- WPM

Ready
Exercise Algorithm Area
1class MyQueue {

2private stack1: number[]; // For enqueue operations

3private stack2: number[]; // For dequeue operations

4

5constructor() {

6this.stack1 = [];

7this.stack2 = [];

8}

9

10/** Push element x to the back of queue. */

11push(x: number): void {

12this.stack1.push(x);

13}

14

15/** Removes the element from in front of queue and returns that element. */

16pop(): number {

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

18// If stack2 is empty, transfer all elements from stack1 to stack2

19// This reverses the order, making the top of stack2 the front of the queue

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

21this.stack2.push(this.stack1.pop()!);

22}

23}

24

25// If stack2 is still empty after transfer, the queue is empty

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

27throw new Error("Cannot pop from an empty queue.");

28}

29

30return this.stack2.pop()!;

31}

32

33/** Get the front element. */

34peek(): number {

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

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

37this.stack2.push(this.stack1.pop()!);

38}

39}

40

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

42throw new Error("Cannot peek an empty queue.");

43}

44

45return this.stack2[this.stack2.length - 1];

46}

47

48/** Returns whether the queue is empty. */

49empty(): boolean {

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

51}

52}

53

54class MyQueueHelper {

55// This helper class is just for demonstration and doesn't add new logic.

56// In a real scenario, it might contain utility functions related to stack operations.

57private helperStack: number[];

58

59constructor() {

60this.helperStack = [];

61}

62

63pushToHelper(x: number): void {

64this.helperStack.push(x);

65}

66

67popFromHelper(): number {

68if (this.helperStack.length === 0) {

69throw new Error("Helper stack is empty.");

70}

71return this.helperStack.pop()!;

72}

73}
Algorithm description viewbox

Implement Queue using Stacks

Algorithm description:

This implementation simulates a queue data structure using two stacks. A queue follows a First-In, First-Out (FIFO) principle, while stacks follow a Last-In, First-Out (LIFO) principle. By strategically using two stacks, we can achieve the FIFO behavior. This is a common interview question that tests understanding of fundamental data structures and their interrelationships.

Algorithm explanation:

The `MyQueue` class uses two stacks: `stack1` for enqueue operations and `stack2` for dequeue operations. When an element is pushed (`push`), it's simply added to `stack1`. When an element needs to be dequeued (`pop` or `peek`), if `stack2` is empty, all elements from `stack1` are transferred to `stack2`. This reversal ensures that the element that was pushed first into `stack1` (and is at the bottom of `stack1`) becomes the top element of `stack2`. The `pop` operation then removes and returns the top element from `stack2`. If `stack2` is still empty after the transfer, it means the queue is empty. The `peek` operation is similar to `pop` but only returns the top element without removing it. The `empty` method checks if both stacks are empty. The amortized time complexity for `push` is O(1). For `pop` and `peek`, the worst-case complexity is O(N) when a transfer is needed, but the amortized complexity is O(1) because each element is pushed and popped from each stack at most once. The space complexity is O(N) to store the elements.

Pseudocode:

class MyQueue:
  stack1 (for enqueue)
  stack2 (for dequeue)

  constructor():
    initialize stack1 and stack2 as empty stacks

  push(x):
    push x onto stack1

  pop():
    if stack2 is empty:
      while stack1 is not empty:
        move top element from stack1 to stack2
    if stack2 is empty:
      throw error "Queue is empty"
    return pop from stack2

  peek():
    if stack2 is empty:
      while stack1 is not empty:
        move top element from stack1 to stack2
    if stack2 is empty:
      throw error "Queue is empty"
    return top element of stack2

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