[자료구조] 스택과 큐에 대해 알아보자

스택(STACK)

 

스택 자료구조는 접시에 음식을 쌓아 올리듯 데이터를 차곡차고 쌓아 올린 형태로 자료를 구성합니다.

 

 

    일상에서 쌓아 올리는 방식을 추상화하여 자료구조로 정의한 것이 스택입니다. 스택은 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있고 ,top으로 정한 한 곳으로만 접근하도록 제한 되어 있습니다.따라서 top을 통해 들어온 데이터가 일정한 방향, 즉 아래에서 위로 차곡차곡 쌓이게 됩니다. 여기서 top는 가장 마지막에 삽입이 된 위치 즉 스택에서의 가장 상단에 위치하게 됩니다.

 

스택의 특징으로는 가장 마지막에 삽입된 데이터가 가장 먼저 삭제 된다는 구조적인 특징을 가집니다. 이러한 스택 동작 구조를 후입선출 LIFO(last in First out) 이라고 합니다.

 

스택의 활용 예시

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

 

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

 

 

큐(QUEUE)

 

큐는 삽입과 삭제의 위치와 방법이 제한된 순서리스트라는 점은 같지만 리스트의 한쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업만 이루어진다는 점이 스택과는 다릅니다.

큐는 삽입된 순서대로 먼저 삽입된 데이터가 삭제되는 선입선출 (FIFO:first in first out) 구조로 운영이 됩니다.

 

 

   큐는 한쪽 끝은 front(머리)로 정해 삭제 연산만 수행하고, 다른 쪽 끝을 rear(꼬리)로 정하여 삽입 연산만 수행하는 제한 조건을 가진 자료구조 입니다. 큐에서 front는 가장 먼저 큐에 삽입된 첫번째 원소이고 ,rear는 큐에 가장 늦게 삽입된 마지막 원소입니다. 가장 먼저 삽입되어 가장 앞에 있는 front 원소가 가장 먼저 삭제 되므로 큐는 FIFO구조가 됩니다.

큐의 rear에서 이루어지는 삽입 연산을 EnQueue라고 하고, front에서 이루어지는 삭제 연산을 Dequeue라고 합니다.

 

큐의 활용 예시

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

 

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