[2022 정보처리기사] 자료구조 - 스택(Stack)과 큐(Queue)

Haribo·2022년 3월 1일

정보처리기사

목록 보기

5/10

📕 자료구조 - 스택(Stack)과 큐(Queue)

자료구조인 스택(Stack)과 큐(Queue)에 대해 알아보기

📌 스택(Stack)이란 무엇인가?

스택에 대한 그림

스택(stack)이라는 것은 "쌓다"라는 의미로, 책을 올려놓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말합니다.
설명을 좀 더 보태면, 위의 사진과 같이 데이터가 순서대로 쌓이고, 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조(Last In First Out/LIFO)를 가지고 있다.

책을 쌓아놓은 사진

간단한 예시로 위의 사진과 같이 책상에 책을 쌓아두는 것, 일회용 종이컵을 하나씩 꺼내 사용하는 것으로 들 수 있습니다.

📌 스택(Stack)의 특징

스택은 위의 사진과 같이 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해 삭제 가능합니다.

그리고 스택에서는 삽입 연산을 push, 삭제 연산을 pop이라 하며, 이러한 스택의 구조를 후입 선출의 구조라고 합니다.

📌 스택(Stack)의 사용 사례

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

🔑 큐(Queue)란 무엇인가?

큐에 대한 이미지

큐(Queue)의 사전적 의미는 1.(무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미합니다.

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

🔑 큐(Queue)의 특징

정해진 한 곳(top)을 통해 삽입, 삭제가 이루어지는 스택과 달리
큐는 한쪽 끝에서 삽입 작업이, 반대쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
이 때, 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 이루어지는 곳을 리어(rear) 로 정해 각각의 연산작업만 수행
큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)
프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라 부른다.