Stack and Queue — Complete Guide

Introduction

”When do I use stacks and queues?”

Stacks and queues are used when processing data in specific order. They appear very frequently in coding interviews. What this article covers:

• Stack (LIFO)
• Queue (FIFO)
• Implementation methods
• Real-world problem solving

---

1. Stack

What is a Stack?

A stack is a LIFO (Last In First Out) data structure. The last item inserted comes out first. Real-life analogies:

• Stacking plates: Take the top plate first
• Browser back button: Navigate to most recent page
• Function call stack: Most recently called function exits first

Stack operations:
    push(3)        push(2)        push(1)
    ↓              ↓              ↓
                            [1]  ← top
                   [2]      [2]
[3]                [3]      [3]  ← bottom
    pop() → 1      pop() → 2      pop() → 3
    ↓              ↓              ↓
[2]  ← top         [3]  ← top     [] (empty)
[3]

Python Implementation (3 Methods)

# Method 1: Using list (simplest, recommended)
stack = []
# push: add element
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]
print(stack)  # [1, 2, 3] (3 is top)
# pop: remove and return top
top = stack.pop()
print(top)  # 3
print(stack)  # [1, 2] (2 is new top)
# top: check without removing
if stack:
    print(stack[-1])  # 2 (last element = top)
# empty check
is_empty = len(stack) == 0
print(is_empty)  # False
# Method 2: collections.deque (more efficient)
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # 3
# Method 3: Class implementation (explicit, educational)
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")
    
    def top(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("top from empty stack")
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)
# Usage
s = Stack()
s.push(10)
s.push(20)
print(s.top())   # 20
print(s.pop())   # 20
print(s.size())  # 1

C++ Implementation

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    
    // push: add element
    s.push(1);
    s.push(2);
    s.push(3);
    
    // top: check top (no removal)
    cout << s.top() << endl;  // 3
    
    // pop: remove top (no return!)
    s.pop();  // Remove 3
    
    cout << s.top() << endl;  // 2
    
    // empty: check if empty
    cout << s.empty() << endl;  // 0 (false)
    
    // size: get size
    cout << s.size() << endl;  // 2
    
    return 0;
}

Python vs C++ Difference:

• Python: pop() returns the value
• C++: pop() doesn’t return, use top() then pop()

Stack Time Complexity

Operation	Description	Time	Python	C++
push(x)	Add element	O(1)	append(x)	push(x)
pop()	Remove top	O(1)	pop()	pop()
top()	Check top	O(1)	[-1]	top()
empty()	Check empty	O(1)	len() == 0	empty()
size()	Get size	O(1)	len()	size()

---

2. Queue

What is a Queue?

A queue is a FIFO (First In First Out) data structure. The first item inserted comes out first. Real-life analogies:

• Standing in line: First person gets served first
• Printer queue: First document sent prints first
• Call center: First caller gets answered first

Queue operations:
    enqueue(1)     enqueue(2)     enqueue(3)
    ↓              ↓              ↓
[1]                [1][2]         [1][2][3]
 ↑                  ↑              ↑     ↑
front              front          front  rear
    dequeue() → 1  dequeue() → 2  dequeue() → 3
    ↓              ↓              ↓
[2][3]             [3]            [] (empty)
 ↑                  ↑
front              front

Python Implementation

# Method 1: collections.deque (recommended)
from collections import deque
queue = deque()
# enqueue: add to rear
queue.append(1)  # deque([1])
queue.append(2)  # deque([1, 2])
queue.append(3)  # deque([1, 2, 3])
# dequeue: remove from front
front = queue.popleft()  # O(1) - efficient!
print(front)  # 1
print(queue)  # deque([2, 3])
# front: check without removing
if queue:
    print(queue[0])  # 2
# empty check
is_empty = len(queue) == 0
# ❌ Method 2: list (inefficient, NOT recommended)
queue_list = []
queue_list.append(1)
queue_list.pop(0)  # O(n)! Very slow

deque vs list Performance:

import time
from collections import deque
# deque (O(1))
q = deque(range(100000))
start = time.time()
for _ in range(10000):
    q.popleft()
print(f"deque: {time.time() - start:.4f}s")  # ~0.001s
# list (O(n))
q = list(range(100000))
start = time.time()
for _ in range(10000):
    q.pop(0)
