스택(Stack)과 큐(Queue)

고객사와 미팅을 가지며 개발팀장님의 "큐에 막혀서 테스트를 해볼 수가 없다" 라는 말을 회의록에 옮기며 Queue를 알아듣지 못해 Q 라고 적어버렸다.  question인가 혼자 생각하다 미팅이 끝난 후 아니나 다를까 실장님의 질문에 Q라고 작성한 걸 걸리며... 이 글을 작성하게 되었다.

 

Stack이란 무엇인가?

 

Stack은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다. 위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.

 

또한 Stack은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.

 

Stack에서 삽입 연산을 push, 삭제 연산을 pop이라고 하며, 이러한 스택의 구조를 후입 선출의 구조라고 하며, LIFO(Last In First Out) 라고 부른다.

사용 사례

• 웹 브라우저 방문기록 (뒤로 가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

 

큐(Queue)의 개념

 

Queue는 Stack과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로, FIFO(First In First Out)의 구조를 가지고 있다.

 

삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로, FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 나뉘어서 이루어지고 있다.

 

Queue는 rear에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트에서 이루어지는 삭제 연산을

디큐(Dequeue) 라고 부른다. 

 

사용 사례

• 은행 업무
• 대기열 순서와 같은 우선순위의 작업 예약 등
• 서비스 센터의 대기시간
• 프로세스 관리