Python Data Structures – Stack

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:

1. 1. Push i.e., Insertion of element in the stack
   2. Pop i.e., Deletion of an element from the stack
   3. Peek i.e., viewing topmost element without removing it
   4. 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.

Q. 5 What are the two major stack operations?
Ans. The two operations performed on the stack are:

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

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

Q.7 Difference between Stack and Queues
Ans.

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.

1. 1. Scan the infix expression from left to right.
   2. If the scanned character is an operand, output it.
   3. 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.)

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

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

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)

Ans. Output ABCD-*E/+

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

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)

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, – , + , *

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)

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