Queue

개요

한 쪽 끝에선 삽입, 다른 쪽 끝에선 삭제가 일어나는 자료구조

 

 

Queue의 성질

First-in First-out (FIFO), 즉 선입선출 방식으로 객체를 담는다.

 

rear에 삽입하고 front에서 삭제한다.

 

 

Queue

대표적인 operation은 enqueue, dequeue가 있고, 추가로 front, size, empty 등을 지원할 수 있다.

 

Array 또는 Linked List로 구현할 수 있다.

 

Array의 크기를 변경하기 곤란하다는 점을 고려하여 환형으로 구성하면 시간복잡도를 낮출 수 있다.

 

배열에서 큐의 시작점, 끝점, 크기를 기억하는 변수를 만들어서 구현할 수 있다.

 

아래는 Array기반 큐의 구현 예시이다. (Linked list 기반 큐는 SLL과 똑같다.)

 

struct ArrayQueue {
    int* que;
    int maxSize, f, r, n;
   
    ArrayQueue(int ms) {
        maxSize = ms;
        f = r = n = 0;
        que = new int[maxSize];
        for (int i = 0; i < maxSize; ++i) que[i] = 0;
    }
   
    void enqueue(int data);
    int dequeue();
}

 

예외처리

빈 큐에 dequeue, front를 호출하거나 Array 기반 큐가 가득 찼을 때 enqueue를 호출하면 예외가 발생한다.

 

 

Implementation

아래는 이론에서 배운 내용을 구현한 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

struct ArrayQueue {
	int* que;
	int maxSize;
	int f, r, n;

	ArrayQueue(int ms) {
		maxSize = ms;
		f = r = n = 0;
		que = new int[maxSize];
		for (int i = 0; i < maxSize; ++i) que[i] = 0;
	}

	int size() {
		return n;
	}
	bool empty() {
		return (n == 0);
	}
	int front() {
		if (empty()) return -1;
		return que[f];
	}
	int rear() {
		if (empty()) return -1;
		return que[(f + n - 1) % maxSize];
	}
	void enqueue(int e) {
		if (n == maxSize) {
			cout << "Full\n"; return;
		}
		que[r] = e;
		r = (r + 1) % maxSize;
		n++;
	}
	int dequeue() {
		if (n == 0) return -1;
		int ret = que[f];
		f = (f + 1) % maxSize;
		n--;
		return ret;
	}
};

struct Node {
	int data;
	Node* next;

	Node(int e) {
		data = e;
		next = nullptr;
	}
};

struct SLLQueue {
	Node* head;
	Node* tail;
	int sz;

	SLLQueue() {
		head = nullptr;
		tail = nullptr;
		sz = 0;
	}

	bool empty() {
		return (!head);
	}
	int size() {
		return sz;
	}
	int front() {
		if (empty()) return -1;
		return head->data;
	}
	int rear() {
		if (empty()) return -1;
		return tail->data;
	}
	int dequeue() {
		if (empty()) return -1;
		Node* oldHead = head;
		int ret = oldHead->data;
		head = oldHead->next;
		delete oldHead;
		sz--;
		if (!head) tail = nullptr;
		return ret;
	}
	void enqueue(int e) {
		Node* newNode = new Node(e);
		if (tail) tail->next = newNode;
		tail = newNode;
		if (!head) head = newNode;
		sz++;
	}
};

int main() {
	int S, TEST; cin >> S >> TEST;
	ArrayQueue Q(S);
	// SLLQueue Q;

	while (TEST--) {
		string oper; int p; cin >> oper;
		if (oper == "enqueue") {
			cin >> p; Q.enqueue(p);
		}
		if (oper == "dequeue") {
			cout << Q.dequeue() << "\n";
		}
		if (oper == "size") {
			cout << Q.size() << "\n";
		}
		if (oper == "isEmpty") {
			cout << (Q.empty() ? 1 : 0) << "\n";
		}
		if (oper == "front") {
			cout << Q.front() << "\n";
		}
		if (oper == "rear") {
			cout << Q.rear() << "\n";
		}
	}
}

 

응용

카드2 boj.kr/2164

2164번: 카드2

#include <bits/stdc++.h>
using namespace std;

struct ArrayQueue {
	int* que;
	int maxSize;
	int f, r, n;

	ArrayQueue(int ms) {
		maxSize = ms;
		f = r = n = 0;
		que = new int[maxSize];
		for (int i = 0; i < maxSize; ++i) que[i] = 0;
	}

	int size() {
		return n;
	}
	bool empty() {
		return (n == 0);
	}
	void enqueue(int e) {
		if (n == maxSize) {
			cout << "Full\n"; return;
		}
		que[r] = e;
		r = (r + 1) % maxSize;
		n++;
	}
	int dequeue() {
		if (n == 0) return -1;
		int ret = que[f];
		f = (f + 1) % maxSize;
		n--;
		return ret;
	}
};

int main() {
	int n; cin >> n;
	ArrayQueue Q(n);
	for (int i = 1; i <= n; ++i) {
		Q.enqueue(i);
	}

	while (1) {
		if (Q.size() > 1) Q.dequeue();
		if (Q.size() > 1) Q.enqueue(Q.dequeue());
		if (Q.size() == 1) break;
	}

	cout << Q.dequeue();
}