Data Structure Laboratory
Experiment no.9
Title
Implementation of a Menu-Driven Program for Array-Based Stack Operations on Integers.
Objective
To implement a Stack of Integers using an Array Implementation in Python, including the core
operations (Push, Pop, Display), demonstrating Overflow and Underflow conditions, and
showcasing a practical application, such as checking for a Palindrome.
Problem Statement
Design and implement a menu-driven program in Python for a stack of integers with a maximum
size (MAX). The program must provide the following operations:
a) Push an Element onto the Stack
b) Pop an Element from the Stack
c) Demonstrate how Stack can be used to check Palindrome
d) Demonstrate Overflow and Underflow situations on Stack
e) Display the status of Stack
f) Exit
Theory Concept in Brief
A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. This means
the last element added to the stack is the first one to be removed.
* Array Implementation: In an array-based stack, a fixed-size array stores the elements, and a
variable (often called top) tracks the index of the topmost element.
* Push: The operation to insert an element onto the top of the stack. An Overflow condition
occurs if an attempt is made to push an element onto a full stack.
* Pop: The operation to remove the topmost element from the stack. An Underflow condition
occurs if an attempt is made to pop an element from an empty stack.
* Palindrome Check: A stack can be used to check if a string or number sequence is a
palindrome (reads the same forwards and backward). The process involves pushing the first
half of the sequence onto the stack and then comparing the elements popped from the stack
with the second half of the sequence.
Algorithm
* Initialize an array (the stack) with a maximum size \text{MAX} and set a \text{TOP} pointer to
-1 (indicating an empty stack).
* PUSH(element):
a. If \text{TOP} == \text{MAX} - 1, report Overflow.
b. Else, increment \text{TOP} and set \text{Stack}[\text{TOP}] = \text{element}.
* POP():
a. If \text{TOP} == -1, report Underflow and return an error value.
b. Else, store \text{element} = \text{Stack}[\text{TOP}], decrement \text{TOP}, and return
\text{element}.
* IS_PALINDROME(sequence):
a. Push all characters/elements of the sequence onto a temporary stack.
b. Pop elements one by one from the stack and build a reversed sequence.
c. Compare the original sequence with the reversed sequence.
* DISPLAY():
a. If \text{TOP} == -1, print "Stack is Empty."
b. Else, print the elements from \text{Stack}[0] up to \text{Stack}[\text{TOP}].
Code (Python)
# Set the maximum size for the stack
MAX_SIZE = 5
# Initialize the stack array and the top pointer
stack = []
top = -1
# a) Push an Element onto Stack
def push(item):
global top
if top == MAX_SIZE - 1:
print("STACK OVERFLOW: Cannot push element,", item, "- Stack is full.")
return
[Link](item)
top += 1
print(f"Pushed {item} onto stack.")
# b) Pop an Element from Stack
def pop():
global top
if top == -1:
print("STACK UNDERFLOW: Cannot pop element - Stack is empty.")
return None
item = [Link]()
top -= 1
print(f"Popped {item} from stack.")
return item
# c) Demonstrate how Stack can be used to check Palindrome
def check_palindrome(sequence):
# Palindromes are usually checked on strings, so we convert input to a string
s = str(sequence).lower().replace(" ", "")
temp_stack = []
# Push all characters onto the stack
for char in s:
temp_stack.append(char)
reversed_s = ""
# Pop all characters to form the reversed string
while temp_stack:
reversed_s += temp_stack.pop()
print(f"\nOriginal Sequence: '{s}'")
print(f"Reversed Sequence: '{reversed_s}'")
if s == reversed_s:
print("The sequence IS a Palindrome. ")
else:
print("The sequence IS NOT a Palindrome.")
# d) Demonstrate Overflow and Underflow situations (already handled in push/pop, but shown
explicitly)
def demonstrate_overflow_underflow():
print("\n--- Demonstration of Overflow/Underflow ---")
# Underflow Demonstration
print("Trying to POP from an empty stack:")
pop()
# Fill the stack to demonstrate Overflow
print("\nFilling the stack to MAX_SIZE:", MAX_SIZE)
for i in range(1, MAX_SIZE + 1):
push(i * 10)
# Overflow Demonstration
print("Trying to PUSH one more element (60):")
push(60)
print("--- End of Demonstration ---")
# e) Display the status of Stack
def display():
print("\nStack Status:")
if top == -1:
print("Stack is empty.")
else:
print(f"Stack elements (Top -> Bottom): {stack[::-1]}")
print(f"Top index: {top}, Size: {len(stack)}")
def menu():
print("\n==============================")
print("STACK OPERATIONS MENU (MAX_SIZE = 5)")
print("==============================")
print("a) Push Element")
print("b) Pop Element")
print("c) Check Palindrome")
print("d) Demonstrate Overflow/Underflow")
print("e) Display Stack Status")
print("f) Exit")
# Main menu-driven loop
while True:
menu()
choice = input("Enter your choice (a-f): ").lower()
if choice == 'a':
try:
element = int(input("Enter integer element to push: "))
push(element)
except ValueError:
print("Invalid input. Please enter an integer.")
elif choice == 'b':
pop()
elif choice == 'c':
seq = input("Enter a sequence (e.g., a number or a word) to check for Palindrome: ")
check_palindrome(seq)
elif choice == 'd':
demonstrate_overflow_underflow()
elif choice == 'e':
display()
elif choice == 'f':
print("Exiting program. Goodbye! ")
break
else:
print("Invalid choice. Please enter a letter from 'a' to 'f'.")
Conclusion
The experiment successfully implemented the menu-driven program for Array-Based Stack
Operations in Python. The program accurately executed the Push and Pop operations, correctly
handling the Overflow and Underflow boundary conditions. The stack's LIFO property was
effectively used to check if a sequence is a Palindrome.
