[자료구조] 큐와 덱

큐(Queue)

앞에서 배운 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO였다면,

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out, 선입선출)의 특성을 가진다.

 

예를 들어 큐는, 매표소에 표를 사기 위해 줄을 선 사람들이라고 생각하면 된다. 줄의 맨 앞에 서있는 사람(=먼저온  사람)이 먼저 표를 사게 된다. 이것이 FIFO(First In First Out, 선입선출)이다.

 

큐는 뒤에서 새로운 데이터가 추가되고, 앞에서 데이터가 하나씩 삭제되는 구조를 가진다.

스택과의 차이점은, 스택은 데이터의 추가와 삭제가 같은 쪽에서 일어나지만,

큐는 데이터의 추가와 삭제가 다른 쪽에서 일어난다. 추가는 후단(Rear)에서, 삭제는 전단(front)에서 일어난다.

 

https://velog.io/@suitepotato/00004

 

큐는 스택과 마찬가지로 프로그래머들에게 폭넓게 사용되는 자료구조 중 하나이다.

 

컴퓨터를 이용하여 실세계의 실상황을 시뮬레이션 하는데 많이 사용된다.

예를 들어, 은행의 대기 줄이나 공항에서 이착륙하는 비행기 등을 시뮬레이션 하는데 큐가 사용된다.

그리고 운영체제에서도 많이 사용된다. 보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재한다. 이유는, 컴퓨터의 CPU와 주변 기기들 간의 속도 차이가 존재하기 때문이다. 

---

큐의 추상 자료형

1️⃣ create(max_size) : 최대 크기가 max_size인 공백 큐를 생성한다.

2️⃣ init(q) : 큐를 초기와 한다.

3️⃣ is_empty(q) 

4️⃣ is_full(q)

5️⃣ enqueue(q,e) : q의 끝에 e를 추가한다.

6️⃣ dequeue(q) : q의 맨 앞에 있는 e를 제거하여 반환한다.

7️⃣ peek(q) : q의 맨 앞에 있는 e를 읽어 반환한다.

 

---

큐의 구현

큐도 스택과 마찬가지로 배열이나 연결 리스트를 이용하여 구현할 수 있다.

 

1. 선형 큐(Linear Queue)

선형 큐에서 front는 큐의 첫번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.초기에는 front는 큐의 첫번째(front = 0)를, rear는 -1을 가리킨 상태에서 시작한다.

public class Linear_Queue {

	private int front;
	private int rear;
	private int maxSize;
	private Object[] queue;
	
	//Queue 생성
	public Linear_Queue(int maxSize) {
		this.front = 0;
		this.rear = -1;
		this.maxSize = maxSize;
		this.queue = new Object[maxSize];
	}
	
    //Queue 비었는지 확인
	public boolean empty() {
		return (front == rear + 1);
	}
	
    //Queue 꽉 찼는지 확인
	public boolean full() {
		return (rear == maxSize - 1);
	}
	
     //Queue에 item 입력
	public boolean enqueue(Object item) {
		if(full()) {
			System.out.println("Queue is FULL!");
			return false;
		}
		queue[++rear] = item;
		return true;
	}
	
    
    //Queue 가장 먼저들어온 데이터 출력
	public Object dequeue() {
		if(empty()) {
			System.out.println("Queue is EMPTY!");
			return false;
		}else {
			Object item = queue[front];
			queue[front] = null;
			front++;
			return item;
		}
	}
 }   

 

 

- 선형 큐의 한계

선형 큐 알고리즘은 Rear가 배열의 끝에 있으면, 앞에 빈 부분이 남아있더라도 더이상 삽입 연산을 하지 못한다.

==> 메모리를 효율적으로 관리하지 못한다. 이러한 한계를 극복하기 위해 나온 것이 원형 큐이다.

 

---

2. 원형 큐

https://hongpossible.tistory.com/entry/Java-%EC%9B%90%ED%98%95-%ED%81%90-%EA%B5%AC%ED%98%84

 

