# Python Data Structures – Stack

- Categories Uncategorized

In this post we will cover Stack Data Structure in Python. You can watch our videos on Stack in Python – Click Here

**Q. 1 What is a Data-Structure?**

**Ans.**

- A data-structure is a logical way for organizing data in memory that considers not only items stored but also the relationship among the items so as to give efficient and optimal performance.
- In other words, it is a way of organizing data such that it can be used efficiently

**Q. 2 What is a stack? What basic operations can be performed on them?**

**Ans.**

- Stack is a basic data-structure where insertion and deletion of data takes place at one end called the top of the stack i.e., it follows the Last In-First Out(LIFO) principle
- In Python, a stack is generally implemented with lists.
- Following basic operations can be performed on stacks:

**Push**i.e., Insertion of element in the stack**Pop**i.e., Deletion of an element from the stack**Peek**i.e., viewing topmost element without removing it**Display**or view all the elements in the stack.

**Q. 3 Enlist some applications of stack.Ans.** Because of LIFO property of stacks, these are used in various applications like :

- reversal of a sequence,
- Infix to Postfix conversion, O
- Postfix and prefix expression evaluation, and many more.

**Q. 4 What is overflow and underflow situation? Or What is difference between them?**

**Ans.**

Overflow | underflow |
---|---|

Overflow refers to when one tries to push an item in stack that is full | Underflow refers to when one tries to POP/delete an item from an empty stack |

This situation occurs when the size of the stack is fixed and cannot grow further or there is no memory left to accommodate new item | This situation is when the stack is empty and still one tries to pop/delete an item |

**Q. 5 What are the two major stack operations?**

**Ans.**The two operations performed on the stack are:

**Push:**Adding (inserting) new element on to the stack.**Pop:**Removing (deleting) an element from the stack.

**Q. 6 Difference between Simple Data and Compound Data Structures.**

**Ans.**

Simple Data Structure | Compound Data Structure |
---|---|

Data structures built from primitive data types | Data structures built from non-primitive data types |

e.g. integers, float, characters, boolean | e.g. arrays, list, Tuple, Dictionary,set,file |

**Q.7 Difference between Stack and QueuesAns.**

Working principle | LIFO (Last in First out) | FIFO (First in First out) |
---|---|---|

Structure | Same end is used to insert and delete elements. | One end is used for insertion, i.e., rear end and another end is used for deletion of elements, i.e., front end. |

Number of pointers used | One | Two (In simple queue case) |

Operations performed | Push and Pop | Enqueue and dequeue |

Examination of empty condition | Top == -1 | Front == -1 || Front == Rear + 1 |

Examination of full condition | Top == Max – 1 | Rear == Max – 1 |

Variants | It does not have variants | It has variants like circular queue, priority queue, doubly ended queue. |

Implementation | Simpler | Comparatively complex |

**Q. 8 What is Polish String?**

**Ans.**Polish String refers to the notation in which the operator symbol is placed either before its operands (prefix or after its operands(postfix)

**Q. 9 Algorithm for Infix to Postfix.**

**Ans.**

- Scan the infix expression from left to right.
- If the scanned character is an operand, output it.
- Else,

**3.1** If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.

** 3.2** Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

- If the scanned character is an ‘(‘, push it to the stack.
- If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.
- Repeat steps 2-6 until infix expression is scanned.
- Print the output
- Pop and output from the stack until it is not empty.

**Q. 10 What is the ****Operator Precedence in stack.**

**Ans.**

Operators | Meaning |
---|---|

() | Parentheses |

** | Exponent |

+x, -x, ~x | Unary plus, Unary minus, Bitwise NOT |

*, /, //, % | Multiplication, Division, Floor division, Modulus |

+, – | Addition, Subtraction |

<<, >> | Bitwise shift operators |

& | Bitwise AND |

^ | Bitwise XOR |

| | Bitwise OR |

!ERROR! illegal character ‘!’ | Comparisions, Identity, Membership operators |

not | Logical NOT |

and | Logical AND |

or | Logical OR |

**Q. 11 Write a algorithm for Postfix evaluation.**

**Ans.**

1) Create a stack to store operands (or values).

2) Scan the given expression and do following for every scanned element.

a) If the element is a number, push it into the stack

b) If the element is a operator, pop operands for the operator from stack.

Evaluate the operator and push the result back to the stack

3) When the expression is ended, the number in the stack is the final answer

**Q. 12 Convert the following infix expression to its equivalent postfix expression. Showing stack contents for the conversion(A+B*(C-D) /E).**

**Ans. Let us rewrite like(A+B*(C-D) / E)**

Scanned Elements | Operation | Stack Status |
---|---|---|