print(f"list: {time.time() - start:.4f}s")  # ~5s (5000x slower!)

C++ Implementation

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    
    // push: add to rear
    q.push(1);
    q.push(2);
    q.push(3);
    
    // front: check front (no removal)
    cout << q.front() << endl;  // 1
    
    // back: check rear
    cout << q.back() << endl;  // 3
    
    // pop: remove from front (no return!)
    q.pop();  // Remove 1
    
    cout << q.front() << endl;  // 2
    
    // empty: check if empty
    cout << q.empty() << endl;  // 0 (false)
    
    // size: get size
    cout << q.size() << endl;  // 2
    
    return 0;
}

---

3. Problem Solving

Problem 1: Valid Parentheses

def is_valid_parentheses(s):
    """
    Check if parentheses are valid
    "(())" → True
    "(()" → False
    """
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack:
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0
# Test
print(is_valid_parentheses("()"))        # True
print(is_valid_parentheses("()[]{}"))    # True
print(is_valid_parentheses("(]"))        # False
print(is_valid_parentheses("([)]"))      # False
print(is_valid_parentheses("{[]}"))      # True

C++ Solution:

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {'(', ')'}, {'{', '}'}, {'[', ']'}
    };
    
    for (char c : s) {
        if (pairs.count(c)) {  // Opening bracket
            st.push(c);
        } else {  // Closing bracket
            if (st.empty()) return false;
            
            char opening = st.top();
            st.pop();
            
            if (pairs[opening] != c) return false;
        }
    }
    
    return st.empty();
}

Problem 2: Implement Queue using Stacks

Problem: Implement a queue using two stacks. Idea:

• stack_in: for enqueue
• stack_out: for dequeue
• When dequeue and stack_out is empty, transfer all from stack_in

class QueueUsingStacks:
    """
    Implement queue using two stacks
    """
    def __init__(self):
        self.stack_in = []   # for enqueue
        self.stack_out = []  # for dequeue
    
    def enqueue(self, x):
        """Add to rear - O(1)"""
        self.stack_in.append(x)
    
    def dequeue(self):
        """Remove from front - Amortized O(1)"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out.pop() if self.stack_out else None
    
    def front(self):
        """Check front - Amortized O(1)"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out[-1] if self.stack_out else None
    
    def is_empty(self):
        return not self.stack_in and not self.stack_out
# Test
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.front())    # 2
print(q.dequeue())  # 2

Problem 3: Next Greater Element

Problem: Find the next greater element to the right for each element. Example:

• [4, 5, 2, 10] → [5, 10, 10, -1]
• [1, 2, 3, 4] → [2, 3, 4, -1]

def next_greater_element(arr):
    """
    Find next greater element for each element
    Time: O(n)
    Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Store indices
    
    for i in range(n):
        # Current value is greater than stack top's value
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        
        stack.append(i)
    
    return result
# Test
arr = [4, 5, 2, 10, 8]
print(next_greater_element(arr))
# [5, 10, 10, -1, -1]

Problem 4: BFS (Breadth-First Search)

from collections import deque
def bfs(graph, start):
    """
    Traverse graph using BFS
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result
# Test
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs(graph, 'A'))
# ['A', 'B', 'C', 'D', 'E', 'F']

---

4. Usage Patterns

Stack Usage Patterns

Pattern	Description	Examples
Bracket/Tag Matching	Match opening and closing	HTML, JSON, expressions
Calculator	Evaluate postfix notation	3 4 + 2 * → 14
Function Call Stack	Simulate recursion	DFS, backtracking
Undo	Cancel recent actions	Ctrl+Z
Path Tracking	Remember previous states	Maze exploration

Queue Usage Patterns

Pattern	Description	Examples
BFS	Level-order traversal	Shortest path, tree levels
Task Queue	Process in order	Printer, call center
Scheduling	Round-robin	CPU scheduler
Sliding Window	Fixed-size window	Recent N items
Stream Processing	Sequential data	Log analysis

---

5. Advanced Topics

Priority Queue

Priority queue is a queue where elements with higher priority come out first.