초기에 front와 rear는 [0]을 가리키고 있다. 

처음 데이터가 삽입되면, rear는 [1]을 가리키게 되고, front는 여전히 [0]에 위치한다.

https://hongpossible.tistory.com/entry/Java-%EC%9B%90%ED%98%95-%ED%81%90-%EA%B5%AC%ED%98%84

이렇게 계속 데이터를 삽입하다가, [3]까지 데이터가 차게 되면 "포화 상태"가 된다.

원형 큐에서는 공백 상태와 포화 상태를 구분하기 위해, 항상 한 자리를 비워두어야 한다.

 

front == rear인 경우는 공백 상태, front가 rear보다 한 자리 앞서 있으면 포화 상태가 된다.

https://hongpossible.tistory.com/entry/Java-%EC%9B%90%ED%98%95-%ED%81%90-%EA%B5%AC%ED%98%84

포화 상태에서 dequeue를 한다면, front가 [1]로 이동하고, [1]에 들어가있던 데이터를 삭제한다.

데이터 하나가 삭제되었으니 더이상 포화 상태가 아니다. 이제 또 새로운 데이터를 추가할 수 있다!

 

여기서 데이터를 하나 더 추가하고자 한다면, rear가 [3]에서 [0]으로 이동하며, [0]에 데이터를 새로 삽입하게 된다.

 

이제 코드를 살펴보자.

public class Queue {

	private int front;
	private int rear;
	private int maxSize;
	private Object[] queue;


	//Queue 생성
	public Queue(int maxSize) {
		this.front = 0;
		this.rear = 0;
		this.maxSize = maxSize;
		this.queue = new Object[maxSize];
	}
	
    //Queue 비었는지 확인
	public boolean empty() {
		return (rear == front);
	}
	
    //Queue 꽉 찼는지 확인
	public boolean full() {
		if(((rear + 1) % this.maxSize) == front)
			return true;
		else
			return false;
	}
	
     //Queue에 item 입력
	public boolean enqueue(Object item) {
		if(full()) {
			System.out.println("Queue is FULL!");
			return false;
		} else {
			rear = (++rear) % this.maxSize;
			queue[rear] = item;
			return true;
		}
	}
	
    
    //Queue 가장 먼저들어온 데이터 출력
	public Object dequeue() {
		if(empty()) {
			System.out.println("Queue is EMPTY!");
			return false;
		}else {
			front = (++front) % this.maxSize;
			return queue[front];
		}
	}
}

 

---

덱(Deque)

덱은 Double-ended queue의 줄임말로 큐의 앞과 두에서 모두 삽입과 삭제가 가능한 큐를 말한다. 

하지만 큐와 마찬가지로 중간에서의 삽입, 삭제는 허용하지 않는다.

---

덱의 추상 자료형

1️⃣ create() : 덱을 생성한다.

2️⃣ init(dq) : 덱을 초기와 한다.

3️⃣ is_empty(dq) 

4️⃣ is_full(dq)

5️⃣ add_front(dq,e)

6️⃣ add_rear(dq,e)

7️⃣ delete_front(dq)

8️⃣ delete_rear(dq)

9️⃣ get_front(q)

🔟 get_rear(q)

 

---

덱의 구현

원형 큐와 덱은 공통점이 많다. 원형 큐를 확장하면 덱도 쉽게 구현할 수 있다.

덱은 배열 보다는 연결 리스트로 구현하는 것이 훨씬 효율적이다.

연결리스트는..다시 공부해야하니 일단 참고자료만 남긴다.

 

st-lab.tistory.com/187

자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기

 

---

Reference

◎ c언어로 쉽게 풀어쓴 자료구조 Chapter.5 큐

◎ 원형 큐 : https://hongpossible.tistory.com/entry/Java-%EC%9B%90%ED%98%95-%ED%81%90-%EA%B5%AC%ED%98%84

◎ 선형 큐 : hahahoho5915.tistory.com/11?category=653539

◎ 덱 : st-lab.tistory.com/187