Abstract Data Type

Stack (LIFO)

In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy.

Basic Operations

• push(val) - adds an element to the top of the stack
• pop() - removes the element at the top of the stack
• peek() - checks the top element without removing
• isEmpty() - returns true or false depending if the stack is empty

Implementation

You can implement a stack using a Linked List, C++ Vector or Deque.

• Linked List Implementation → $O(1)$ time
  • Have the head be the only place for insertion and removal
• Dynamic Array Implementation → $O(1)$ time
  • Append and remove from back of array

Language-Specific

Both Python and Stack implement a stack using a Deque.

Python

from collections import deque
 
stack = deque()
stack.push(2)
stack.push(3)
stack.pop()
 
d.get() # Top element
d.qsize() # size of stack
d.empty() # IsEmpty is FALSE

C++

stack<int> s;
s.push(3);
s.push(2);
s.push(5);
cout << s.top(); // 5
s.pop();
cout << s.top(); // 2

Stack vs. Queue (memory trick)

https://www.youtube.com/watch?v=2wM6_PuBIxY&ab_channel=CS50 This video above helped me remember the difference between a stack and a queue.