Chapter 3. Stack#
A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations:
push, which adds an element to the collection, and
pop, which removes the last element that was added.
In stack both the operations of push and pop take place at the same end that is top of the stack. It can be implemented by using both array and linked list.
Stacks are used for maintaining function calls (the last called function must finish execution first), we can always remove recursion with the help of stacks.
Stacks are also used in cases where we have to reverse a word, check for balanced parenthesis, and in editors where the word you typed the last is the first to be removed when you use undo operation. Similarly, to implement back functionality in web browsers.
Stack in Python#
There are three ways to implement stack in python:
list
collections.deque
queue.LifoQueue
List#
Using dynamic array list to implement stack can directly take use of the built-in method append() and pop to implement push and pop for stack.
The shortcomings:
listis a dynamic array.insertionanddeletionat the end only takeO(1)time, but when the allocated memoery is not enough when do the inseration at the end, new memory will be allocated. This will take a long time if the stack is big enough.
stack = []
stack.append(1) # push
stack.pop() # pop
1
collection.deque#
Python collection.deque is a generailization of stacks and queues, and its name is short for double-ended queue. Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
from collections import deque
stack = deque()
stack.append(1)
stack.pop()
1
queue.LifoQueue#
from queue import LifoQueue
stack = LifoQueue(maxsize=1)
print(stack.qsize()) # check size
stack.put(1) # push
print(stack.qsize()) # check size
stack.get() # pop
0
1
1
Linked List#
We implement a stack using linked list here.
class Node():
def __init__(self, val, next = None):
self.val = val
self.next = next
class Stack():
# initialize a stack
# use a dummy node
def __init__(self):
self.head = Node('head')
self._size = 0
# get current size
def size(self):
return self._size
# check if is empty
def isEmpty(self):
return self._size == 0
# push a value into the stack
def push(self, val):
node = Node(val)
# add to head
tail = self.head.next
self.head.next = node
node.next = tail
# update size
self._size += 1
# pop the last added element
def pop(self):
if self.isEmpty():
raise Exception("Poping from an empty stack !")
tail = self.head.next.next
removed = self.head.next
self.head.next = tail
# update size
self._size -= 1
return removed.val
# string representation of current stack
def __str__(self):
cur = self.head.next
out = ""
while cur:
out += str(cur.val) +'->'
cur = cur.next
return out
# test
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(f"stack: {stack}")
stack.pop()
stack.pop()
print(f"stack: {stack}")
stack: 3->2->1->
stack: 1->
Special Stack#
The above stack are standard stack structure, which can easily perform standard operations such as push, pop and size.
For special operations, such as getMiddle, popMiddle, special stacks are needed.
how to implement a stack that will support the following operations in O(1) time complexity:
push()
pop()
findMiddle(), which will return the middle element of the stack
deleteMiddle(), which will delete the middle element of the stack
Method 1: Double Linked List#
The important question is, whether to use a linked list or array for the implementation of the stack?
Please note that we need to find and delete the middle element. Deleting an element from the middle is not O(1) for the array. Also, we may need to move the middle pointer up when we push an element and move down when we pop(). In a singly linked list, moving the middle pointer in both directions is not possible.
The idea is to use a Doubly Linked List (DLL). We can delete the middle element in O(1) time by maintaining mid pointer. We can move the mid pointer in both directions using previous and next pointers.
Following is implementation of push(), pop() and findMiddle() operations. If there are even elements in stack, findMiddle() returns the second middle element. For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 3.
class DLLNode():
def __init__(self, val, prev = None, next = None):
self.prev = prev
self.val = val
self.next = next
class Stack():
def __init__(self):
self.head = None
self.mid = None
self.size = 0
def push(self, val):
# construct node
node = DLLNode(val)
# push to head: the prev is always None
if not self.head:
# assign node to head if head is none
self.head = node
else:
# put node in front of head
self.head.prev = node
node.next = self.head
# update size
self.size += 1
# update middle pointer
# 1. if stack is empty
# 2. number of nodes is odd
if not self.mid:
self.mid = node
if self.size > 0 and (self.size % 2 == 0):
self.mid = self.mid.prev
# update head
self.head = node
def pop(self):
removed = self.head
tail = self.head.next
tail.prev = None
# update mid pointer
if self.size % 2 == 0:
self.mid = self.mid.next
# update head
self.head = tail
# update size
self.size -= 1
return removed.val
# find middle
def findMiddle(self):
return self.mid.val
# remove middle
def popMiddle(self):
mid = self.mid
# remove mid by connecting prev and next
prev = mid.prev
next = mid.next
prev.next = next
next.prev = prev
# update mid pointer
if self.size % 2 == 0:
self.mid = next
else:
self.mid = prev
# update size
self.size -= 1
return mid.val
# string representation
def __str__(self):
cur = self.head
out = "-"
while cur:
out += str(cur.val) + '-'
cur = cur.next
return out
# test
stack = Stack()
stack.push(1)
print(stack.mid.val)
stack.push(2)
print(stack.mid.val)
stack.push(3)
print(stack.mid.val)
stack.push(4)
stack.push(5)
print(stack.mid.val)
print(f"stack: {stack}")
stack.pop()
print(stack.mid.val)
stack.pop()
print(stack.mid.val)
print(f"stack: {stack}")
# pop middle
print(stack.popMiddle())
print(stack.mid.val)
print(f"stack: {stack}")
1
2
2
3
stack: -5-4-3-2-1-
3
2
stack: -3-2-1-
2
3
stack: -3-1-
Method 2: Use a standard stack and a deque#
We will use a standard stack to store half of the elements and the other half of the elements which were added recently will be present in the deque.
Standard Problems on Stack#
Infix, Prefix, and Postfix Expression#
How do computers deal with math equation expressions, such as a + b*c + d?
Some Preliminary
Operator and Operand: operator is the math manipulation of operands.
+,*are operators, anda, b, c, dare operands. One special operand is the parentesis group. An expression enclosed in parentheses is typically recursively evaluated to be treated as a single operand on the next evaluation level.Properties of operator
Each operator is given a position, precedence, and an associativity.
Position: an operator may be prefix, postfix or infix.
Prefix: a prefix operator immediately precedes its operand, as in
-x.Postfix: a postfix operatpr immediately succcedes its operand, as in
x!.Infix: an infix operator is positioned in between a left and a right operand.
Precedence:
which operator takes an operand that is surrounded by two operators of different precedence or priority
e.g., multipication has higher priority than addition
Associativity: associativity is only needed when the operators surrounding a operand have the same precedence.
left associativity:
+,-,*,/are usually left-associative, which means evaluation should be from left to righte.g.,
7 - 4 + 2 = (7 - 4) + 2 = 5. if use right associtivity, the expression will lead to 7 - (4 + 2) = 1.
right associativity:
exp,assignmentandfunction evaluationare usually right-associativee.g.,
5^2^3 = 5^(2^3)
-
The connection between operators and operands
Infix expression: an operators is
in-betweenevery pair of operands, e.g.,a * (b+c) - deasy for humand to understand
Postfix expression: an operator follows every pair of operands, e.g.,
abc+*d-no parenthesis is needed
precedence and associativity disappear, which makse it easy for computer to process
operations are performed in the order in which thery written
compiler evaulation algorithm
scan the expression, left to right,
when you encounter an operand, push it on the stack
when your encounter an operator
@, pop the corresponding operands off the stackperform the operation
@. The operands precede the operator:bc+ = b+c.push the computed result back on the stack
repeat the process untill no more operators
Prefix expression: an operator precedes every pair of operands, e.g,
-*a+bcdprecedence and associativity disappear, which makse it easy for computer to process
prefix notation has more overheads of parenthesis compared with postfix
How to convert infix to postfix ?
initiate a stack
scan the infix, left to right
if the scanned character is an operand, output it
else
if the precedence and associativity of the scanned operator are greater than the precedence and associativity of the top operator in the stack, or the stack has a left parenthesis
(, then push it to the stackelse, pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. Then push the scanned operator to the stack.
special: if encoutering a parathesis during popping, then stop there and push the scanned operator in the stack
if the scanned character is a
(, push it to the stackif the scanned charecter is a
), pop the stack and output it until a(is encountered. Discard both parentheses.repeat till the infix is scanned
class Conversion():
def __init__(self):
self.precedence={'+': 0, '-':0, "*":1, "/":1, "^":2}
# check if a given character is an operand
def isOperand(self, ch):
return ch.isalpha()
# conver from infix expr to postfix expr
def infixToPostfix(self, expr):
# initialize a stack and output
stack = []
output = []
# scan the expr
for s in expr:
# if is an operand, store to output
if self.isOperand(s):
output.append(s)
# if "("
elif s == '(':
stack.append(s)
# if ")", the pop all elements in the stack until "(" is met
elif s == ')':
so = stack.pop()
while len(stack) > 0 and so != '(':
output.append(so)
so = stack.pop()
# else an operator is met
else:
# if scanned operator has no greater precedence over the top operator in the stack, then output
while len(stack)>0 and ((stack[-1] != '(') and (self.precedence[s] <= self.precedence[stack[-1]])):
so = stack.pop()
if so != '(' and so != ')':
output.append(so)
stack.append(s)
while stack:
output.append(stack.pop())
return output
# test
expr = "a+b*c-d"
c = Conversion()
print(c.infixToPostfix(expr))
expr = "a-b*(c+d)"
c = Conversion()
print(c.infixToPostfix(expr))
expr = "a+b*(c^d-e)^(f+g*h)-i"
c = Conversion()
print(c.infixToPostfix(expr))
['a', 'b', 'c', '*', '+', 'd', '-']
['a', 'b', 'c', 'd', '+', '*', '-']
['a', 'b', 'c', 'd', '^', 'e', '-', 'f', 'g', 'h', '*', '+', '^', '*', '+', 'i', '-']
Stock Span Problem#
The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of the stock’s price for all n days.
The span Si of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than its price on the given day.
Examples
Input: N = 7, price[] = [100 80 60 70 60 75 85]
Output: 1 1 1 2 1 4 6
Explanation: Traversing the given input span for 100 will be 1, 80 is smaller than 100 so the span is 1, 60 is smaller than 80 so the span is 1, 70 is greater than 60 so the span is 2 and so on. Hence the output will be 1 1 1 2 1 4 6.
Input: N = 6, price[] = [10 4 5 90 120 80]
Output:1 1 2 4 5 1
Explanation: Traversing the given input span for 10 will be 1, 4 is smaller than 10 so the span will be 1, 5 is greater than 4 so the span will be 2 and so on. Hence, the output will be 1 1 2 4 5 1.
Analysis
this is very similar to the next question to find the index of the previous cloest greater element
algorithm:
initiate a stack to store the index of the traversed value, a span with -1 to store the span value for each element
traverse from left to right
if the stack s is empty, then push current index to the stack
if the current value < the value at the top index of the stack s, then previous closest greater value for current index is met. We can simply get the difference between these two indexes to get the span.
push the current index to stack
if the current value > the value at the top inddex of the stack s
pop the stack until the current value < the value at the top index of the stack s or the stack is empty
calculate the span based on index
push the current index to the stack
def calculateSpan(price):
n = len(price)
span = [1]*n
# maintain a stack s to store the index of the closest element in the price before current index
s = [0]
for i in range(1, n):
while len(s) > 0 and price[s[-1]] <= price[i]:
s.pop()
if len(s) == 0:
span[i] = i + 1
else:
span[i] = i - s[-1]
# push the element to stack
s.append(i)
return span
# test
price = [100, 80, 60, 70, 60, 75, 85]
print(calculateSpan(price))
price = [10, 4, 5, 90, 120, 80]
print(calculateSpan(price))
[1, 1, 1, 2, 1, 4, 6]
[1, 1, 2, 4, 5, 1]
Check for Blanced Parentheses#
Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.
def isBalanced(expr):
stack = []
pairs = {')':'(', '}':'{', ']':'['}
left = ['(', '{', '[']
for c in expr:
if c in left:
stack.append(c)
else:
if len(stack)>0 and pairs[c] == stack[-1]:
stack.pop()
else:
return False
return True
# test
expr = "[()]{}{[()()]()}"
print(isBalanced(expr))
expr = "[(])"
print(isBalanced(expr))
True
False
Next Greater Element in an array#
The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1.
For example, for arry [1, 12, 10, 5], the results should be [12, -1, -1, -1].
The brute force implementation is iteratively check elements between [i, len(arr)], which is \(0(N^2)\) in time.
We can use a stack to reduce the time complexity to \(O(N)\) but increase the space complexity to \(O(N)\).
traverse from the end of the array to the starting
if the current pointer is no greater than the topmost element in the stack
then the next greater of the current pointer is the topmost element in the stack
push current pointer to the stack
else
pop the stack until the topmost elemenet in the stack is greater than the current pointer or the stack is empty
the topmost element is the next greater for the current pointer
push the current pointer to the stack
def nextGreaterElement(array):
n = len(array)
stack = []
out = array
# reverse traversal
for i in range(n-1, -1, -1):
curr = array[i]
# if current element is smaller than the topmost element in the stack
if len(stack) > 0 and curr < stack[-1]:
out[i] = stack[-1]
stack.append(curr)
else:
# pop the stack untill a greater element at the top of the stack or untill the stack is empty
while stack and stack[-1] <= curr:
stack.pop()
if len(stack) == 0:
out[i] = -1
else:
out[i] = stack[-1]
stack.append(curr)
return out
# test
array = [1, 12, 10, 5]
print(nextGreaterElement(array))
array = [4, 12, 5, 3, 1, 2, 5, 3, 1, 2, 4, 6]
print(nextGreaterElement(array))
[12, -1, -1, -1]
[12, -1, 6, 5, 2, 5, 6, 4, 2, 4, 6, -1]
Reverse a Stack#
# Reverse a stack with recursion O(n) time O(n) space
def reverseStack(s):
if len(s) == 0:
return []
lastEle = s.pop()
rev = reverseStack(s)
return [lastEle] + rev
# test
stack = list(range(0,5))
print(reverseStack(stack))
[4, 3, 2, 1, 0]
# reverse a stack in O(1) extra space
# the idea is to use linked list