Stack & Queue
Stack
스택( Stack ) 이란 쌓아올린 다는 것을 의미합니다. 쌓여져 있는 접시 더미와 같이 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다.
접시를 쌓을 때 맨 위에 차곡차곡 쌓고 가져올 때에는 위에서부터 하나씩 가져오는 것과 같은 원리입니다.
Stack의 특징
스택은 위의 사진처럼 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다.
top은 가장 위에 있는 자료가 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 됩니다.
스택에서 자료를 삭제하거나 가져올 때에도 top을 통해서만 가능합니다.
스택에서 top을 통해 삽입하는 연산을 push, top을 통해 삭제하거나 가져오는 연산을 pop 이라고 합니다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입 된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지고 있습니다.
이러한 스택의 구조를 후입선출(LIFO: last in, first out) 구조라고 합니다.
비어있는 스택에서 원소를 추출하려고 할 때는 stack underflow라고 하고, 스택이 넘치는 경우에는 stack overflow 라고 합니다.
스택을 활용한 예시
스택의 특징인 후입선출(LIFO)은 여러 분야에서 활용 가능합니다.
- 웹 브라우저 방문 기록(뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여줍니다.
- 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력합니다.
- 실행취소 (undo) : 가장 나중에 실행된 것 부터 실행을 취소합니다.
Queue
Queue의 사전적 의미는 줄, 혹은 차례를 기다리는 사람이나 승용차의 열을 의미합니다.
따라서 일상생활에서 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것, 은행에서 먼저온 사람의 업무를 창구에서 처리하는 것과 같이 선입 선출 (FIFO: first in, first out) 방식의 자료구조를 말합니다.
Queue의 특징
정해진 곳(top)을 통해서만 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업을 하고 다른 쪽 끝에서 삭제 작업이 이루어 집니다. 이때 삭제 연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행됩니다.
이 때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)라고 하고, 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라고 부릅니다.
정리해보자면 다음과 같습니다.
- 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear 라고 합니다.
- 큐는 들어올 때 rear로 들어오지만 나올때는 front부터 빠지는 특성을 가지고 있습니다.
- 접근 방법은 가장 첫 원소와 끝 원소로만 가능합니다.
- 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제 됩니다.
큐를 활용한 예시
큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 많이 이용합니다.
- 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
- 은행 업무
- 콜센터 고객 대기시간
따라서 큐는 주로 순서를 보장하기 위한 처리가 필요할 때 사용되고, 큐에 저장된 요소들은 순서대로 존재하고, 가장 앞에 있을수록, 오래 기다리고 있다는 것을 의미한다는 것을 알 수 있습니다.