본문 바로가기
학과공부/자료구조

Queue

by 유시은 2020. 10. 26.
개요

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

 

 

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

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가

www.acmicpc.net

#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();
}

'학과공부 > 자료구조' 카테고리의 다른 글

Heap  (0) 2020.12.03
Priority Queue  (0) 2020.12.03
Stack  (0) 2020.10.26
Doubly Linked List와 Iterator  (0) 2020.10.26
Singly Linked List  (0) 2020.10.26

댓글