Stack
Stacks: A stack is linear data structure implemented in LIFO (Last in first out)
manner where insertion and deletion are restricted to occur at one end, i.e.
stack top.
Thus we can say that a stack is a list of data that follows these rules:
1) Data can only be removed from the top. The removal of element from stack
is technically called POP operation.
2) A new data element can only be added at the top of the stack. The insertion
of element in a stack is technically called PUSH operation.
Other stack terms: There are some other terms related to stack such as peek,
overflow and underflow.
Peek: Refers to inspecting the value at the stack top without removing it.
Overflow: Refers to situation when one tries to push an item in stack that is
full.
This situation occurs when the size of stack is fixed.
Underflow: Refers to situation when one tries to pop/delete an item from an
empty stack.
Implementing stack in Python: For various stack operation, we can use a list
say stack and use Python code as described below:
Peek: we can use stack [<top>] where stack is a list and top is an integer value
equal to len(<stack>)-1
Push: We can use : <stack>.append(<value>) where <value> is the item being
pushed in the stack.
Pop: We can use <stack>.pop(). It removes the last value from the stack and
returns it.
Stack Application: There are several application and uses of stacks. The
stacks are basically applied where LIFO scheme is required.
Reversing a line: A simple example of stack application is reversal of given
line.
We can accomplish this task by pushing each character on the stack then
popped of the stack.
Polish string: Polish string, named after a polish mathematician, Jan
Lukasiewicz, refers to the notation in which the operator symbol is placed
either before its operands (prefix notation) or after its operands (postfix
notation) in contrast to usual form where operand is placed between the
operands (infix notation).
e.g.
Infix Prefix Postfix
A+B +AB AB+
(A-C)×B ×-ACB AC-B×
Conversion of infix expression to postfix expression: There is an evaluation
order according to which operation place.
(i) Brackets and parenthesis
(ii) Exponential
(iii) Multiplication or division
(iv) Addition or subtraction
e.g. convert (A+B)×C/D into postfix notation.
Solution: (I) determine the actual evaluation order by putting braces.
((A+B)×C)/D
(II)Converting expression into innermost braces.
((A+B)×C)/D
((AB+)×C)/D
((AB+C)×)/D
((AB+C)×D)/
Evaluation of postfix expression using stacks: Evaluation rule of a
postfix expression states:
1) While reading the expression from left to right, push the element in
the stack if it is operand.
2) pop the two operands from, if the element is operator (Except not
operator)
3) push back the result of the evaluation. Repeat it till the end of the
expression.
Example: Evaluate the postfix expression AB+C×D/
If A=2,B=3,C=4 and D=5
Solution:
2 Push
2 Push ,3 Push
2 Push ,3 Push ,+ Pop
5 ,4 Push
5 ,4 Push ,× Pop
20 ,5 Push
20 ,D Push ,/ Pop
4
#Stack implemented as a list:
def isEmpty(stk):
if(stk==[]):
return True
else:
return False
def push(stk,item):
[Link](item)
top=len(stk)-1
def pop(stk):
if isEmpty(stk):
return "Underflow"
else:
item=[Link]()
if (len(stk)==0):
top=None
else:
top=len(stk)-1
return item
def peek(stk):
if (isEmpty(stk)):
return "Underflow"
else:
top=len(stk)-1
return stk[top]
def display(stk):
if(isEmpty(stk)):
print("Stack Empty")
else:
top=len(stk)-1
print( stk[top],"<- top")
for a in range(top-1,-1,-1):
print (stk[a])