# Stack (6 Programs)
# Program 1: Implement Stack using Two Queues
# ---------------------------------------------
from collections import deque
class Stack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x):
self.q1.append(x)
def pop(self):
if not self.q1:
return None
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
popped_element = self.q1.popleft()
self.q1, self.q2 = self.q2, self.q1
return popped_element
def top(self):
if not self.q1:
return None
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
top_element = self.q1[0]
self.q2.append(self.q1.popleft())
self.q1, self.q2 = self.q2, self.q1
return top_element
print("--- Stack Program 1: Implement Stack using Two Queues ---")
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print("Top element:", stack.top())
print("Popped element:", stack.pop())
print("Top element after pop:", stack.top())
print("Popped element:", stack.pop())
print("Popped element:", stack.pop())
print("Popped element (empty stack):", stack.pop())
print("\n")
# Program 2: Evaluate Postfix Expression using Stack
# ----------------------------------------------------
def evaluate_postfix(expression):
stack = []
operators = {'+', '-', '*', '/'}
for char in expression.split():
if char not in operators:
stack.append(int(char))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if char == '+':
stack.append(operand1 + operand2)
elif char == '-':
stack.append(operand1 - operand2)
elif char == '*':
stack.append(operand1 * operand2)
elif char == '/':
stack.append(int(operand1 / operand2))
return stack[0]
print("--- Stack Program 2: Evaluate Postfix Expression ---")
postfix_expression = "10 2 8 * + 3 -"
print(f"Expression: '{postfix_expression}'")
print(f"Result: {evaluate_postfix(postfix_expression)}")
print("\n")
# Program 3: Balanced Parentheses with Multiple Types
# ---------------------------------------------------
def is_balanced(s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in "({[":
stack.append(char)
elif char in ")}]":
if not stack or mapping[char] != stack.pop():
return False
return not stack
print("--- Stack Program 3: Balanced Parentheses ---")
s1 = "{[()]}[]"
s2 = "{[(])}"
print(f"String '{s1}' is balanced: {is_balanced(s1)}")
print(f"String '{s2}' is balanced: {is_balanced(s2)}")
print("\n")
# Program 4: Stock Span Problem
def stock_span(prices):
stack = []
spans = [0] * len(prices)
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
spans[i] = i - stack[-1] if stack else i + 1
stack.append(i)
return spans
print("--- Stack Program 4: Stock Span Problem ---")
stock_prices = [100, 80, 60, 70, 60, 75, 85]
print(f"Prices: {stock_prices}")
print(f"Spans: {stock_span(stock_prices)}")
print("\n")
# Program 5: Largest Rectangle in Histogram
def largest_rectangle_area(heights):
stack = [-1]
max_area = 0
for i, h in enumerate(heights):
while stack[-1] != -1 and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
while stack[-1] != -1:
height = heights[stack.pop()]
width = len(heights) - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area
print("--- Stack Program 5: Largest Rectangle in Histogram ---")
histogram = [2, 1, 5, 6, 2, 3]
print(f"Histogram heights: {histogram}")
print(f"Largest rectangle area: {largest_rectangle_area(histogram)}")
print("\n")
# Program 6: Next Greater Element using Stack
# -------------------------------------------
def next_greater_element(nums):
stack = []
result = [-1] * len(nums)
for i in range(len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
result[i] = stack[-1]
stack.append(nums[i])
return result
print("--- Stack Program 6: Next Greater Element ---")
arr = [4, 5, 2, 10]
print(f"Array: {arr}")
print(f"Next greater elements: {next_greater_element(arr)}")
print("\n")
Output
--- Stack Program 1: Implement Stack using Two Queues ---
Top element: 3
Popped element: 3
Top element after pop: 2
Popped element: 2
Popped element: 1
Popped element (empty stack): None
--- Stack Program 2: Evaluate Postfix Expression ---
Expression: '10 2 8 * + 3 -'
Result: 23
--- Stack Program 3: Balanced Parentheses ---
String '{[()]}[]' is balanced: True
String '{[(])}' is balanced: False
--- Stack Program 4: Stock Span Problem ---
Prices: [100, 80, 60, 70, 60, 75, 85]
Spans: [1, 1, 1, 2, 1, 4, 6]
--- Stack Program 5: Largest Rectangle in Histogram ---
Histogram heights: [2, 1, 5, 6, 2, 3]
Largest rectangle area: 10
--- Stack Program 6: Next Greater Element ---
Array: [4, 5, 2, 10]
Next greater elements: [5, 10, 10, -1]
