자료구조 Stack, Queue

1. Stack이란?

1-1) Stack의 정의

스택이란 쌓아 올린다는것을 의미한다.
직역 그대로, 데이터를 순서대로 쌓는 자료구조이다.

1-2) Stack의 특징

• LIFO(Last In First Out)
  : 먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조
• 데이터는 하나씩 넣고 뺄 수 있다.
  : Stack 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 처리한다.
• 하나의 입출력 방향을 가지고 있다.
  : 데이터의 입출력 방향이 같다. 만약, 입출력 방향이 여러 개라면 Stack 자료구조라고 볼 수 없다.
• 저장되는 데이터는 유한하고 정적이어야 한다.
• 스택의 크기는 제한되어 있다.
  : 힙(heap)에 비해 스택의 크기는 제한되어 있으므로, 스택 오버플로(Stack Overflow) 같은 에러가 자주 발생한다.

1-3) Stack의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

• 웹 브라우저 방문기록 : 뒤로가기, 앞으로가기
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소(undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계산
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

2. Queue란?

2-1) Queue의 정의

큐는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.
선입선출(FIFO, First in first out)방식의 자료구조를 말한다.

2-2) Queue의 특징

• 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 이루어진다.
• 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.
• 큐의 리어에서 이루어지는 삽입연산을 enQueue, 프론트에서 이루어지는 삭제연산을 deQueue라고 부른다.
  즉, 큐에서 front 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되는 것이며, rear 원소는 가장 늦게 들어온 마지막 원소가 된다.

2-3) Queue의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breath-First Search) 구현
• 캐시(Cache) 구현