[과제] 자료구조 - 스택과 큐

다음 토론답변은 KG아이티뱅크 2학기 3기수 자료구조 수업의 과제에 대한 개인적인 답변입니다.

이에 받은 점수와 무관하게 학기를 마무리하며 개인적으로 기록을 남기고자 포스팅합니다.

 

 

주제

스택의 구조 및 특징을 큐와 비교해서 서술하고, 생활 속 스택과 큐 구조의 예를 각각 5가지 이상씩 그 이유와 함께 기술하시오.

 

 

답변

정보가 홍수처럼 넘쳐나고, 자료를 효과적으로 접근하고 사용하는 것이 중요한 시대가 도래했다. 이렇게 자료의 효율적인 사용을 위해 자료의 특징에 따라 분류, 구성, 저장 및 처리하는 모든 작업을 자료구조라 일컫는다. [1] 스택과 큐 또한 자료구조의 종류 중 두 가지이며, 서로 다른 특징을 갖고 이에 따른 장단점을 갖는다.

 

먼저 스택 (Stack)은, 자료를 차곡차곡 쌓아놓은 형태의 자료구조를 지칭한다. 동일한 구조와 크기의 자료를 한 방향으로 쌓을 수 있고, 현재 스택의 가장 위에 있는 마지막 자료를 가리키는 스택 상단 (stack top)에서만 입출력이 이루어진다. 그러므로 가장 먼저 삽입한 자료가 아래에 쌓이고, 가장 마지막에 삽입한 자료가 위에 쌓이며, 또 제일 먼저 출력된다. 후입선출 (LIFO, Last-In First-Out)의 구조인 것이다.

 

반면 큐 (Queue)는 반대로 가장 먼저 삽입된 원소가 가장 먼저 삭제되는 선입선출 (FIFO, First-In First-Out)의 구조이다. 여러 원소들이 한 방향, 한 줄로 늘어선 형태라고 볼 수 있다. 큐에서의 삽입은 큐의 끝, 후단 (rear)에서만 일어나며, 삭제는 큐의 처음, 전단 (front)이라고 부른다. 원소 삽입과 삭제가 같은 쪽에서 일어나는 스택과 달리, 큐는 다른 쪽에서 일어난다. [2]

 

스택 자료 구조의 예시는 일상 생활에서도, 컴퓨터에서도 쉽게 찾아볼 수 있다. 뷔페에 비치된 접시 더미가 한 예이다. 깨끗이 건조된 접시를 추가할 때는 더미의 위에서 놓고, 뷔페 사용자들 또한 위에서부터 접시를 가져간다. ‘원소’의 삽입과 삭제가 모두 스택의 맨 위 (top)에서 이루어지며, 더미의 중간에서는 발생하지 않는다. 창고에 쌓인 상자들 또한, 이미 있는 상자 더미 위에 새로운 상자들을 놓고, 물건이 출고될 때는 더미가 무너지지 않게 위에서부터 가져간다. 헬스장에서 중량 운동에 쓰는 바벨 원판 또한, 원판들을 차곡차곡 쌓아 원하는 중량을 만들되, 가장 나중에 끼운 원판을 가장 먼저 빼게 된다. 옷을 입고 벗을 때도 스택의 원리가 작용한다. 속옷, 스웨터와 바지, 롱패딩, 목도리의 순서로 입고, 벗을 때에는 정반대의 순서로 벗는다. 후입선출의 구조인 것이다.

 

이러한 스택은 컴퓨터에서 굉장히 유용하게 쓰인다. 그 예로, 핸드폰에서 앱을 사용하다가 특정 버튼을 누르면 다음 페이지로 넘어가고, 이 때 뒤로 가기 버튼을 누르면 현재 페이지가 종료되고 이전에 실행되었던 페이지로 돌아간다. 비슷한 예로 여러 응용프로그램에서 실행 취소를 누르면, 가장 나중에 실행되었던 명령부터 취소된다. 입력한 자료를 역순으로 출력해주는 프로그램을 구현할 때에도, 스택형 자료 구조는 유용하게 쓰인다.

 

큐의 예시 또한 매우 쉽게 발견할 수 있다. 패스트푸드 점에 가서 햄버거 주문을 할 때, 제일 먼저 줄을 선 사람이 제일 먼저 주문을 하고, 줄에서 빠져나간다. 은행에서 대기 번호표를 뽑을 때도, 가장 먼저 온 사람이 제일 빠른 순서를 부여 받고, 제일 먼저 서비스를 받은 후 대기 명단에서 제외된다. 편의점에서 음료는, 가장 먼저 진열된 것이 가장 빨리 나갈 수 있게 냉장고의 뒤에서부터 충전한다. 원소 삽입은 큐의 뒷부분에서, 원소 삭제는 큐의 앞부분에서 이루어지는 것이다. 정체된 도로에 가장 먼저 진입한 차가 가장 먼저 빠져나가고, 휴게소 판매대에서 제일 먼저 만들어진 호두과자가 제일 먼저 나가는 것 또한 큐의 예이다.

 

컴퓨터에서의 큐의 사용도 아주 빈번하다. 보통 컴퓨터의 CPU와 주변기기 사이에 속도 차이가 있기 때문에, CPU의 효율적인 사용을 위해 큐가 사용된다. CPU에서 데이터를 빠른 속도로 큐에 저장하고 다른 작업으로 넘어가고, 주변기기의 속도에 맞게 큐에서 자료를 출력하여 해당 작업을 수행한다. 또한 실제 상황을 시뮬레이션하는 모델링에도 큐는 많이 사용된다.

 

이처럼 스택과 큐는 자료 구조 중 아주 많이 쓰이는 두 가지 형태이며, 실생활에서도, 컴퓨터 내에서도 여러 방면으로 쓰인다.

 

 

 

 

출처:

[1] 학점은행제 교안

[2] 천 인국, et al. C언어로 쉽게 풀어쓴 자료구조. 생능출판, 2019