스택(STACK), 큐(QUEUE)

스택이란?

스택(STACK)은 객체들의 집합소로 데이터를 기록하는 구조라고 보면된다.

스택이란 쌓아올린다는 것을 의미한다. 따라서, 스택 구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아올린 형태의 구조를 말한다.

 

스택의 특징

스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, 정해진 곳을 통해서만 접근할 수 있다.

아래가 막혀있고 위가 뚫린 형태로 차곡차곡 쌓는 구조로 볼 수 있는데, 이러한 경우 가장 위의 자료가 가장 최근에 쌓인 자료가 된다.

 

스택은 시간 순서에 따라 자료가 쌓여 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가진다. 이를 후입선출(LIFO, Last-In-First-Out)구조라고 한다.

 

스택에서 삽입은 PUSH, 삭제는 POP이라는 용어로 사용하고 있다.

 

비어있는 스택에서 원소를 추출하려고 할때 stack underflow라고 하며, 스택이 넘치는 경우를 stack overflow라고 한다.

특히 우리는 stack overflow라는 에러를 많이 접해봤을 것이다.

무언가를 계속 넣고 있다가(삽입 또는 쌓고 있다가) 받아들일 수 있는 크기를 초과해서 흘러넘쳐버린 것을 의미한다. (흔히, 재귀함수를 호출할 때 많이 경험한다)

 

스택의 활용 예시

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

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

 

 

큐(QUEUE)란?

큐(QUEUE)는 단순히 스택의 반대 개념을 갖는다. 

우리가 흔히 접할 수 있는 순서대로 처리하는 방식이라고 할 수 있다.

놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 사람이 창구에서 먼저 업무를 처리하는 것과 같이 선입선출(FIFO, First-In-First-Out) 방식의 자료 구조를 말한다.

 

* 양방향 큐(Qeque) - 덱

덱은 큐를 양 방향으로, 즉 삽입 삭제가 양쪽 방향에서 이루어진 것을 말한다. (큐와 스택을 합친 것으로 선입 선출, 후입 선출의 복합적인 성격을 띈다.

 

큐의 특징

큐의 저장된 요소들은 순서대로 존재하고, 가장 앞에 있을 수록 오래 기다리고 있다는 것을 의미한다.

 

큐는 스택과 다른게 입구와 출구가 각각 나뉘어져 있으며, 삭제연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear)로 정해 각각의 연산작업만 수행한다.

 

큐의 리어에서 이루어지는 삽입 연산을 인규(enQueue) 프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올 때는 front부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다. 주로 순서를 보장하기 위한 처리가 필요할 때 사용한다.

 

큐의 활용예시

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

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