from collections import deque
class Stack:
def __init__(self, data=None):
"""Initialize the stack, optionally converting a data type into a stack."""
self.stack = []
if data is not None:
self.convert_to_stack(data)
def convert_to_stack(self, data):
"""Convert a data type (string, list, tuple, etc.) into a stack."""
if isinstance(data, str):
# If it's a string, treat it as a sequence of characters
self.stack = list(data)
elif isinstance(data, (list, tuple)):
# If it's a list or tuple, directly convert it to a stack
self.stack = list(data)
elif isinstance(data, dict):
# If it's a dictionary, treat it as key-value pairs
self.stack = list(data.items())
elif isinstance(data, set):
# If it's a set, convert it to a list
self.stack = list(data)
else:
# Handle other types of data by converting them into a list
self.stack = [data] # Wrap the data into a list if it's not iterable
print(f"Stack initialized with: {self.stack}")
def push(self, item):
"""Push an item onto the stack."""
self.stack.append(item)
def pop(self):
"""Pop an item from the stack. Returns None if the stack is empty."""
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
"""Peek at the top item of the stack without removing it."""
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
"""Check if the stack is empty."""
return len(self.stack) == 0
def size(self):
"""Return the size of the stack."""
return len(self.stack)
def clear(self):
"""Clear all items in the stack."""
self.stack.clear()
def print_stack(self):
"""Print all elements in the stack."""
print(self.stack)
def reverse_stack(stack):
"""Reverse a stack using recursion."""
if stack.is_empty():
return
top = stack.pop()
reverse_stack(stack)
insert_at_bottom(stack, top)
def insert_at_bottom(stack, item):
"""Helper function to insert an item at the bottom of the stack."""
if stack.is_empty():
stack.push(item)
else:
top = stack.pop()
insert_at_bottom(stack, item)
stack.push(top)
def is_balanced(expression):
"""Check if the parentheses in the expression are balanced."""
stack = Stack()
for char in expression:
if char in '([{':
stack.push(char)
elif char == ')' and (stack.is_empty() or stack.pop() != '('):
return False
elif char == ']' and (stack.is_empty() or stack.pop() != '['):
return False
elif char == '}' and (stack.is_empty() or stack.pop() != '{'):
return False
return stack.is_empty()
def dfs_stack(graph, start):
"""
Perform DFS traversal of a graph using a stack.
:param graph: A dictionary representing the graph (adjacency list).
:param start: The starting node for DFS traversal.
:return: A list of nodes in the order they were visited.
"""
visited = set()
stack = [start]
traversal_order = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
traversal_order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return traversal_order
def bfs_queue(graph, start):
"""
Perform BFS traversal of a graph using a queue.
:param graph: A dictionary representing the graph (adjacency list).
:param start: The starting node for BFS traversal.
:return: A list of nodes in the order they were visited.
"""
visited = set()
queue = deque([start])
traversal_order = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
traversal_order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return traversal_order
def is_palindrome(s):
"""
Check if a string is a palindrome using a stack.
:param s: The string to check.
:return: True if the string is a palindrome, False otherwise.
"""
stack = []
# Push each character onto the stack
for char in s:
stack.append(char)
# Check if the string is a palindrome by comparing characters
for char in s:
if char != stack.pop():
return False
return True
def sort_stack(stack):
"""
Sort a stack using only another stack for auxiliary storage.
:param stack: The stack to be sorted.
:return: The sorted stack.
"""
auxiliary_stack = []
while stack:
current = stack.pop()
# Move elements from auxiliary stack back to stack if they are greater than current
while auxiliary_stack and auxiliary_stack[-1] > current:
stack.append(auxiliary_stack.pop())
# Push the current element to the auxiliary stack
auxiliary_stack.append(current)
# Move all elements back to the original stack
while auxiliary_stack:
stack.append(auxiliary_stack.pop())
return stack
class MinStack:
def __init__(self):
"""
Initialize the stack and the auxiliary stack to keep track of minimum elements.
"""
self.stack = []
self.min_stack = []
def push(self, x):
"""
Push an element onto the stack.
:param x: The element to be pushed onto the stack.
"""
self.stack.append(x)
# Push the minimum element onto the min_stack
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
"""
Pop the top element from the stack.
:return: The popped element.
"""
if self.stack:
popped_value = self.stack.pop()
if popped_value == self.min_stack[-1]:
self.min_stack.pop()
return popped_value
return None
def top(self):
"""
Get the top element of the stack.
:return: The top element of the stack.
"""
return self.stack[-1] if self.stack else None
def get_min(self):
"""
Retrieve the minimum element in constant time.
:return: The minimum element in the stack.
"""
return self.min_stack[-1] if self.min_stack else None
# Example Use Cases
# 1. Test the Stack class
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Stack operations:")
print(stack.peek()) # Output: 30
print(stack.pop()) # Output: 30
print(stack.size()) # Output: 2
stack.print_stack() # Output: [10, 20]
# 2. Test DFS
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("\nDFS traversal:", dfs_stack(graph, 'A')) # Output: ['A', 'C', 'F', 'E', 'B', 'D']
# 3. Test BFS
print("\nBFS traversal:", bfs_queue(graph, 'A')) # Output: ['A', 'B', 'C', 'D', 'E', 'F']
# 4. Test Palindrome Check
print("\nIs 'racecar' a palindrome?", is_palindrome('racecar')) # Output: True
print("Is 'hello' a palindrome?", is_palindrome('hello')) # Output: False
# 5. Test Reversing a Stack
print("\nReversing stack:")
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
reverse_stack(stack)
stack.print_stack() # Output: [3, 2, 1]
# 6. Test Balanced Parentheses
expression = "{[()()]}"
print("\nIs the expression balanced?", is_balanced(expression)) # Output: True
expression = "{[(])}"
print("Is the expression balanced?", is_balanced(expression)) # Output: False
# 7. Test Sorting a Stack
stack = [5, 2, 9, 1, 5, 6]
print("\nSorted stack:", sort_stack(stack)) # Output: [1, 2, 5, 5, 6, 9]
# 8. Test MinStack
min_stack = MinStack()
min_stack.push(3)
min_stack.push(4)
min_stack.push(2)
min_stack.push(5)
print("\nMinStack get_min:", min_stack.get_min()) # Output: 2
min_stack.pop()
print("MinStack get_min after pop:", min_stack.get_min()) # Output: 2
min_stack.pop()
# 1. Test the Stack class with different data types using convert_to_stack
# Test with a string
stack1 = Stack("abcd")
print("\nStack with string 'abcd':")
stack1.print_stack() # Output: ['a', 'b', 'c', 'd']
# Test with a list
stack2 = Stack([1, 2, 3, 4])
print("\nStack with list [1, 2, 3, 4]:")
stack2.print_stack() # Output: [1, 2, 3, 4]
# Test with a tuple
stack3 = Stack((5, 6, 7, 8))
print("\nStack with tuple (5, 6, 7, 8):")
stack3.print_stack() # Output: [5, 6, 7, 8]
# Test with a dictionary (key-value pairs)
stack4 = Stack({'a': 1, 'b': 2, 'c': 3})
print("\nStack with dictionary {'a': 1, 'b': 2, 'c': 3}:")
stack4.print_stack() # Output: [('a', 1), ('b', 2), ('c', 3)]
# Test with a set
stack5 = Stack({9, 10, 11, 12})
print("\nStack with set {9, 10, 11, 12}:")
stack5.print_stack() # Output: [9, 10, 11, 12] (order may vary due to set properties)
# Test with an integer (wrapped in a list for other non-iterable types)
stack6 = Stack(42)
print("\nStack with integer 42 (wrapped as a list):")
stack6.print_stack() # Output: [42]