[자료구조 복습4] 원형 큐와 연결리스트 큐 구현하기

 

큐 란 무엇인가?

FIFO, "가장 먼저 들어온 것이 가장 먼저나가는 " 자료구조의 형태이다. 이는 영화관 매표소의 줄을 생각하면 쉽다. 가장 먼저 온 사람이 가장 먼저 티켓을 받고 줄에서 나간다!

 

그래서 큐는 리스트의 두군데에서 입출력을 담당한다. 스택의 경우 tail 즉 꼬리부분이 입출력을 모두 담당했지만, 큐의 경우 입력은 뒤에서! 출력은 앞에서 ! 담당한다. 그래서 각각 출력을 담당하는 부분을 front , 입력을 rear 라고 한다. 

 

그러면 이러한 큐를 어떻게 구현하는가 ?

일단 크게 세가지의 방법이 있다. 1) 배열리스트 구현 2)원형 배열 구현 3)연결리스트 구현

1번 배열리스트 구현은 너무 쉽게 구현되기 때문에 패스하고, 2번과 3번을 구현해보도록 하겠다.

 

먼저 원형큐를 살펴보자!

배열을 '원형'으로 만든다는 것은 무엇인가? 기존 배열리스트 같은 경우는 아무리 Dequeue가 진행되서 빈자리가 남아도, 그 자리에 다시 Enqueue를 할수 없었다. 그렇게 되면 Enqueue와 Dequeue의 연산이 섞이기 때문이다. 이를 위한게 바로 원형큐이다! 원형큐는 Dequeue가 되어서 남는 자리에 다시 요소를 넣을 수 있게 되어있다. 

 

1. 원형 큐가 empty일 때에는 front와 rear 모두 0을 가리킨다

2. 원형 큐에 삽입이 이루어지면, front는 맨 첫 요소의 앞을 가리키고, rear는 가장 늦게 들어온 요소를 가리킨다.

3. 원형 큐의 핵심은 바로 '원형'이다. 이를 위해서 삽입, 삭제 시 단순히 rear+=1 front+=1을 해주면 index 범위 에러가 난다. 따라서

 rear = (rear+1) % MAX_ARR 

 front = (front+1)%MAX_ARR 

로 계산을 해주면 배열의 마지막 인덱스값이 7일 때 , 그 다음 값은 0이 된다.

4. 원형 큐는 front 자리를 남겨둔다. 이는 empty 일때와 full일때를 구분하기 위함이다. 만약 front가 맨 처음 요소의 인덱스를 가지고 있는다고 한다면, 우리는 empty를 구분할 방법이 없다! (이렇게되면 rear와 front가 모두 맨 처음 들어온 요소를 가리키게 된다!) 따라서 empty일때는 front==rear이고, full 일때는 front가 rear의 한칸 앞에 있는 것을으로 구분해주도록 한다. 이 역시 원형큐의 법칙을 따라서  if ( (rear+1) % MAX_ARR == front ) 라고 조건문을 걸어준다!

 

다음은 cpp로 구현한 원형큐이다 . queue클래스 안에 동적 배열을 구현했다.

#include <iostream>
#include <vector>
using namespace std;

#define MAX_ARR 5
/*원형 큐 */
typedef int dataType;

class queue {

	dataType* que;
	int front, rear;
public:
	queue() { //생성자 
		que = new dataType[MAX_ARR];
		front = 0;
		rear = 0;
	}

	void enqueue(int x) {
		if (is_full()) {
			cout << " queue is full!" << endl;
			return;
		}
		rear = (rear + 1) % MAX_ARR;
		que[rear] = x;
	}

	dataType dequeue() {
		if (is_empty()) {
			cout << "queue is empty!" << endl;
			return -1;
		}
		front = (front + 1) % MAX_ARR;
		return que[front]; //front 증가, front +1에 있던 요소 반환
	}

	bool is_full() { //front가 rear보다 하나 앞에있을 때, 포화상태 
		if ((rear+1)%MAX_ARR == front) return true;
		else return 0;
	}

	bool is_empty() {
		if (front == rear) return true;
		else return false;
	}
	
	dataType peek() {
		if (is_empty()) {
			cout << "queue is empty!" << endl;
			return -1;
		}
		return que[(front + 1) % MAX_ARR];
	}

	void display() {
		for (int i = front + 1; i != (rear+1)%MAX_ARR; i= (i+1)%MAX_ARR)
			cout << que[i] << " ";
		cout << endl;
	}

	~queue() {
		delete[] que;
	}
};

 

 

다음은 연결리스트로 구현한 큐이다.

그동안 스택과 여러 연결리스트를 구현했던것과 구조는 같다. 다만 내부 연산이 조금 달라졌을뿐이다!

역시나 클래스 3개를 구현했다. 1) 데이터타입 클래스 (노드타입) (이는 구조체로 변경가능)

2) 연결리스트 클래스  3) 큐 클래스 이다.

아래가 소스코드이다.

#include <iostream>
using namespace std;

class dataType { 
public:
	int num; //data field
	dataType* next; //link field
};

class LinkedList { //연결리스트 
	dataType* front; //출력
	dataType* rear; //입력
	int countnum; //길이 

public:
	LinkedList() {
		front = NULL;
		rear = NULL;
		countnum = 0;
	}

	void insert(dataType* new_data) {
		if (front == NULL) { //가장 처음 삽입된 요소인 경우 
			front = new_data;
		}
		else {
			rear->next = new_data;
		}
		rear = new_data;
		countnum++;
	}

	int remove() {
		if (is_empty()) {
			cout << "queue is empty!" << endl;
			return -1;
		}
        dataType* removed=front;
		int num = front->num;
		countnum--;
		front = front->next; //front 옮겨준다. 
        delete removed; //메모리 해제 
		return num;
	}

	bool is_empty() {
		if (front == NULL) return true;
		else return false;
	}

	int get_length() {
		return countnum;
	}

	int peek() {
		if (is_empty()) {
			cout << "queue is empty!" << endl;
			return -1;
		}
		return front->num;
	}

	void display() {
		dataType* tmp = front;
		while (tmp != NULL) {
			cout << tmp->num << " ";
			tmp = tmp->next;
		}
		cout << endl;
	}
	~LinkedList() {
		DestroyLinkedList();
	}
	void DestroyLinkedList() {
		dataType* tmp = front;
		while (tmp != NULL) {
			tmp = tmp->next;
			delete front;
			front = tmp;
		}
		rear = front;
	}

};


class queue {
	LinkedList que;
public:
	void enqueue(int x) { //맨뒤에 삽입 
		dataType* new_data = new dataType();
		new_data->num = x;
		new_data->next = NULL;
		que.insert(new_data);
	}

	int deqeue() { //맨 앞의요소 삭제
		return que.remove();
	}

	int peek() { // 맨 앞의요소 반환
		return que.peek();
	}

	bool is_empty() { //큐가 비었는가 ? 
		return que.is_empty();
	}

	int get_length() { //큐의 길이
		return que.get_length();
	}

	void display() { //출력
		que.display();
	}
};

스택과 달라진 점은 삭제나 peek (top) 연산에서 tail대신 front 를 사용한다는 것이다.