원형 큐

Eugenius1st·2022년 10월 4일
0

JavaScript_algorithm

목록 보기
15/21
post-thumbnail

큐와 스택 구현 비교

스택(Stack), 큐(Queue), 덱/데크(Deque) 객체를 보면 아시겠지만 Array 객체로 모두 구현이 가능하다. JavaScript의 Array 객체는 덱/데크(Deque)라고 생각하면 된다. 그리고 크기 제한을 하지 않으면 사용할 수 있는 메모리만큼 사용할 수 있다.

만약 직접 큐(Queue)를 만들어서 사용하면 무슨 문제가 생길까?

바로 데이터 Push와 Pop에 따른 큐(Queue)의 비효율적인 메모리 사용 문제이다.

큐(Queue) 데이터를 넣는 위치(rear)와 데이터를 가져오는 위치(front)가 다르다. 그래서 데이터를 넣고 가져오기를 반복하다 보면 더 이상 데이터를 넣을 수는 상태가 발생한다.

class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈를 구합니다.
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
  size() {
    return this.rear - this.front;
  }
  // queue에 element를 추가합니다.
  // 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}

한계 및 보완

배열로 선형 큐를 구현하면 Dequeue 할 때마다 앞의 공간이 비게 된다(앞에서 빠져나가므로). 이를 채우기 위해 데이터를 계속 앞으로 이동시키는 것도 문제다(불필요한 데이터 이동과 함께 처리 속도가 느려짐)

다른 문제로, 시작 부분(front)과 끝 부분(rear) 포인터를 이용하는 경우, rear가 맨 끝을 가리킬 때 큐가 다 차지 않았는데도 가득 차 있다고 인식해 새로운 원소를 추가하지 못한다.

그래서 큐(Queue)의 문제점을 해결한 것이 원형 큐(Circular Queue - 또는 환상 큐)이다.

검색해 보았다


굳이..?

이유는?

그렇다고 한다

원형 큐/환상 큐(Circular Queue)

원형 큐/환상 큐(Circular Queue)란, 데이터를 넣고 가져오는 방향이 없는 구조이다. 단 큐의 크기가 지정되어 있어야 한다. 그리고 front와 rear의 위치 계산을 위해 하나의 빈 공간이 있어야 한다. 그래서 실제 사용할 수 있는 큐의 크기는 전체 큐의 크기에서 1을 뺀 크기이다.

원형 큐/환상 큐(Circular Queue)의 모양은 큐(Queue)를 원형으로 만든 튜브나 도넛 모양이다.

위의 원형 큐/환상 큐(Circular Queue)의 크기(queueSize)는 6이다. 실제 데이터가 저장되는 크기는 5이다.

학습할 것

    1. 큐에 데이터 넣기
    1. 큐에서 데이터 가져오기
    1. 원형 큐 객체 생성하기

큐에 데이터 넣기

큐에 데이터를 넣기 위해서 rear의 다음 위치를 계산해야 한다.
rear에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 rear의 다음 위치이다.

큐의 크기로 나눈 나머지 값을 사용하는 이유는 큐가 원형처럼 사용하기 위해서 큐의 마지막 위치에 오면 큐의 시작 위치인 0부터 처리하게 하기 위해서이다.

rear = (rear + 1) % queueSize;
queue[rear] = data; --> 데이터 넣기

그런데 rear의 다음 위치가 front의 위치와 같다면 더 이상 큐에 데이터를 넣을 수 없는 포화 상태이다.

front == (rear + 1) % queueSize --> 큐 포화 상태S

큐에서 데이터 가져오기

큐에서 데이터를 가져오기 위해서 front의 다음 위치를 계산해야 한다. (rear의 위치 계산 공식과 동일하다.)

front에 1을 더하고 큐의 크기(queueSize)로 나눈 나머지 값이 front의 다음 위치이다.

front = (front + 1) % queueSize;
data = queue[front]; --> 데이터 가져오기
queue[front] = null; --> 빈 공간 처리

데이터를 가져오기 전에 front와 rear의 위치가 같으면 큐는 데이터가 없는 공백 상태이다.

front == rear --> 큐 공백 상태

업로드중..

위의 계산 공식으로 원형 큐 객체를 만들어보자

사전지식 : JavaScript Array - 배열 객체 생성

공부링크: https://carrotweb.tistory.com/184

Array 객체로 생성(new) 하면 빈 배열(Array) 객체(Object)가 생성된다.

var ar = new Array();
console.log(ar);
--> [] --> 빈 배열 객체
console.log(ar.length);
--> 0
console.log(typeof ar);
--> object
console.log(ar instanceof Array);
--> true
console.log(ar instanceof Object);
--> true

원형 큐/환상 큐(Circular Queue) 객체 생성하기

function()으로 CircularQueue 객체를 선언하겠습니다.
객체 생성할 때 큐의 크기를 받아서 큐를 초기화한다.

