Implementing Stacks

1. Creating Stack Class

Method	Description	Parameters	Return Value
constructor()	Initializes an empty stack	None	Stack instance
push(element)	Adds an element to the top of the stack	element: any type	undefined
pop()	Removes and returns the top element from the stack	None	Top element or undefined if stack is empty
peek()	Returns the top element without removing it	None	Top element or undefined if stack is empty
isEmpty()	Checks if the stack is empty	None	Boolean: true if empty, false otherwise
size()	Returns the number of elements in the stack	None	Number: current size of the stack

Example: Basic Stack Usage

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 2
console.log(stack.pop());  // 2
console.log(stack.size()); // 1

2. Creating Stack

Operation	Description	Time Complexity	Space Complexity
push(element)	Adds an element to the top of the stack	O(1)	O(1)
pop()	Removes and returns the top element from the stack	O(1)	O(1)
peek()/top()	Returns the top element without removing it	O(1)	O(1)
isEmpty()	Checks if the stack is empty	O(1)	O(1)
size()	Returns the number of elements in the stack	O(1)	O(1)

Example: Implementing a Stack in JavaScript

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "No elements in Stack";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Example usage
const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop());  // 20
console.log(stack.size()); // 1

3. Pushing Elements

Pushing an element onto a stack adds it to the top of the stack, following LIFO (Last In, First Out) order.

Operation	Time Complexity	Description
push(element)	`O(1)`	Adds an element to the top of the stack

Example: Pushing Elements to a Stack

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.items); // [10, 20]

4. Popping Elements

Method	Description	Time Complexity	Space Complexity
pop()	Removes and returns the top element from the stack	`O(1)`	`O(1)`

Example: Popping Elements from a Stack

const stack = [10, 20, 30];
const poppedElement = stack.pop();
console.log(poppedElement); // Output: 30
console.log(stack);         // Output: [10, 20]

Note: Popping from an empty stack typically results in undefined or throws an error depending on the implementation.

5. Peeking Top Element

Peeking at the top element of a stack is a common operation that allows you to inspect the most recently added item without removing it from the stack.

Operation	Description	Time Complexity	Space Complexity
peek()	Returns the top element of the stack without removing it	O(1)	O(1)

Example: Peeking at the top element in a stack

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.peek()); // Output: 30

6. Checking if Empty

Method	Description	Time Complexity	Space Complexity
isEmpty()	Returns `true` if the stack is empty, otherwise `false`	`O(1)`	`O(1)`

Example: Checking if Stack is Empty

class Stack {
  constructor() {
    this.items = [];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true

stack.push(10);
console.log(stack.isEmpty()); // false

7. Getting Stack Size

Method	Description	Time Complexity	Space Complexity
size()	Returns the number of elements in the stack	`O(1)`	`O(1)`

Example: Getting Stack Size

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  size() {
    return this.items.length;
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
console.log(stack.size()); // Output: 2

8. Clearing Stack

Clearing a stack involves removing all elements from the stack, leaving it empty. The method used to clear a stack depends on the implementation (array-based or linked list-based).

Operation	Description	Time Complexity	Space Complexity
clear()	Removes all elements from the stack, making it empty.	O(n)	O(1)

Example: Clearing a Stack (Array-based)

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  clear() {
    this.items = [];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.isEmpty()); // false
stack.clear();
console.log(stack.isEmpty()); // true

Example: Clearing a Stack (Linked List-based)

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
  }

  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
  }

  clear() {
    this.top = null;
  }

  isEmpty() {
    return this.top === null;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.isEmpty()); // false
stack.clear();
console.log(stack.isEmpty()); // true

9. Implementing with Two Queues

Stacks can be implemented using two queues to simulate LIFO (Last In, First Out) behavior. This approach uses one queue for pushing elements and another to assist in reversing the order during pop operations.

Operation	Description	Time Complexity	Space Complexity
push(element)	Enqueues the element to the first queue.	O(1)	O(n)
pop()	Transfers all but the last element from queue1 to queue2, then removes and returns the last element. Swaps queues afterward.	O(n)	O(n)
top()	Similar to pop but returns the top element without removing it.	O(n)	O(n)
isEmpty()	Checks if both queues are empty.	O(1)	O(1)

Example: Stack Implementation Using Two Queues

class StackWithQueues {
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }

  push(element) {
    this.queue1.push(element);
  }

  pop() {
    if (this.queue1.length === 0) return null;

    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift());
    }

    const popped = this.queue1.shift();
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    return popped;
  }

  top() {
    if (this.queue1.length === 0) return null;

    const temp = [];
    while (this.queue1.length > 1) {
      temp.push(this.queue1.shift());
    }

    const topElement = this.queue1[0];
    temp.push(topElement);
    [this.queue1, this.queue2] = [temp, []];
    return topElement;
  }

  isEmpty() {
    return this.queue1.length === 0 && this.queue2.length === 0;
  }
}

// Example usage:
const stack = new StackWithQueues();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.top()); // 2