[CS/Computer Science][자료구조/Data Structure] 스택 / 큐

이번 포스트에서는 컴퓨터 자료구조 중 중요한 특성을 지닌 스택과 큐에 대해 알아보겠습니다.

1. 스택(Stack)

한 쪽에서만 데이터의 삽입 및 삭제가 가능한 자료구조
후입선출(LIFO, Last in First Out) 자료구조
- 푸시(push): 스택에 데이터를 저장하는 연산
- 팝(pop): 스택에서 데이터를 빼내는 연산
스택의 활용도
1. 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때
  - 함수의 매개변수를 저장할 때
  - 함수가 실행되는 동안만 유효 → 함수의 실행이 끝나면 1로 초기화
  - 최근에 호출된 함수의 매개변수가 가장 먼저 활용 & 가장 먼저 삭제
2. 뒤로가기 기능을 만들고 싶을 때
  - 웹 브라우저의 ‘뒤로 가기’버튼
    1. 웹 사이트 방문 시, 스택에 URL 저장(push)
    2. 뒤로 가기 버튼 클릭 시, 저장된 URL을 빼내어(pop)
    3. 해당 URL로 이동

한 쪽으로 데이터 삽입, 다른 한 쪽으로 데이터 삭제하는 자료구조
선입선출(FIFO, First in First Out) 자료구조
- 인큐(enqueue): 큐에 데이터를 저장하는 연산
- 디큐(dequeue): 큐에서 데이터를 빼내는 연산
큐의 활용도
- 버퍼(buffer): 임시 저장된 데이터를 차례로 내보내거나 꺼내오는 것
- 변형된 형태: 원형 큐 / 덱 / 우선순위 큐
  1. 원형 큐(Circular Queue)
    - 데이터를 삽입하고 삭제하는 쪽, 양쪽을 하나로 연결해 원형으로 사용하는 자료구조
  2. 덱(deque)
    - 양쪽으로 데이터를 삽입/삭제할 수 있는 큐 (= 양방향 큐(double-ended queue))
  3. 우선순위 큐(priority queue)
    - FIFO로 처리되는 것이 아닌, 우선순위가 높은 순서대로 처리되는 큐
    - 힙(heap) 기반 구현