[ 선형 자료구조 ] 스택(Stack) & 큐(Queue)

1. Stack

1) 개념

 

  스택은 LIFO(last-in-first-out), 즉, 후입선출 원칙을 따르는 선형 자료구조이다. 따라서 데이터의 출입은 한 방향에서만 이루어지고, 이름에 걸맞게 쌓아가는 구조를 가진다. 데이터에 대한 접근은 가장 위층에 대해서 가능하며, 삽입(push) / 삭제(pop) 연산 또한 가장 위층의 데이터에 대해서 가능하다. 스택에서 사용되는 주요 연산은 앞서 소개한 push, pop과 더불어 가장 위층의 데이터를 삭제하지 않고 반환하는 peek, 스택이 비었는지 여부를 반환하는 isEmpty 등이 있다.

 

2) 장점

1. 구조 자체가 간단하고 직관적이며, 구현이 쉽다.
2. 가장 마지막 데이터에대한 접근만 가능하므로 데이터에 대한 접근이 매우 빠르다.

 

3) 단점

1. 최대 할당 크기가 제한된다.(제한을 넘길 겨우를 stack overflow라 한다.)
2. 가장 위층의 데이터 이외의 경우 접근하기 비효율적이다.
3. 데이터를 지속적으로 보존하기에 알맞지 안핟.

 

3) 사용 예시

1. 데이터 순서 반전 (ex. 문자열 반전)
2. 웹 브라우저 뒤로가기
3. 함수호출 트래킹

 

 

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) 선형 큐 기본 연산

1. createQueue : 큐를 생성한다. front, rear는 -1로 초기화한다.
2. enQueue : 큐의 rear를 1 증가 시키고 해당 자리에 요소를 추가한다.
3. deQueue : front를 1 증가시키고 기존 자리의 요소를 빼낸다.(따라서 front 앞의 항목이 비어있을 수 있다.)
4. isFull : 큐가 다 찼는지 확인한다. rear가 마지막 인덱스와 동일 할 경우 true를 반환한다.(front 앞의 항목이 비어있어도 rear가 마지마 인덱스와 동일하면 true를 반환, 이를 해결하기 위해 원형 큐 가 사용된다.)
5. isEmpty : 큐가 비었는지 확인한다. front === rear인 경웅 true를 반환한다.
6. 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) 원형 큐의 기본 특성

1. 일차원 배열을 바탕으로 한다.
2. front, rear는 0(가장 처음 인덱스)로 초기화 된다.
3. 별도의 isFull, isEmpty를 가지지 않는다.
4. 배열의 포화 상태 여부 판단을 위해 1칸을 비워 두며, 이는 (rear + 1) % queueSize === front  따라 결정된다.
5. enQueue 연산 시 rear는 (rear + 1) % queueSize로 변경되고 해당 위치에 데이터를 저장한다. (포화 상태라면 enQueue 연산은 이루어지지 않는다.)
6.  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. enQueue 연산 실행

 

(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) 장점

1. 배열, 연결 리스트 등을 사용한 구현이 쉽다.
2. 요소의 삽입, 삭제가 효율적이다.

 

5) 단점

1. 크기가 제한적이다.
2. 할 수 있는 연산이 제한적이다.

 

6) 사용 예시

1. cpu 스케쥴링
2. 메세지 큐
3. Batch 프로세싱
4. Event-driven programming