Stack
- Quick summary: a sequential collection where elements are added to and removed from the same end.
- Important facts:
- First-in, last-out (FILO) data structure.
- Equivalent of a real-life pile of papers on desk.
- In stack terms, to insert is to push, and to remove is to pop.
- Often implemented on top of a linked list where the head is used for both insertion and removal. Can also be implemented using dynamic arrays.
- Pros:
- Fast insertions and deletions:
O(1).
- Fast insertions and deletions:
- Cons:
- Access and search are
O(n).
- Access and search are
- Notable uses:
- Maintaining undo history.
- Tracking execution of program functions via a call stack.
- Reversing order of items.
- Time complexity (worst case):
- Access:
O(n) - Search:
O(n) - Insertion (pushing):
O(1) - Deletion (popping):
O(1)
- Access:
- See also:
xxxxxxxxxx33
console.log(newStack);class Stack { constructor() { this.stack = []; } push(item) { return this.stack.push(item); } pop() { return this.stack.pop(); } peek() { return this.stack[this.length - 1]; } get length() { return this.stack.length; } isEmpty() { return this.length === 0; }}const newStack = new Stack();OUTPUT
Results will appear here.