Stack and queue are fundamental data structures with two core operations: push (insert) and pop (remove). They differ in the order in which elements are removed.
- Stack follows LIFO (Last-In-First-Out).
- Queue follows FIFO (First-In-First-Out).
Stack
The last element pushed is the first one popped. Therefore, a stack reverses the insertion order when popping.
Queue
The first element enqueued is the first one dequeued. Therefore, a queue preserves the insertion order when popping.
Complexity
Using a linked list with a tail pointer (List 2) for both stack and queue gives $O(1)$ push and pop, since we already have $O(1)$ insert and delete at both ends.
| Time complexity | Stack | Queue |
|---|---|---|
| Insert | $O(1)$ | $O(1)$ |
| Pop | $O(1)$ | $O(1)$ |
| Space complexity | $O(n)$ | $O(n)$ |