STACK

CHAPTER-03
STACK
Data Structure:
A mechanism to store, organize and access data in memory along with
operations that can be performed on the data.

Primitive data structure:

Primitive data structure fundamental basic data types that allow to store
only single data values directly supported by machine level language.

Non-Primitive data structure:

Non-Primitive data structure are complex structures used to store
collections of data, created by programmers using primitive data
structures.

3.2 Stack:
A stack in data structure is a linear collection of items that follows LIFO
principle.
Suma AJ Dept. of Computer Science
 STACK

Operations performed on stack:

1. PUSH: To add a new element to the stack.
In Python, this is typically done using the append() method of a list.
2. POP: To remove an element from the stack.
In Python, this is typically done using the pop() method of a list.
3. PEEK(or TOP): Returns the top element of the stack without removing
it. In Python, this can be done by accessing the last element of the list
using index -1.
Ex:
stack = [1, 2]
top_element = stack[-1]
print(top_element)

Output:
2

4. isEmpty: Checks if the stack is empty. It returns True if the stack is

empty and False otherwise. In Python, this can be done by checking if
the length of the list is 0.
5. Size: Returns the number of elements in the stack. In Python, this can
be done using the len() function on the list.

Additional Operations:
 isFull: Checks if the stack is full. This operation is relevant when a
stack has a defined size limit. Python lists can grow dynamically, this
operation is not typically used, but can be implemented.
 Display: Prints all the elements of the stack, from top to bottom.

Note:
1. Trying to add an element to a full stack result in an exception called
‘overflow’.
2. Trying to delete an element from an empty stack result in an exception
called ‘underflow’.

Suma AJ Dept. of Computer Science

 STACK
3.2.1 APPLICATIONS OF STACK:
 Application of stack in programming are as follows:

 Function calls and Recursion: Stacks are used to keep track of the
return addresses of function calls, allowing the program to return to
the correct location after a function has finished executing.

 String Reverse:Changing the order of its characters so that the last

character becomes the first, and the second to last becomes the
second, and so on.

 Expression evaluation: Stacks are used to evaluate expressions in

postfix notation (Reverse Polish Notation).

 Undo/redo operations in various applications.

 Syntax parsing: Stacks are used to check the validity of syntax in

programming languages and other formal languages.

 Memory management: Stacks are used to allocate and manage

memory in some operating systems and programming languages.

3.4 Implementation of Stack in Python:

Functions:

 #Create an empty stack

glassStack = list()

• #A function named isEmpty to check whether the stack glassStack is

empty or not.

def isEmpty(glassStack):
if len(glassStack)==0:
return True
else:
return False

•#A function named opPush to insert (PUSH) a new element in stack.

def opPush(glassStack,element):
[Link](element)
Suma AJ Dept. of Computer Science
 STACK

• #A function named size to read the number of elements in the

glassStack.

def size(glassStack):
return len(glassStack)

• #A function named top to read the most recent element (TOP) in the
glassStack.

def top(glassStack):
if isEmpty(glassStack):
print('Stack is empty')
return None
else:
x =len(glassStack)
element=glassStack[x-1]
return element

• #A function named opPop to delete the topmost element from the stack.

def opPop(glassStack):
if isEmpty(glassStack):
print('underflow')
return None
else:
return([Link]())

• #A function named display to show the contents of the stack.

def display(glassStack):
x=len(glassStack)
print("Current elements in the stack are: ")
for i in range(x-1,-1,-1):
print(glassStack[i])

Suma AJ Dept. of Computer Science

 STACK
Example program to implement stack operations:

Once we define the above functions we can use the following Python code to
implement a stack of glasses.

glassStack = list() # create empty stack

element='glass1'
print("Pushing element ",element)
opPush(glassStack,element)
element='glass2' #add elements to stack
print("Pushing element ",element)
opPush(glassStack,element)

#display number of elements in stack

print("Current number of elements in stack is",size(glassStack))

element=opPop(glassStack) #delete an element from the stack

print("Popped element is",element)

element='glass3'
print("Pushing element ",element) #add new element to stack
opPush(glassStack,element)

#display the last element added to thestack

print("top element is",top(glassStack))

#display all elements in the stack

display(glassStack)

while True:
item=opPop(glassStack)
if item == None:
print("Stack is empty now") #delete all elements from stack
break
else:
print("Popped element is",item)

Suma AJ Dept. of Computer Science

 STACK
Output:
Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
Underflow
Stack is empty now

Notations for arithmetic expressions:

Algorithm to convert infix to postfix expression:

Step 1: Input infix Expression.

Step 2: Read a character from expression.
Step 3: If character is ‘(‘ or an operator then push character to stack.
Step 4: else append the character to output string.
Step 5: if character is ‘)’, then pop the operators from stack and append to
output string till ‘(‘ is encountered, ignore the popped ‘(‘.
Suma AJ Dept. of Computer Science
 STACK
Step 6: Repeat step 4 to 6 till the end of expression.
Step 7: Pop all the remaining operators and append to output string.

Example: Let us now use this algorithm to convert a given infix expression
(x + y)/(z*8) into equivalent postfix expression using a stack.

Suma AJ Dept. of Computer Science

 STACK

Algorithm to Evaluation of Postfix Notation:

Step1: Store postfix expression in a variable say Exp.

Step2: for each character in exp, Repeat step3.

Step3: If character is an operand, then push character to stack, else pop

two elements & apply the operator on the popped two elements and push
the computed value back to stack.

Step4: If stack has a single element then pop the element and output as the
net result else output “Invalid post fix expression”.

Example: This example shows the step-by-step process of evaluation of the

postfix expression 7 8 2 * 4 / + using Algorithm.

Suma AJ Dept. of Computer Science

 STACK

MCQ’S
1 What is the principle of a stack?
A) FIFO B) LIFO
C) LILO D) FIFS
Answer : B

