-
[ 선형 자료구조 ] 스택(Stack) & 큐(Queue)Computer Science/자료 구조 2023. 1. 9. 13:55반응형
1. Stack
1) 개념
스택은 LIFO(last-in-first-out), 즉, 후입선출 원칙을 따르는 선형 자료구조이다. 따라서 데이터의 출입은 한 방향에서만 이루어지고, 이름에 걸맞게 쌓아가는 구조를 가진다. 데이터에 대한 접근은 가장 위층에 대해서 가능하며, 삽입(push) / 삭제(pop) 연산 또한 가장 위층의 데이터에 대해서 가능하다. 스택에서 사용되는 주요 연산은 앞서 소개한 push, pop과 더불어 가장 위층의 데이터를 삭제하지 않고 반환하는 peek, 스택이 비었는지 여부를 반환하는 isEmpty 등이 있다.
2) 장점
- 구조 자체가 간단하고 직관적이며, 구현이 쉽다.
- 가장 마지막 데이터에대한 접근만 가능하므로 데이터에 대한 접근이 매우 빠르다.
3) 단점
- 최대 할당 크기가 제한된다.(제한을 넘길 겨우를 stack overflow라 한다.)
- 가장 위층의 데이터 이외의 경우 접근하기 비효율적이다.
- 데이터를 지속적으로 보존하기에 알맞지 안핟.
3) 사용 예시
- 데이터 순서 반전 (ex. 문자열 반전)
- 웹 브라우저 뒤로가기
- 함수호출 트래킹
2. Queue
1) 선형 큐
(1) 개념
큐는 FIFO(first-in-first-out), 즉, 선입선출 원칙을 따르는 선형 자료구조이다. 따라서 큐는 특정한 순서를 따라 처리해야 하는 데이터를 저장할 때 주로 사용된다. 큐는 스택과 달리 삽입과 삭제가 양방향에서 이루어지며, 입력을 Enqueue 출력을 Dequeue라 한다. 이때 삽입이 이루어지는 부분(가장 뒷 부분)을 rear 삭제가 이루어지는 부분(가장 앞 부분)을 front라 한다. 스택과 유사하게 rear, front 부분에만 접근 가능하며, 큐에서 사용되는 주요 연산은 앞서 언급한 Enqueue, Dequeue 외에도 peek, isEmpty, size 등이 있다. (deQueue 실행시 front는 front + 1로 변경되고 enQueue 증가시 rear는 rear + 1로 변경 된다. )
(2) 선형 큐 기본 연산
- createQueue : 큐를 생성한다. front, rear는 -1로 초기화한다.
- enQueue : 큐의 rear를 1 증가 시키고 해당 자리에 요소를 추가한다.
- deQueue : front를 1 증가시키고 기존 자리의 요소를 빼낸다.(따라서 front 앞의 항목이 비어있을 수 있다.)
- isFull : 큐가 다 찼는지 확인한다. rear가 마지막 인덱스와 동일 할 경우 true를 반환한다.(front 앞의 항목이 비어있어도 rear가 마지마 인덱스와 동일하면 true를 반환, 이를 해결하기 위해 원형 큐 가 사용된다.)
- isEmpty : 큐가 비었는지 확인한다. front === rear인 경웅 true를 반환한다.
- qPeek : front의 값을 삭제하지 않고 확인한다.
(3) 선형 큐 구현 (javascript)
class Queue { constructor() { this.container = {}; this.front = -1; this.rear = -1; } enQueue(item) { if (this.front === -1) { this.front++; this.rear++; } else { this.rear++ } this.container[this.rear] = item; } deQueue() { if (this.front === -1) return undefined; let temp = this.container[this.front]; delete this.container[this.front] if (this.front === this.rear) { this.front = -1; this.rear = -1; } else { this.front += 1; } return temp } peek() { return this.container[this.front] } isEmpty() { if(this.front === -1) return true else return false } print() { return this.container; } }
2) 원형 큐
(1) 개념
원형 큐는 앞서 선형 큐에서 deQueue 연산 등에 의해 front가 0보다 큰 경우에도(값이 빠져나간 부분의 메모리가 비어있음에도) rear가 마지막 인덱스와 동일하면 isFull이 true를 반환하는 문제를 보완하기 위한 자료구조이다. 원형 큐가 가지는 특성은 아래와 같다.
(2) 원형 큐의 기본 특성
- 일차원 배열을 바탕으로 한다.
- front, rear는 0(가장 처음 인덱스)로 초기화 된다.
- 별도의 isFull, isEmpty를 가지지 않는다.
- 배열의 포화 상태 여부 판단을 위해 1칸을 비워 두며, 이는 (rear + 1) % queueSize === front 따라 결정된다.
- enQueue 연산 시 rear는 (rear + 1) % queueSize로 변경되고 해당 위치에 데이터를 저장한다. (포화 상태라면 enQueue 연산은 이루어지지 않는다.)
- deQueue 연산 시 front는 (front + 1) % queueSize로 변경되고 해당 위치의 데이터를 추출한다.(rear === front 라면 배열이 비었다고 판단하며, 연산이 실행 되지 않는다.)
(3) 원형 큐에서의 데이터 입출력
1. 생성과 함께 rear, front 0으로 초기화
2. enQueue 연산 실행
큐의 포화상태 여부 확인 후 포화상태가 아닐 시, rear를 (rear + 1) % queueSize로 이동 후 해당 위치에 데이터 삽입. 이는 데이터 g 삽입 까지 동일하게 작동하며 g 삽입 이후에 추가적인 enQueue는 deQueue 연산이 선행되지 않은 경우 불가능하다.
3. deQueue 연산 실행
deQueue 연산 실행 시 rear === front 조건에 따라 큐의 공백 여부를 판단하며, 빈 큐가 아닐 시 front는 (front + 1) % queueSize로 변경 되며 해당 위치의 데이터를 추출한다. 만약 위 두 번 더 deQueue 연산을 하려 한다면 공백 조건에 따라 한번만 실행 가능하다.
(4) 원형 큐 구현
class CircularQueue { constructor(size) { this.size = size; this.container = new Array(this.size).fill(null); this.front = 0; this.rear = 0; } enQueue(item) { if ((this.rear + 1) % this.size === this.front) return undefined this.rear = (this.rear + 1) % this.size; this.container[this.rear] = item; } deQueue() { if (this.front === this.rear) return undefined this.front = (this.front + 1) % this.size; let temp = this.container[this.front]; this.container[this.front] = undefined; return temp } print() { return this.container } }
4) 장점
- 배열, 연결 리스트 등을 사용한 구현이 쉽다.
- 요소의 삽입, 삭제가 효율적이다.
5) 단점
- 크기가 제한적이다.
- 할 수 있는 연산이 제한적이다.
6) 사용 예시
- cpu 스케쥴링
- 메세지 큐
- Batch 프로세싱
- Event-driven programming
반응형'Computer Science > 자료 구조' 카테고리의 다른 글
[ 비선형 자료구조 ] 트리 (0) 2023.01.18 [ 비선형 자료구조] 그래프 (0) 2023.01.11 [ 선형 자료구조 ] Vector (0) 2023.01.09 [ 선형 자료구조 ] 배열 & 리스트 (0) 2023.01.06 [ 선형 자료구조 ] 연결 리스트 - Circular Linked List(원형 연결 리스트) (0) 2023.01.04