C++ 기초 - 스택, 큐

Ctrl+z 를 생각해보자.

사용자의 행동을 자료구조로 저장해서 맨 마지막에 수행된 작업을 차례대로 제거해준다.

 

 

LIFO : 나중에 들어온 것이 먼저 나간다. Stack.

• vector의 push_back(), pop_back()은 대표적인 LIFO다.
• C++에는 stack이라는 자료구조가 따로 있다. vector는 동적 배열이지만 stack은 stack으로만 쓰려는 의도를 명확하게 하려고 사용된다.
  • push() : 맨 위에 값 추가
  • pop() : 맨 위의 값을 제거하고 값은 반환하지 않음
  • top() : 제거 안 하고 맨 위의 값만 반환 
  • 중간 값에 접근할 수 없다.

FIFO : 먼저 들어온 것이 먼저 나간다.

• Queue
  • push() : 맨 뒤에 값 추가
  • pop() : 맨 앞의 값 제거
    • deque를 사용하기 때문에 O(1)
  • front() : 맨 앞 요소 반환
  • back() : 맨 뒤 요소 반환

 

내부 구현 - 컨테이너 어댑터

stack과 queue는 컨테이너 어댑터라고 불린다.

기존 컨테이너를 감싸서 접근 방식을 제한한 것이다.

 

사용

게임 개발

Undo/Redo시스템 = 스택 두 개(Undo 스택에서 pop -> Redo 스택에 push)

입력 이벤트 큐, 네트워크 패킷 큐, 매칭 대기열 = 전부 Queue

 

웹/서버

브라우저 뒤로가기/앞으로가기 = 스택 두 개

메시지 큐(Message Queue) = 서비스 간 비동기 통신

 

일반 CS

함수 호출 스택 = 모든 프로그래밍 언어의 핵심

OS 프로세스 스케줄링 = Ready Queue

나중에 배울 DFS는 스택 기반, BFS는 큐 기반!