What is the difference between stack and queue?

Stack is LIFO (Last In First Out), queue is FIFO (First In First Out). Stack is like stacking plates, queue is like standing in line.

Use for parenthesis matching, function calls, undo operations, DFS, etc.

Use for BFS, printer queue, task scheduling where order matters.

How to implement stack/queue in Python?

Use list for stack, collections.deque for queue.

Stack and Queue — Complete Guide

2024년 12월 25일 · 18분 읽기 · 수정 2026년 3월 28일 Beginner Tutorial

이 글의 핵심

Complete guide to stacks and queues for coding interviews. Master LIFO and FIFO data structures with principles, code examples, and practical applications.

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

Stack: LIFO, push/pop O(1), parenthesis matching
Queue: FIFO, enqueue/dequeue O(1), BFS
Python: Use list for stack, deque for queue
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

Keywords

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

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

A. Complete guide to stacks and queues for coding interviews.

Q. What should I read before this?

A. Follow the previous article or related articles links at the bottom of each post to learn in sequence.

Q. Where can I study this more deeply?

A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

이 글의 핵심

Introduction

”When do I use stacks and queues?”

1. Stack

What is a Stack?

Python Implementation (3 Methods)

C++ Implementation

Stack Time Complexity

2. Queue

What is a Queue?

Python Implementation

C++ Implementation

3. Problem Solving

Problem 1: Valid Parentheses

Problem 2: Implement Queue using Stacks

Problem 3: Next Greater Element

Problem 4: BFS (Breadth-First Search)

4. Usage Patterns

Stack Usage Patterns

Queue Usage Patterns

5. Advanced Topics

Priority Queue

Deque - Double-Ended Queue

Troubleshooting

Issue 1: Pop from Empty Stack/Queue

Issue 2: Using list for Queue (Performance)

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

Summary

Key Points

Selection Guide

Next Steps

Recommended Problems

Beginner

Intermediate

Advanced

Related Posts

Keywords

Frequently Asked Questions (FAQ)

Q. When would I use this in practice?

Q. What should I read before this?

Q. Where can I study this more deeply?

Related Articles (Internal Links)

Keywords Covered in This Article (Related Search Terms)

이 글이 도움이 되셨나요?