TIL - Today I Learned
Search…
Computer Science
Software Engineering
Personal Development
TIL - Today I Learned
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.
Description
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).
Base Operations
Method
Description
push()Add item to a stack.
pop()Remove item from a stack.
peek()Get the latest item in a stack.
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
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.
Code
Stack.ts
1
import { LinkedList } from '../LinkedList/LinkedList';
2
3
export class Stack<T> {
4
private storage = new LinkedList<T>();
5
6
public push(value: T): void {
7
this.storage.append(value);
8
}
9
10
public pop(): T | null {
11
return this.storage.deleteTail()?.value || null;
12
}
13
14
public isEmpty(): boolean {
15
return !this.storage.getLast();
16
}
17
18
public peek(): T | null {
19
return this.storage.getLast()?.value || null;
20
}
21
22
public toArray(): T[] {
23
return this.storage.toArray();
24
}
25
26
public toString(callback?: (val: T) => string): string {
27
return this.storage.toString(callback);
28
}
29
}
Copied!
Links:
Last modified 1yr ago
Copy link