Stack
A Stack is a linear data structure that keeps its elements stacked on each other. It uses LIFO (last-in-first-out) ordering in which the last pushed item to the stack is processed first.
Stack Data Structure
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).
Method | Description |
push() | Add item to a stack. |
pop() | Remove item from a stack. |
peek() | Get the latest item in a stack. |
- 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...
Operation | Complexity |
Insertion | O(1) |
Deletion | O(1) |
*Access | O(n) |
*To access some value you need first to pop an element from the top.
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);
}
}
Last modified 2yr ago