import heapq
# Min heap (default)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
print(heapq.heappop(pq))  # 1 (smallest)
print(heapq.heappop(pq))  # 2
print(heapq.heappop(pq))  # 3
# Max heap (use negative values)
pq = []
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
heapq.heappush(pq, -2)
print(-heapq.heappop(pq))  # 3 (largest)

C++ Priority Queue:

#include <queue>
#include <iostream>
using namespace std;
int main() {
    // Max heap (default)
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    
    cout << pq.top() << endl;  // 3 (largest)
    pq.pop();
    cout << pq.top() << endl;  // 2
    
    // Min heap
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(3);
    min_pq.push(1);
    min_pq.push(2);
    
    cout << min_pq.top() << endl;  // 1 (smallest)
    
    return 0;
}

Deque - Double-Ended Queue

Deque allows insertion/deletion from both ends.

from collections import deque
dq = deque([1, 2, 3])
# Add/remove from rear
dq.append(4)        # [1, 2, 3, 4]
dq.pop()            # [1, 2, 3]
# Add/remove from front
dq.appendleft(0)    # [0, 1, 2, 3]
dq.popleft()        # [1, 2, 3]
# Check both ends
print(dq[0])   # 1 (front)
print(dq[-1])  # 3 (back)
# Rotate
dq.rotate(1)   # Right by 1 → [3, 1, 2]
dq.rotate(-1)  # Left by 1 → [1, 2, 3]

---

Troubleshooting

Issue 1: Pop from Empty Stack/Queue

# ❌ Error
stack = []
# stack.pop()  # IndexError: pop from empty list
# ✅ Solution: Check empty
if stack:
    value = stack.pop()
else:
    print("Stack is empty")
# ✅ Or exception handling
try:
    value = stack.pop()
except IndexError:
    print("Stack is empty")

Issue 2: Using list for Queue (Performance)

# ❌ Inefficient
queue = []
queue.append(1)
queue.pop(0)  # O(n)!
# ✅ Efficient
from collections import deque
queue = deque()
queue.append(1)
queue.popleft()  # O(1)

Issue 3: C++ stack/queue pop() Returns Nothing

// ❌ Error: pop() is void
// int value = stack.pop();  // Compile error
// ✅ Correct way
int value = stack.top();  // Get value
stack.pop();              // Remove

---

Summary

Key Points

1. Stack: LIFO, push/pop O(1), parenthesis matching
2. Queue: FIFO, enqueue/dequeue O(1), BFS
3. Python: Use list for stack, deque for queue
4. C++: <stack>, <queue> headers

Selection Guide

Situation	Data Structure	Reason
Process recent items first	Stack	LIFO
Process in order	Queue	FIFO
Parenthesis matching	Stack	Match most recent opening
BFS	Queue	Level-order traversal
DFS	Stack	Depth-first search
Undo/Redo	Stack	Cancel recent actions

Next Steps

• Hash Table
• BFS/DFS

---

Recommended Problems

Beginner

• LeetCode 20: Valid Parentheses
• LeetCode 225: Implement Stack using Queues
• LeetCode 232: Implement Queue using Stacks

Intermediate

• LeetCode 155: Min Stack
• LeetCode 496: Next Greater Element I
• LeetCode 739: Daily Temperatures

Advanced

• LeetCode 84: Largest Rectangle in Histogram
• LeetCode 239: Sliding Window Maximum
• LeetCode 862: Shortest Subarray with Sum at Least K

---

Related Posts

• Arrays and Lists | Essential Data Structures
• Hash Table | O(1) Search Data Structure
• BFS and DFS | Graph Traversal Algorithms

---

Keywords

Stack, Queue, Data Structure, LIFO, FIFO, Coding Interview, Algorithm, Python, C++, BFS, DFS, Deque, Priority Queue

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Complete guide to stacks and queues for coding interviews. Master LIFO and FIFO data structures with principles, code ex… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리
• BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
• Python 자료형 | 리스트, 딕셔너리, 튜플, 세트 완벽 가이드
• C++ queue/stack | ‘자료구조’ 완벽 정리 [BFS/DFS 활용]

---

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Data Structure, Stack, Queue, Coding Interview, LIFO, FIFO 등으로 검색하시면 이 글이 도움이 됩니다.