자료구조 -02. 스택과 큐

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' '자료구조' 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

스택과 큐

01. 스택, 큐의 개념

대표적인 자료구조의 예시

선형 구조		비선형 구조
스택 (Stack)	큐 (Queue)	트리 (Tree)	그래프 (Graph)

선형구조: 자료가 순서를 가지고 연속되어 있음

비선형 구조 : 선형 구조에 해당하지 않는 자료구조

스택

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조 스택이 지원하는 연산 목록 • push: 스택에 자료를 넣는연산 • pop: 스택에서 자료를 빼는연산 • top: 스택의 가장 위에 있는 자료를 반환하는 연산 • empty: 스택이 비어있는지 여부를 반환하는 연산

나중에 들어간 자료가 먼저 출력되기 때문에 Last In First Out(LIFO)(후입선출) 자료구조라고도 한다. 

파이썬의 리스트는 append, pop 등의 연산을 지원하므로 리스트를 이용하여 스택을 구현할 수 있다.

큐

입구와 출구가 각각 한 쪽 끝에 존재하는 자료구조 큐가 지원하는 연산 목록 • push:큐에 자료를 넣는 연산 • pop: 큐에서 자료를 빼는 연산 • front: 큐의 가장 앞에 있는 자료를 반환하는 연산 • back: 큐의 가장 뒤에 있는 자료를 반환하는 연산 • empty:큐가 비어있는지 여부를 반환하는 연산

선형 자료구조이기 때문에 배열을 이용하여 구현이 가능하기는 하지만 여러 문제가 존재한다.

배열로 구현된 크기가 6인 큐가 있다.
head와 rear는 인덱스를 나타내며, 큐에 포함되어있는 내용은 head 이상 rear 미만의 인덱스들이다.

 

 

 

push - rear 위치에 자료를 추가하고 rear를 1 증가시킴

pop - head 위치의 자료를 제거하고 head를 1 증가시킴

 

마지막 그림의경우 크기가 6인 큐에 자료가 4개 들어있고, 빈 공간이 2개 있는 상태

그러나, 위의 경우에는 rear가 가리키는 인덱스가 6이기 때문에 자료를 추가할 수 없다.

인덱스가 배열의 크기를 초과했기 때문이다.

 

배열로 큐를 구현하였을 때의 문제점을 보완하기 위한 자료구조 => '원형 큐'

원형 큐

원형 큐의 경우, rear나 head가 큐의 끝에 도달하면 큐의 맨 앞으로 보내어 문제를 해결

링크드 큐 (Linked Queue)

연결 리스트로 구현한 큐를 '링크드 큐' 라고 한다.

삽입과 삭제가 제한되지 않는 점과, 크기의 제한이 존재하지 않는 점이 편리

import queue
q = queue.Queue()

큐를 실제로 사용하고자 할 때는 파이썬 기본 라이브러리의 queue 모듈의 Queue 클래스를 사용

정리

스택과 큐는 선형 구조고, 선형 구조는 자료들이 순서를 가지고 연속된 자료구조이다.

스택은 나중에 들어온 자료가 먼저 출력되고, 큐는 먼저 들어온 자료가 먼저 출력된다.

 

파이썬의 리스트(배열)를 사용하여 구현할 때 스택은 간편하게 구현이 가능하지만 큐의 경우는 여러 문제점이 발생

큐를 배열로 구현하였을 때의 문제점을 해결하는 방법은 원형큐,링크드큐 등 존재

스택과큐를실제로사용하고자할때 스택은 그냥 파이썬의 리스트를, 큐는 queue 모듈의 Queue 클래스를 사용

02. 스택, 큐의 의미

스택과 큐의 의미

스택과 큐는 컴퓨터 내에서 중요한 역할을 갖고 있기 때문이다.

그리고 스택과 큐는 가장 기본적인 형태의 자료구조 중 하나이며

스택과 큐로 해결할 수 있는 문제인지 알기 위해서는 스택과 큐의 의미를 알고 있어야 한다.

스택이 활용되는 대표적 예시

콜 스택(Call Stack): 컴퓨터 프로그램에서 현재 실행 중인 함수(서브루틴)을 저장하는 역할

 

스택은 의존관계가 있는 상태를 저장한다.

어떤 일보다 더 먼저 처리되어야 하는 일이 있다면, 스택에 저장할 수 있다.

 

팩토리얼 연산의 정의를 코드로 옮긴 factorial 함수이다.

이 함수는 재귀함수, 즉 자기 자신을 호출하는 함수이다

 

# 𝑛!를 구하기 위해서는 (𝑛−1)!를 먼저 구해야 했던 것처럼 여러 작업들 사이에 의존관계가 있을 때
스택을 이용하여 표현할 수 있다.

큐가 활용되는 대표적 예시

스케줄링(Scheduling)

운영 체제가 프로세스를 관리하는 기법으로
동시에 실행되는 여러 프로세스에 CPU 등의 자원 배정을 적절히 함으로써 성능을 개선할 수 있다.

 

여러프로세스를동시에수행할수있게하기위한기법인

시분할 시스템을 비롯하여 운영체제의 스케줄링 알고리즘은 매우 다양하지만

대체로 '큐'를 기반으로 스케줄링을 관리하고 있다.

 

어떤 작업이 병렬적으로 이루어져도 괜찮을 때, 작업들 사이에 의존관계가 없다면 큐에 저장하여 관리할 수 있다.

정리

스택	큐
어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우	여러 작업들이 동시에(병렬적으로) 이루어져도 상관없는 경우
의존관계가 있는 경우	의존관계가 없는 경우