Linear Data Structures — Stack & Queue

Stacks and queues are two of the most fundamental data structures in computer science. A stack is LIFO (Last-In, First-Out), a queue is FIFO (First-In, First-Out). Together they underlie undo systems, browser history, breadth-first search, message brokers, and CPU schedulers. Let's see how to build them with Python's lists, collections.deque, and queue.Queue.

• Stack via list: append() to push, pop() to remove last.
• Queue via collections.deque: append() + popleft() for O(1) FIFO.
• Avoid list.pop(0) for queues — it is O(n).
• For multi-threaded queues use queue.Queue.

# Stack with list
stack = []
stack.append(1); stack.append(2); stack.append(3)
print(stack.pop())     # 3 (LIFO)

# Queue with deque
from collections import deque
q = deque()
q.append("a"); q.append("b"); q.append("c")
print(q.popleft())     # 'a' (FIFO)

• Stack — LIFO: The newest item is removed first. Think of a stack of plates: you take the top one off.
• Queue — FIFO: The oldest item is removed first. Think of a queue at the bank: first come, first served.
• List-based stack: Python lists already support push (append) and pop (pop()) in O(1). Lists make excellent stacks.
• List-based queue (don't!): list.pop(0) is O(n) because every other element shifts. Use collections.deque instead — it does O(1) at both ends.
• Using deque: deque is a double-ended queue. Use append + popleft for FIFO, or appendleft + pop for reverse-FIFO.
• Thread-safe queue: For producer-consumer patterns across threads, use queue.Queue — it handles synchronisation automatically.

stack = []
for x in [1, 2, 3, 4]:
    stack.append(x)
while stack:
    print(stack.pop(), end=" ")

from collections import deque
q = deque()
for x in ["a", "b", "c", "d"]:
    q.append(x)
while q:
    print(q.popleft(), end=" ")

def balanced(s):
    pairs = {")":"(","]":"[","}":"{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced("([]{})"))
print(balanced("([)]"))

def reverse(s):
    stack = list(s)
    return "".join(stack.pop() for _ in range(len(s)))

print(reverse("Python"))

from queue import Queue
q = Queue()
for i in range(5):
    q.put(i)
while not q.empty():
    print(q.get(), end=" ")

from collections import deque
graph = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}
seen, order = set(), []
q = deque([1])
while q:
    n = q.popleft()
    if n in seen: continue
    seen.add(n); order.append(n)
    q.extend(graph[n])
print(order)

• Use list for stacks — append/pop are both O(1).
• Use collections.deque for queues — both ends are O(1).
• Never use list.pop(0) for queues — it is O(n).
• Use queue.Queue only when threads are involved; in single-threaded code it's overkill.
• Stacks and queues are abstractions — the API matters, not the underlying container.
• collections.deque(maxlen=N) creates a fixed-size circular buffer.

• Using list as queue: pop(0) shifts every element — terrible performance.
• Empty pop: list.pop() on an empty list raises IndexError.
• Wrong end: using append+pop on deque gives LIFO, not FIFO.
• Mixing semantics: calling a stack a 'queue' confuses readers — name variables correctly.
• Forgetting thread-safety: deque is not safe across threads; queue.Queue is.
• Recursion limit: deep DFS via recursion may hit Python's recursion limit — use an explicit stack.

• Problem 1: Implement a stack class with push, pop, peek, and is_empty methods.
• Problem 2: Implement a queue class using collections.deque.
• Problem 3: Use a stack to evaluate a postfix expression.
• Problem 4: Use a queue to print numbers from 1 to N in level-order from a binary tree.
• Problem 5: Check if a string is a palindrome using one stack and one queue.
• Problem 6: Implement a circular queue of fixed capacity 5.

• Q1. What is the difference between a stack and a queue?
• Q2. Why is list.pop(0) slow?
• Q3. When would you use collections.deque over a list?
• Q4. What is the difference between queue.Queue and collections.deque?
• Q5. How would you implement a queue using two stacks?
• Q6. Explain the use of stacks in expression evaluation.

• Q1: What's the difference between a stack and a queue?
  A stack is LIFO — last in, first out. A queue is FIFO — first in, first out.
• Q2: How do I build a stack in Python?
  Use a list: append to push, pop() to remove. Both are O(1).
• Q3: How do I build a queue in Python?
  Use collections.deque with append() and popleft(). Both ends are O(1).
• Q4: When should I use queue.Queue?
  When multiple threads must put and get safely. Otherwise deque is faster.
• Q5: Are stacks recursive?
  Recursion itself uses the call stack. Many recursive algorithms can be rewritten iteratively using an explicit stack.
• Q6: What is a priority queue?
  A queue where items are dequeued by priority. Use the heapq module for an efficient implementation.