[자료구조] queue

queue

1. queue

 

queue(큐)는 출구와 입구가 양쪽에 각각 있는 선형 자료구조이다.

즉, front에 데이터를 삽입하면 rear에서 빠져나온다.

이는 큐의 FIFO(First In First Out) 성질을 보장해주는데 먼저 들어간 데이터가 먼저 나온다는 뜻이다.

큐의 구조는 아래 그림과 같다.

 

 

이제 그림을 통해 삽입 과정을 이해해보자.

 

int형 데이터를 담는 큐에 5, 4, 2, 1을 순서대로 push해보자.

 

 

 

 

제일 먼저 들어간 5가 rear, 제일 마지막에 들어간 1이 front에 위치하고 있다.

 

그렇다면 처음 삭제 연산이 수행됐을 때 삭제되는 원소는 무엇일까?

rear에 위치하는, 즉 가장 먼저 들어온 5이다.

만약 삭제 연산이 2번 연속 수행된다면 5와 4가 차례로 삭제되고, 큐는 아래 그림과 같은 모습을 하고 있을 것이다.

 

 

 

앞서 스택은 연결 리스트를 통해 구현했으므로 큐는 배열을 통해 구현했다.

class Queue {
public:

	int *Q;
	int capacity;
	int n;
	int f, r;

	Queue(int capacity) {
		this->capacity = capacity;
		this->f = 0;
		this->r = 0;
		this->Q = new int[capacity];
		this->n = 0;
	}

	void push(int x) {
		if (n < capacity) {
			if (f == 0&&n==0) {
				Q[0] = x;
			}
			else {
				r += 1;
				Q[r] = x;
			}
			n++;
		}
		else
			return;
	}

	int pop() {
		if (n != 0) {
			int item = Q[f];
			f += 1;
			n--;
			return item;
		}
		else
			return -1;
	}

	int size() {
		return n;
	}

	int empty() {
		if (n == 0)
			return 1;
		else
			return 0;
	}

	int front() {
		if (n == 0)
			return -1;
		else {
			int item = Q[f];
			return item;
		}
	}

	int back() {
		if (n == 0)
			return -1;
		else {
			int item = Q[r];
			return item;
		}
	}
};