The stack

The LIFO rule:

A stack is a linear data structure where all insertions and deletions happen at one end, called the top. The rule is LIFO (Last In, First Out): the element added most recently is the one removed first.

Imagine a stack of dinner plates in a cupboard. When you grab a plate, you take from the top (the last one placed there). When you put a plate back, it goes on top. You never grab from the middle or bottom. That is LIFO.

The three operations:

1. Push: Add an element to the top of the stack. Returns nothing; updates the stack in-place.
2. Pop: Remove and return the top element of the stack. If the stack is empty, either return null or raise an error (implementation-dependent).
3. Peek (or top): Return the top element without removing it. Lets you see what is there before you commit to popping.

const stack = [];  // Empty stack

// Push: add 10, 20, 30
stack.push(10);    // Stack: [10]
stack.push(20);    // Stack: [10, 20]
stack.push(30);    // Stack: [10, 20, 30]

// Peek: see the top
console.log(stack[stack.length - 1]);  // 30 (without removing)

// Pop: remove the top
const top = stack.pop();  // Returns 30. Stack: [10, 20]

Array implementation:

An array naturally models a stack. The end of the array is the top. Push appends to the end; pop removes from the end. Both run in O(1) amortized time (in JavaScript, the language hides array resizing).

class Stack {
  constructor() {
    this.items = [];
  }
  
  push(value) {
    this.items.push(value);
  }
  
  pop() {
    if (this.items.length === 0) return null;
    return this.items.pop();
  }
  
  peek() {
    if (this.items.length === 0) return null;
    return this.items[this.items.length - 1];
  }
  
  isEmpty() {
    return this.items.length === 0;
  }
}

Linked-list implementation:

A stack can also be backed by a linked list. Push and pop both work at the head (no traversal needed). This is also O(1).

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

class StackLinkedList {
  constructor() {
    this.top = null;  // Head pointer
  }
  
  push(value) {
    const newNode = new Node(value, this.top);
    this.top = newNode;
  }
  
  pop() {
    if (this.top === null) return null;
    const value = this.top.value;
    this.top = this.top.next;
    return value;
  }
  
  peek() {
    if (this.top === null) return null;
    return this.top.value;
  }
  
  isEmpty() {
    return this.top === null;
  }
}

A worked application: balanced brackets

One of the most common uses of stacks is to check if brackets, parentheses, and braces are balanced in an expression.

The problem: Given a string with characters (, ), [, ], {, }, check if every opening bracket has a matching closing bracket in the correct order.

Example: "({[]})" is balanced. "({[}])" is not (the } closes the wrong bracket).

The algorithm: Process the string from left to right.

1. If you see an opening bracket ((, [, {), push it onto the stack.
2. If you see a closing bracket (), ], }), pop the stack and check if it matches. If it does not match, return false. If the stack is empty, return false (no opening bracket to match).
3. At the end, the stack must be empty. If not, there are unclosed opening brackets.

Example trace: "{[]}"

• See {: push {. Stack: [{]
• See [: push [. Stack: [{, []
• See ]: pop [. Does [ match ]? Yes. Stack: [{]
• See }: pop {. Does { match }? Yes. Stack: []
• End: stack is empty. Balanced!

Example trace: "{[}]"

• See {: push {. Stack: [{]
• See [: push [. Stack: [{, []
• See }: pop [. Does [ match }? No. Return false. Not balanced.