[자료구조] 스택(Stack) / 큐(Queue)

스택(Stack), 큐(Queue) 등은 자료구조에서 선형 구조라 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다.

 

■ 스택 (Stack)

• 스택이란 쌓아 올린다는 것을 의미한다. 따라서 탑처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.
• 예를 들어 원형 통 과자에 마지막에 담긴 과자가 제일 먼저 꺼내지는 것처럼 스택 구조는 입구와 출구가 같아 마지막에 들어온 것이 가장 먼저 나간다 하여 후입선출(LIFO, Last-In-First-Out)법 이라고 한다.

※ 스택의 특징

• 스택의 입력과 출력은 맨 위에서만 일어나기 때문에, 스택의 중간에서는 데이터를 삽입하거나 삭제할 수 없다.  
• 스택 구조의 맨 위를 가리키는 top 이라는 변수가 존재하며, 입력과 출력이 이루어지는 맨 위 부분을 스택 상단이라 하고 반대쪽인 바닥 부분을 스택 한단 이라고 부른다. 
• 삽입되는 새 데이터는 top 이 가리키는 자료 위에 쌓이게 되며 삭제할 때도 top 을 통해서만 가능하다. 
• top 을 통해 데이터를 삽입하는 연산을 'push' 라 하고, top 을 통해 삭제하는 연산을 'pop' 이라고 한다. 

※ 스택의 활용 예시

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

 

■ 큐 (Queue)

• 큐의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미하는데, 이처럼 줄지어 순서대로 처리 되는 것이 큐 자료구조이다. 
• 예를 들어 은행 업무가 놀이기구 대기라인처럼 먼저 입력된 것이 먼저 나가는 방식으로, 선입선출(FIFO, First-In-First-Out)법이라고 한다.

※ 큐의 특징

• 큐에서는 삽입과 관련된 연산만 수행하는 곳을 후단(rear) 이라 하고, 삭제 관련 연산만 수행하는 곳을 전단(front) 라고 한다.
• 후단에서 이뤄지는 삽입 연산을 '인큐(enQueue)'라 하고, 전단에서 이뤄지는 삭제연산을 '디큐(deQueue)'라고 한다.

※ 큐의 활용 예시

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

※ 큐의 종류

▷ 선형 큐

• 선형 큐에서 삽입 및 삭제를 반복하다 보면 rear가 맨 마지막 인덱스(n-1)를 가리키게 되어, 앞에는 비어 있음에도 불구하고 더이상 노드를 삽입할 수 없어 큐가 꽉 찼다고 인식하게 된다.
• 이러한 문제점을 해결하기 위해 원형 큐를 사용한다.

▷ 원형 큐

• 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 '(index+1) % ${배열 사이즈}' 를 이용하기 때문에 OutOfBoundsException 이 일어나지 않고 인덱스 0으로 순환되는 구조를 가진다.

▷ 우선순위 큐

• 우선순위 높은 데이터가 먼저 나온다.
• 트리 구조를 가지고 있으며 일반적으로 최대 힙을 이용해 구현한다. 
• 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등 다양한 기술에 적용되고 있다.