Stack

Introduction to Stacks

A stack is a fundamental linear data structure that follows a particular order for operations. The order is LIFO (Last-In, First-Out). Think of it like a stack of plates: you can only add a new plate to the top, and you can only take a plate from the top. The last plate you put on is the first one you take off.

This "last-in, first-out" principle makes stacks incredibly useful for managing tasks and data in a specific sequence.

Core Operations

A stack is defined by a few primary operations that allow you to interact with it. All these operations happen at the "top" of the stack.

1. Push

The push operation adds a new element to the top of the stack.

stack.push("A"); // Adds 'A'
stack.push("B"); // Adds 'B' on top of 'A'

2. Pop

The pop operation removes the topmost element from the stack and returns it. Trying to pop from an empty stack results in an error known as a "stack underflow."

stack.pop(); // Removes and returns 'B'
stack.pop(); // Removes and returns 'A'

3. Peek

The peek operation returns the topmost element without removing it from the stack.

stack.peek(); // Returns 'A'

4. Is Empty

The isEmpty operation checks if the stack is empty.

stack.isEmpty(); // Returns true

5. Size

The size operation returns the number of elements in the stack.

stack.size(); // Returns 0

How Stacks are Implemented

Stacks can be implemented using various underlying data structures. The two most common ways are using arrays and linked lists.

Using an Array (or List)

This is the simplest implementation. An array can be used to store the stack elements, and a variable (often called top) can keep track of the index of the last inserted element.

• Pros: Easy to implement and memory-efficient (no pointers).

• Cons: Can have a fixed size, leading to a "stack overflow" if you push too many elements. Dynamic arrays can solve this but may have performance costs for resizing.

JavaScript

// A simple array-based stack implementation in JavaScript
class Stack {
  constructor() {
    this.items = [];
  }

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

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

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

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

Using a Linked List

In this approach, each element is a node that contains data and a pointer to the next node. The top of the stack is the head of the linked list.

• Pros: The stack can grow dynamically, so there's no fixed size limit (besides available memory).

• Cons: Requires slightly more memory due to the storage of pointers in each node.

Complexity Analysis

The efficiency of stack operations is one of its greatest advantages.

Real-World Applications

You interact with the stack data structure every day without realizing it!

Stacks LeetCode Problems