[자료구조] 5일차 스택, 큐의 개념, 의미

스택, 큐의 개념

 

대표적인 자료구조의 예시

1. 선형구조 - 스택, 큐
2. : 자료가 순서를 가지고 연속되어 있음.
3. 비선형 구조 - 트리, 그래프
4. : 선형 구조에 해당하지 않는 자료구조

스택

: 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조

스택이 지원하는 연산목록 -push : 자료 넣기 -pop : 자료 빼기 -top : 가장 위에 있는 자료 반환 -empty : 스택 비어있는지 확인

 

 

스택 과정

: 나중에 들어간 자료가 먼저 출력되서 후입선출 자료구조라고 함.

큐

: 입구와 출구가 각각 한 쪽 끝에 존재

큐가 지원하는 연산 목록 -push : 자료 넣기 -pop : 자료 빼기 -front : 가장 앞의 자료 반환 -back : 가장 뒤의 자료 반환 -empty : 큐가 비어있는지 반환

: 배열을 이용하여 구현이 가능하기는 하지만 여러 문제가 존재

 

 

⚠️ 문제점

인덱스가 배열의 크기를 초과해서 push를 더 이상할 수 없음.

 

 

원형 큐

: 배열로 큐를 구현했을 때 문제점을 보완하기 위해 사용.

: rear나 haed가 의 끝에 도달하면 큐의 맨 앞으로 보냄.

링크드 큐

: 연결리스트로 구현한 큐

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

---

스택 : 나중에 들어온 자료가 먼저 출력

큐 : 먼저 들어온 자료가 먼저 출력

= 큐로 배열 구현했을 때 문제점 해결방법은 원형큐, 링크드 큐

 

 

스택, 큐의 의미

💡 스택과 큐는 컴퓨터 내에서 중요한 역할을 함.
스택, 큐 : 가장 기본적인 형태의 자료구조

 

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

1. 콜 스택(call stack)

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

= 50출력

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

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

 

예시2

1. n! 을 구하기 위해서는 n!을 먼저구해야 하므로 factorial(3)을 호출
2. 0!의 값은 1로 정의되어 있음. 조건문 통과 후 1 반환
3. factorial(n)의 반환값은 콜스택에 의해 factorial(n+1)에 전달.
4. factorial(4)의 반환값은 함수 바깥의 print로 전달되어 출력 = 24

여러 작업들 사이에 의존 관계가 있을 때 스택을 이용하여 표현

 

 

2. 스케줄링

: 운영체제가 프로세스를 관리하는 기법.

: cpu등의 자원 배정을 적절히 함으로써 성능 개선.

: 수행 완료한 작업들은 큐에서 pop하기

운영체제의 스케줄링 알고리즘은 매우 다양하지만 대체로 ‘큐’를 기반으로 스케줄링

작업들 사이에 의존관계가 없다면, 병렬적으로 이루어져도 괜찮을 때 큐 사용

---

스택 : 어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우

큐: 여러 작업들이 동시에(병렬적) 이루어져도 상관없는 경우