Description

A Stack is a linear data structure where elements are stacked on each other. It's like an array, but with a few restrictions:

• You can't access items randomly by using their index.

• You can only add an item to the end, and remove or retrieve the latest item.

The simplest way to think about stack structure is to imagine a deck of cards, or a stack of plates. You put a plate on top of another, and to access a plate in the middle you first need to get plates from the top.

A stack uses LIFO (last-in-first-out) ordering which means that the last pushed item to the stack is processed first (all previous items will need to wait until newer are processed).

Base Operations

When to use

• Checking an opening/closing structure. For example, a task to detect balanced usage of opening and closing parentheses, brackets, and quotes. []()""([])

• Undoing (backtracking from) an action.

• Reversing data.

• and more...

Time Complexity

*To access some value you need first to pop an element from the top.

Code

Stack.ts
import { LinkedList } from '../LinkedList/LinkedList';
​
export class Stack<T> {
  private storage = new LinkedList<T>();
​
  public push(value: T): void {
    this.storage.append(value);
  }
​
  public pop(): T | null {
    return this.storage.deleteTail()?.value || null;
  }
​
  public isEmpty(): boolean {
    return !this.storage.getLast();
  }
​
  public peek(): T | null {
    return this.storage.getLast()?.value || null;
  }
​
  public toArray(): T[] {
    return this.storage.toArray();
  }
​
  public toString(callback?: (val: T) => string): string {
    return this.storage.toString(callback);
  }
}

Links:

• ​Linked List record.

• Code on Github.

• Solve problems using Stack on LeetCode.

• ​Big-O Cheat Sheet​

​