2 Which operation inserts an element into a stack?

A) pop B) insert
C) push D) append
Answer : C

3 Which operation removes the top element of a stack?

A) delete B) remove
C) pop D) push
Answer : C

4 What happens when a pop operation is performed on an empty stack?

A) Underflow B) Overflow
C) Error 404 D) Memory leak
Answer : A

5 Which data structure is used for recursion?

A) Queue B) Tree
C) Stack D) Linked List
Answer : C

6 Which of the following is not an application of stacks?

A) Undo mechanism B) Backtracking
C) Parsing expressions D) Disk scheduling
Answer : D

7 Which of the following is true about stack?

A) Insertion happens at rear B) Deletion happens at front
C) Insertion and deletion both happen at the top D) None
Answer : C

8 The memory required by a stack depends on:

A) Type of data B) Number of elements
C) Time of use D) Operating system
Answer : B

9 Which condition indicates that a stack is full (in array implementation)?

A) top == 0 B) top == -1
C) top == size - 1 D) top == size + 1
Answer : C

Suma AJ Dept. of Computer Science

 STACK
10 What does the peek() function return?
A) Bottom element B) Middle element
C) Top element D) All elements
Answer : C

11 Stack underflow occurs when:

A) Inserting into a full stack B) Removing from an empty stack
C) Stack is sorted D) Stack is too large
Answer : B

12 Which of these is not a valid stack operation?

A) push B) pop
C) insert D) peek
Answer : C

13 Which of the following can reverse a string?

A) Queue B) Stack
C) Array D) Hash table
Answer : B

14 Which of the following is used for undo features in text editors?

A) Queue B) Stack
C) Heap D) Tree
Answer : B

15 Stack works on which memory concept?

A) Sequential B) Associative
C) Contiguous D) Last-in-first-out
Answer : D

16 What is the output of popping from an empty stack?

A) 0 B) Error/Exception
C) -1 D) Null
Answer : B

17 Which Python list method is used to push elements to a stack?

A) append() B) insert()
C) extend() D) push()
Answer : A

18 Which method refers the top element from a Python list stack?
A) peek( ) B) remove()
C) pop() D) clear()
Answer : A

Suma AJ Dept. of Computer Science

 STACK
19 What is the output of this code? stack = [1, 2, 3]; [Link]()
A) 1 B) 2
C) 3 D) Error
Answer : C

20 How do you check if a stack is empty in Python?

A) len(stack) != 0 B) stack == []
C) not stack D) All of the above
Answer : D

21 Which of the following is not a valid method in Python?

A) pop() B) append()
C) insert(0, x) D) peek()
Answer : D

22 How can you implement peek in a Python stack s?

A) [Link]() B) s[len(s)]
C) s[-1] D) [Link]()
Answer : C

23 What is the output? s = []; [Link](10); [Link](20); [Link]()

A) 10 B) 20
C) None D) Error
Answer : B

24 In Python, What will [Link](0) do?

A) Remove top B) Remove bottom
C) Error D) Remove middle
Answer : B

25 What is the output of: stack = []; [Link](1); print(stack[-1])

A) 0 B) 1
C) Error D) None
Answer : B

26 Which is postfix of (A + B)?

A) AB+ B) A+B
C) +AB D) (A+B)
Answer : A

27 Postfix expression is also called:

A) Prefix B) Infix
C) Polish notation D) Reverse Polish notation
Answer : D

Suma AJ Dept. of Computer Science

 STACK
28 Which of these follows postfix order?
A) Operator between operands B) Operator before operands
C) Operator after operands D) None
Answer : C

29 What is the postfix of A + B * C?

A) ABC*+ B) AB+C*
C) A+BC* D) ABC+
Answer : A

30 Which stack operation is used during postfix evaluation?

A) push B) pop
C) both A & B D) None
Answer : C

31 What is the result of postfix: 2 3 * 5 4 * + ?

A) 17 B) 26
C) 23 D) 30
Answer : A

32 Which of the following is a valid postfix expression?

A) A + B B) AB+
C) +AB D) A + B * C
Answer : B

33 In postfix, which element is processed first?

A) Operator B) Left operand
C) Right operand D) Depends
Answer : B

34 In evaluating 4 2 + 5 *, what is the output?

A) 30 B) 21
C) 16 D) 27
Answer : A

35 What is used to convert infix to postfix?

A) Queue B) Heap
C) Stack D) Tree
Answer : C

36 Which comes first in postfix: operand or operator?

A) Operand B) Operator
C) Both D) None
Answer : A

Suma AJ Dept. of Computer Science

 STACK
37 Postfix of (A + B) * (C + D) is:
A) AB+CD+* B) ABCD++*
C) A+B+C+D* D) AB+CD+
Answer : A

38 Which of the following cannot be evaluated using a stack?

A) Prefix B) Infix
C) Postfix D) All can be
Answer : D

39 What happens when an operator is found in postfix evaluation?

A) It is pushed B) Operands are popped
C) Stack is cleared D) None
Answer : B

40 Postfix notation eliminates the need for:

A) Operands B) Parentheses
C) Operators D) Functions
Answer : B

Suma AJ Dept. of Computer Science