A stack is LIFO (last in, first out); a queue is FIFO. C++ provides std::stack and std::queue adapters over deque/vector—used in DFS, BFS, parsing, and undo buffers.
Operations
- Stack:
push,pop,top— O(1) - Queue:
push,pop,front— O(1)
Applications
- Stack — matching parentheses, DFS iterative, monotonic stack
- Queue — BFS shortest path layers, task scheduling
Stack and queue demo
#include
#include
#include
int main() {
std::stack st;
st.push(1); st.push(2); st.push(3);
std::cout << "stack top=" << st.top() << "\n";
st.pop();
std::queue q;
q.push(10); q.push(20);
std::cout << "queue front=" << q.front() << "\n";
return 0;
} Important interview questions and answers
- Q: LIFO vs FIFO example?
A: Undo stack is LIFO; printer queue is FIFO. - Q: Can queue use vector alone?
A: Pop from front of vector is O(n); deque gives O(1) ends.
Self-check
- Name two problems that use a stack.
- What is complexity of queue push and pop?
Tip: Parentheses matching is the classic stack warm-up—code it once from memory.
Interview prep
- LIFO vs FIFO?
Stack last-in-first-out; queue first-in-first-out.
- BFS structure?
Queue for layer-order traversal.