( | ( | |

A | ( | A |

+ | ( + | A |

B | ( + | A B |

* | ( + * | A B |

( | ( + * ( | A B |

C | ( + * ( | A B C |

– | ( + * ( – | A B C |

D | ( + * ( – | A B C D |

) | ( + * | A B C D – |

/ | ( + / | A B C D – * |

E | ( + / | A B C D – * E |

) | A B C D – * E / + |

**Ans.** Output ABCD-*E/+

**Q. 13 Evaluate the following postfix notation of expression :** 20, 10, +, 5, 2, * , – ,10, /

Scanned Elements | Operation | Stack Status |
---|---|---|

20 | Push | 20 |

10 | Push | 20,10 |

+ | Pop twice 10+20=30 Push | 30 |

5 | Push | 30,5 |

2 | Push | 30,5,2 |

* | Pop twice 5*2=10 Push | 30 30,10 |

– | Pop twice 30-10=20 Push | 20 |

10 | Push | 20,10 |

/ | Pop twice 20/10=2 Push | 2 |

**Ans.** Output 2

**Q. 14 Obtain the postfix notation for the following infix notation of expression showing the contents of the stack and postfix expression formed after each step of conversion.** A*B +(C-D/F)

Scanned Elements | Operation | Stack Status |
---|---|---|

( | ( | |

A | ( | A |

* | (* | A |

B | (* | AB |

+ | (+ | AB* |

( | (+ ( | AB* |

C | (+ ( | AB*C |

– | (+ (- | AB*C |

D | (+ (- | AB*CD |

/ | (+ (- / | AB*CD |

F | (+ (- / | AB*CDF |

) | (+ | AB*CDF/- |

) | AB*CDF/- + |

Let us rewrite like (A*B +(C-D/F))

**Ans.** Output AB*CDF/-+

**Q. 15 Evaluate the following postfix expression using stack and show the contents of stack after execution of each expression**

**120, 45, 20, + , 25, 15, – , + , ***

Scanned Elements | Operation | Stack Status |
---|---|---|

120 | Push | 120 |

45 | Push | 120,45 |

20 | Push | 120,45,20 |

+ | Pop twice 45+20=65 Push | 120,65 |

25 | Push | 120, 65, 25 |

15 | Push | 120,65,25,15 |

– | Pop Twice 25-15=10 Push | 120, 65, 10 |

+ | Pop Twice 65+10=75 Push | 120,75 |

* | Pop twice 120*75=9000 Push | 9000 |

**Ans. Output 9000**** **

**Q. 16 Change the following infix expression into postfix expression(A+B)*C + D/E –F**

**Ans. Let us rewrite like(( A+B)*C+D/E-F)**

Scanned Elements | Operation | Stack Status |
---|---|---|

( | ( | |

( | (( | |

A | (( | A |

+ | ((+ | A |

B | ((+ | AB |

) | ( | AB+ |

* | (* | AB+ |

C | (* | AB+C |

+ | (+ | AB+C* |

D | (+ | AB+C*D |

/ | (+ / | AB+C*D |

E | (+ / | AB+C*DE |

– | (- | AB+C*DE/+ |

F | (- | AB+C*DE/+F |

) | AB+C*DE/+F- |

**Ans.** Output AB+C*DE/+F-

**Q. 17 Write a program to implement a stack for these book-details (bookno, book name). That is, now each item node of the stack contains two types of information- bookno and its name. Just implement push and display**

**Ans.**

def isEmpty(stk): if stk==[]: return True else: return False

def Push(stk,item): stk.append(item) top=len(stk)-1 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]) Stack=[] top=None while True: print("select stack operation:") print("1.Push") print("2.Display stack") print("3.Exit") ch=int(input("enter your choice:")) if ch==1: BookNo=int(input"Enter bookno: )) BookName= input("Enter book name: ) item=(BookNo,BookName) Push(Stack,item) elif ch==2: Display(Stack) elif ch==3: break else: print("Invaild choice!")

**Q. 18 Python Program to implement stack operations**

**Ans. Stack Operations:**

def isEmpty(stk):

if stk==[]:

return True

else:

return False

def Push(stk,item):

stk.append(item)

top=len(stk)-1

def Pop(stk):

if isEmpty(stk):

return "underflow"

else:

item=stk.pop()

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])

Stack=[]

top=None

while True:

print("stack operations")

print("1.Push")

print("2.pop")

print("3.Peek")

print("4.Display stack")

print("5.Exit")

ch=int(input("enter your choice(1-5):"))

if ch ==1:

item=int(input("Enter item:"))

Push(Stack,item)

elif ch==2:

item= Pop(Stack)

if item=="Underflow":

print("Stack is empty!")

else:

print("popped:", item)

elif ch==3:

item=Peek(Stack)

if item =="underflow":

print("Stack is empty!" )

else:

print("top: ",item)

elif ch==4:

Display(Stack)

elif ch==5:

break

else:

print("Invaild choice!")

**output**

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):1

Enter item:5

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):1

Enter item:15

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):1

Enter item:20

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):2

popped item is 20

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):3

topmost item is 15

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):4

15 <-top

5

Select stack operation:

1.Push

2.pop

3.Peek

4.Display stack

5.Exit

enter your choice(1-5):5