Stack, Queue는 무엇일까?

스택(Stack)

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조를 말하며, LIFO(Last In First Out)으로 되어 있습니다.

즉, 마지막에 들어온 데이터가 제일 먼저 내보내집니다.

출처 : 위키백과

스택의특징

• 스택 내부의 데이터는, top 을 통해서만 접근할 수 있습니다. (top 은 가장 최근(마지막)에 들어온 자료를 의미합니다.)
• 스택에 데이터를 삽입할 때는, top 위에 쌓게 됩니다. ('push' 연산)
• 스택에서 데이터를 삭제할 때는, top 에 위치한 데이터를 삭제하게 됩니다. ('pop' 연산)

스택 사용 예시

• 역순 문자열 만들기 → ...PON..EDCBA
• 웹 브라우저 방문기록 (뒤로 가기) → 가장 마지막에 열린 페이지부터 노출
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

큐(Queue)

큐는 먼저 집어 넣은 데이터가 먼저 나오는 구조를 말하며, FIFO(First In First Out)으로 되어 있습니다.

즉, 스택과 반대의 개념으로 제일 먼저 들어온 데이터가 제일 먼저 내보내집니다.

출처 : 위키백과

큐의특징

• 큐는 삽입, 삭제가 다른 방향에서 이루어집니다.
  삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 수행되는 곳을 리어(rear)라고 합니다.
• 프론트(front)에서 이루어지는 삭제 연산을 디큐('dnQueue')라고 합니다.
• 리어(rear)에서 이루어지는 삽입 연산을 인큐('enQueue') 라고 합니다.

큐 사용 예시

• 큐는 주로, 데이터가 입력된 순서에 따라 처리되어야 할 때 사용됩니다. (놀이동산 줄, 은행 업무 등)
• 너비 우선 탐색(BFS, Breadth-First Search) 구현에 사용됩니다.
  BFS란 루트 노드 혹은 다른 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다.
• 캐시(Cache)를 구현할 때 사용합니다.