C++ STL stack / queue 완전 정리 — LIFO vs FIFO 실전편

코딩테스트 준비 #2

C++ STL stack / queue 완전 정리 — LIFO vs FIFO 실전편

STL · stack · queue · 프로그래머스 · 올바른 괄호

🎯 목표

코딩테스트 스택/큐 유형을 C++로 풀기 위해 stack과 queue 기본 문법을 정리하고, 프로그래머스 올바른 괄호(Level 2) 문제에 직접 적용한다.

📌 stack vs queue vs deque

STL	구조	접근 방향	범위기반 for
stack	LIFO	한쪽 끝만 (top)	❌
queue	FIFO	앞(front) / 뒤(back)	❌
deque	양방향	앞/뒤 모두 + 인덱스	✅

stack과 queue는 내부적으로 deque 기반이다. 접근 방향을 제한해놓은 것뿐이다.

🔧 stack 기본 문법

#include <stack>

stack<int> st;

st.push(3); // 위에 추가
st.top(); // 맨 위 값 확인 (제거 안함)
st.pop(); // 맨 위 값 제거
st.empty(); // 비어있으면 true
st.size(); // 원소 개수

전체 순회 방법

// 범위기반 for 불가 → while로 꺼내야 함
while (!st.empty())
{
  cout << st.top() << "\n";
  st.pop();
}
// LIFO니까 역순 출력됨

⚠️ 빈 스택에서 pop() 하면 런타임 에러. 반드시 empty() 체크 후 pop() 해야 한다.

🔧 queue 기본 문법

#include <queue>

queue<int> q;

q.push(3); // 뒤에 추가
q.front(); // 맨 앞 값 확인 (제거 안함)
q.back(); // 맨 뒤 값 확인
q.pop(); // 맨 앞 값 제거
q.empty(); // 비어있으면 true
q.size(); // 원소 개수

전체 순회 방법

// 범위기반 for 불가 → while로 꺼내야 함
while (!q.empty())
{
  cout << q.front() << "\n";
  q.pop();
}
// FIFO니까 넣은 순서대로 출력됨

⚡ stack vs queue 한눈에 비교

기능	stack	queue
추가	push() → 위에	push() → 뒤에
확인	top()	front() / back()
제거	pop() → 위에서	pop() → 앞에서
순서	LIFO (역순)	FIFO (입력 순서)
코테 용도	괄호, DFS, 히스토리	BFS, 시뮬레이션

🔥 실전 적용 — 올바른 괄호

문자열이 주어질 때, 올바른 괄호 문자열인지 판별해라. ( 로 열면 반드시 ) 로 닫혀야 한다.

핵심 로직: '(' 나오면 push → ')' 나오면 스택 비어있으면 false, 아니면 pop → 루프 끝나고 스택에 남아있으면 false

#include <string>
#include <stack>
using namespace std;

bool solution(string s)
{
  bool answer = true;
  stack<char> st;

  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] == '(')
    {
      st.push('(');
    }
    else if (s[i] == ')')
    {
      if (st.empty()) // 빈 스택에서 pop 방지
      {
        return false;
      }
      st.pop();
    }
  }

  if (!st.empty()) // 루프 끝났는데 '(' 남아있으면
  {
    answer = false;
  }
  return answer;
}

💡 배운 것

• stack과 queue는 범위기반 for 불가. while + empty() 체크로 순회해야 한다.

• 빈 스택/큐에서 pop()은 런타임 에러. 반드시 empty() 체크 후 pop() 해야 한다.

• stack은 DFS/괄호/히스토리, queue는 BFS/시뮬레이션에 쓴다.

• stack과 queue는 내부적으로 deque 기반이다. deque는 양쪽 끝 접근 + 인덱스 접근이 가능하다.

• size_t는 부호 없는 정수라 int와 섞으면 언더플로우 버그 발생 가능. (int) 캐스팅 습관 필요.

다음 포스팅: queue 실전 문제 + sort 정렬 정리