var CircularQueue = function(queueSize) {
	// Array 객체 생성
	this.queue = [];
	// 데이터 가져오는 위치
	this.front = 0;
	// 데이터 넣는 위치
	this.rear = 0;
	// 큐의 크기
	this.queueSize = queueSize;
	// 큐 초기화
	for (var index = 0; index < queueSize; index++) {
		this.queue.push(null);
	}
	// enqueue (큐에 데이터 넣기 함수) 
	this.add = function(data) {
		var result = true;
		if (this.isFull()) {
			console.log("Queue Full");
			result = false;
		} else {
			this.rear = (this.rear + 1) % queueSize;
			this.queue[this.rear] = data;
		}
		return result;
	}
	// dnqueue(큐에서 데이터 가져오기 함수)
	this.remove = function() {
		var result = null;
		if (this.isEmpty()) {
			console.log("Queue Empty");
		} else {
			this.front = (this.front + 1) % queueSize;
			result = this.queue[this.front];
			this.queue[this.front] = null;
		}
		return result;
	}
	// 큐에 데이터가 공백 상태인지 확인하는 함수
	this.isEmpty = function() {
		return (this.front == this.rear) ? true : false;
	}
	// 큐에 데이터가 포화 상태인지 확인하는 함수
	this.isFull = function() {
		return (this.front == (this.rear + 1) % this.queueSize) ? true : false;
	}
	// 큐 정보 출력 함수 ---- 이부분은 불필요----
	this.consoleLog = function() {
		console.log(this.queue);
		console.log("front: " + this.front + ", rear: " + this.rear);
	}
}

큐의 데이터와 front, rear의 위치를 알기 위해서 console로 출력하는 consoleLog 함수를 만들었다.

그리고 데이터를 넣는 함수 명을 add가 아닌 enqueue(인큐)로 데이터를 가져오는 함수 명을 remove이 아닌 dequeue(디큐)로 사용해도 된다.

function()으로 선언된 원형 큐/환상 큐(Circular Queue)를 생성(new) 하겠다.

var circularQueue = new CircularQueue(6);

console.log(circularQueue);
--> CircularQueue {queue: Array(6), front: 0, rear: 0, queueSize: 0, add: ƒ, remove: ƒ, isEmpty: ƒ, isFull: ƒ, consoleLog: ƒ}
console.log(typeof circularQueue);
--> object
console.log(circularQueue instanceof Object);
--> true
console.log(circularQueue instanceof CircularQueue);
--> true

circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 0, rear: 0

// 데이터 넣기
circularQueue.add("Data 1");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', null, null, null, null]
--> front: 0, rear: 1

// 데이터 넣기
circularQueue.add("Data 2");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', null, null, null]
--> front: 0, rear: 2

// 데이터 넣기
circularQueue.add("Data 3");
circularQueue.add("Data 4");
circularQueue.add("Data 5");
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 0, rear: 5

console.log(circularQueue.isFull());
--> true

// 데이터 넣기
circularQueue.add("Data 6");
--> Queue Full
circularQueue.consoleLog();
--> (6) [null, 'Data 1', 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 0, rear: 5

마지막 데이터는 큐가 포화 상태이기 때문에 추가되지 않고 "Queue Full"를 출력합니다. 그리고 리턴 값으로 false를 리턴한다.
add() 함수의 리턴 값이 false 이면 큐에 데이터를 더 이상 추가할 수 없는 포화 상태이다.

생성된 원형 큐/환상 큐(Circular Queue)에 데이터를 가져오겠다.

// 데이터 가져오기
var popData = circularQueue.remove();
console.log(popData);
--> Data 1
circularQueue.consoleLog();
--> (6) [null, null, 'Data 2', 'Data 3', 'Data 4', 'Data 5']
--> front: 1, rear: 5

// 데이터 가져오기
popData = circularQueue.remove();
console.log(popData);
--> Data 2
circularQueue.consoleLog();
--> (6) [null, null, null, 'Data 3', 'Data 4', 'Data 5']
--> front: 2, rear: 5

// 데이터 가져오기
popData = circularQueue.remove();
popData = circularQueue.remove();
popData = circularQueue.remove();
console.log(popData);
--> Data 5
circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 5, rear: 5

console.log(circularQueue.isEmpty());
--> true

// 데이터 가져오기
popData = circularQueue.remove();
--> Queue Empty
console.log(popData);
--> null
circularQueue.consoleLog();
--> (6) [null, null, null, null, null, null]
--> front: 5, rear: 5

마지막 데이터가 없기 때문에 가져오지 않고 "Queue Empty"를 출력합니다. 그리고 리턴 값으로 null를 리턴합니다.

remove() 함수의 리턴 값이 null이면 큐에 데이터가 없는 상태이다.

파이썬 원형큐 구현하기

파이썬은 deque 라이브러리가 있는데 굳이..? 구현 필요가 있나 싶다.

import sys
#sys.stdin = open("input.txt", "rt")

front = 0
rear = 0
MAX_SIZE = 10
queue = [0 for i in range(MAX_SIZE)]

# 큐가 비었는지 판단
def isEmpty():
    global front, rear
    return front == rear
# 큐가 꽉 찼는지 판단
def isFull():
    global front, rear, MAX_SIZE
    return front == (rear+1)%MAX_SIZE

# enqueue
def enqueue(item):
    global front, rear, MAX_SIZE
    if not isFull():
        rear = (rear + 1) % MAX_SIZE
        queue[rear] = item

# dequeue
def dequeue():
    global front, MAX_SIZE
    if not isEmpty():
        front = (front+1) % MAX_SIZE
        return queue[front]


enqueue(1)
enqueue(2)
enqueue(3)
print(333)
print(dequeue())

문제 - BOJ

https://www.acmicpc.net/problem/2161
https://www.acmicpc.net/problem/2164
https://www.acmicpc.net/problem/1158

개념 출처

js
https://carrotweb.tistory.com/190

py
https://piaflu.tistory.com/67=
https://wisetrue.tistory.com/229

profile
Eugenius1st
최강 프론트엔드 개발자가 되고싶은 안유진 입니다
이전 포스트

Tree

다음 포스트

해시(Hash)

0개의 댓글