[11주차] 스택과 큐

4월 2일 자 학습 내용 정리입니다.

 

 

✅ 선형 구조와 비선형 구조

자료구조는 선형 구조와 비선형 구조로 나눌 수 있다.
선형 구조는 자료들이 순서를 가지고 연속된 자료구조를 의미한다.

반대로 비선형 구조는 일렬로 나열하기 힘들고 자료의 순서가 불규칙해서 연결 관계가 복잡한 구조를 말한다.

선형 구조에는 스택(Stack), 큐(Queue) 등이 존재하고 비선형 구조에는 트리(Tree), 그래프(Graph) 등이 존재한다.

 

 

✅ 스택

스택(Stack)은 한쪽 끝에서만 자료를 넣고 뺄 수 있는, Last-In First-Out(LIFO, 후입선출)의 특징을 가진 자료구조이다.

 

스택

스택이 지원하는 연산 목록은 아래와 같다.

• push : 자료 삽입
• pop : 자료 제거
• top : 스택의 가장 위에 있는 자료 반환(마지막에 넣은 값)
• empty : 스택이 비어있는지 여부 반환

 

파이썬에서의 스택은 append, pop 등의 연산을 지원하는 리스트로 구현한다.

 

 

✅ 큐

큐(Queue)는 스택과 달리 입구와 출구가 각각 한쪽 끝에 존재하는 자료구조이다.
따라서 큐는 First-In First-Out(FIFO, 선입선출)의 특징을 가진다.

 

큐

큐가 지원하는 연산 목록은 아래와 같다.

• push : 자료 삽입
• pop : 자료 제거
• front : 큐의 가장 앞에 있는 자료 반환(첫 번째로 넣은 값)
• back : 큐의 가장 뒤에 있는 자료 반환(마지막에 넣은 값)
• empty : 큐가 비어있는지 여부 반환

 

파이썬에서의 큐는 파이썬 기본 라이브러리인 queue 모듈의 Queue 클래스를 이용할 수 있다.

 

head와 rear

큐는 head와 rear라는 포인터를 가진다.
head는 큐의 첫 번째 원소를 가리키며 rear는 큐의 마지막 원소를 가리킨다.

큐의 push 혹은 pop 연산이 진행되면 head와 rear가 가리키는 것이 달라진다.
즉, push는 rear 포인터가 가리키는 위치에 자료를 추가하고 rear를 1 증가시키며 pop은 head 포인터가 가리키는 위치의 자료를 제거하고 head를 1 증가시킨다.

 

✔️ 원형 큐

하지만 큐에서 rear나 head가 큐의 끝에 도달할 경우 push, pop 연산을 할 공간이 사라진다.
따라서 이러한 상황을 막기 위해 원형 큐라는 개념이 등장했다.

원형 큐는 rear나 head가 큐의 끝에 도달하면 큐의 맨 앞으로 보내 위의 문제를 해결한다.

 

✔️ 링크드 큐

링크드 큐(Linked Queue)는 연결리스트로 구현한 큐이다.
링크드 큐의 경우 삽입과 삭제가 공간의 제약을 받지 않으며 크기의 제한 또한 존재하지 않다는 점이 편리하다.

 

 

✅ 스택과 큐의 사용 예시

✔️ 스택

스택이 활용되는 대표적인 예시는 콜 스택(Call Stack)이다.
콜 스택은 컴퓨터 프로그램에서 현재 실행 중인 함수(서브 루틴)를 저장하는 역할을 한다.

스택은 의존 관계가 있는 상태를 저장하므로 어떤 일보다 먼저 처리되어야 하는 일이 있다면 스택에 저장할 수 있다.

 

✔️ 큐

큐가 활용되는 대표적인 예시는 스케줄링(Scheduling)이다.
스케줄링은 운영체제가 프로세스를 관리하는 기법으로 동시에 실행되는 여러 프로세스에 CPU 등 자원 배정을 적절히 함으로써 성능을 개선할 수 있다.

스택과 달리 큐는 의존 관계가 없고 어떤 작업이 병렬적으로 이루어져도 괜찮다면 큐에 저장할 수 있다.

 

 

🔍 참조

비선형구조 https://www.scienceall.com/%EB%B9%84%EC%84%A0%ED%98%95-%EA%B5%AC%EC%A1%B0nonlinear-structure/