"Can you explain the difference between a stack and a queue? Describe how elements are added and removed, typical operations, and when you would use each one."
A stack follows LIFO: last in, first out. A queue follows FIFO: first in, first out, so the oldest element is removed first.
stack.append(x); stack.pop()
queue.append(x); queue.pop(0)
Stacks usually support push, pop, and peek on one end. Queues usually support enqueue, dequeue, and front/peek, with insertion at the back and removal from the front.
Both can be implemented with arrays or linked lists, but the performance trade-offs differ. For example, a Python list works well as a stack, while a deque is better for a queue because removing from the front of a list is O(n).
from collections import deque
q = deque()
q.append(1)
q.popleft()
Stacks are useful for function calls, undo operations, expression evaluation, and DFS. Queues are useful for task scheduling, buffering, producer-consumer systems, and BFS.
The main difference is not just the method names but the order in which data is processed. Choosing the wrong structure can make an algorithm incorrect even if the code still runs.