Stack
works by
LIFO : Last-In-First-Out
in other words FILO : First-In-Last-Out
all insertion and deletion done from one end called top of the stack
Main operation
1. Push => insert item at the top
2. Pop => return the item at the top then removes it
3. Top/Peek => return the item at the top
We can implement stack on arrays & Linked lists
Array
top = -1
maxSize = 10 (for example)
data-type []stack = new data-type [maxSize]
push(x) {
if(top == maxSize -1) {
print("Stack overflow")
} else{
top++
stack[top] = x
}
}
pop() {
if(top==-1) print("Stack underflow)
else{
temp = stack[top]
top--
return temp
}
}
top() {
return stack[top]
}
Some limitations and problems
stack overflow (when push): stack is full (because it is fixed size)
stack underflow (when pop / top) : stack is empty
if we maximized the stack size then we will have waste of memory
Linked List
top = null
push(x) {
newNode
[Link] = x
[Link] = top
top = newNode
}
pop() {
if(top == null) print("stack underflow")
else {
temp = top
top = [Link]
return [Link]
}
}
top() {
if(top==null) print("stack underflow)
else return [Link]
}
Applications
1. Recursion
2. Undo operations
3. Checking balanced parentheses
4. reverse any order of a list