Stacks
By Naveen
What is a stack?
A stack is called a last-in-first-out (LIFO) collection. This means that the last thing we added (pushed) is the first thing that gets pulled (popped) off.
Examples of stack
Stack operations
- push - add an item to the top of the stack
- pop - remove an item from the top of the stack
- peek - look at the top item in the stack
push and pop are the most common operations
Algorithm for push
push(item)
- add item to the top of the stack
- Precondition: Stack has been initialized and is not full.
- Postcondition: Stack has one more item and item is at the top
push(item) is O(1)
Algorithm for pop
pop()
- Removes item from stack and returns it in item.
- Precondition: Stack has been initialized and is not empty.
- Postcondition: Stack has one less item and item is no longer in the stack.
pop() is O(1)
Stack operations
Implementing a Stack
There are two ways we can implement a stack:
- Using an array
- Using a linked list
Implementing a Stack
Implementing a stack using an array
- The bottom of the stack is at
data[0] - The top of the stack is at
data[numItems-1] - push onto the stack at
data[numItems] - pop off of the stack at
data[numItems-1]
Implementing a Stack
Implementing a stack using a linked list
- Store the items in the stack in a linked list
- The top of the stack is the head node, the bottom of the stack is the end of the list
- push by adding to the front of the list
- pop by removing from the front of the list
