[알고리즘/C++] - 큐(Queue),평 , 큐,, 평,,큐,,WER

오늘은 큐에 대해서 알아보도록 하겠습니다.

 

https://www.youtube.com/watch?v=ImuWa3SJulY

Q.

WER..

입니다^^

 

선입선출의 자료구조. 대기열이라고도 한다. Queue라고도 하는데, Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.

오늘도 나무위키와 함께합니다.

말 그대로 큐(Queue)는 먼저 들어온 데이터가 먼저 빠져나가고 쓰입니다. 짜장면 먼저 시켰는데 나중에 시킨 사람 짜장면이 나왔다면 기분이 나쁩니다.. 그런 문제를 해결하기 위해 큐가 있습니다!(?)

데이터를 추출하게 된다면 가장 먼저 넣었던 예전 데이터가 빠져나오고, 데이터를 삽입하게 된다면 가장 나중에 넣은 데이터 뒤로 들어가게 됩니다.

삽입과 삭제를 하는데 있어 O(1)이라는 빠른 속도를 가지기 때문에 상황에 맞게 사용한다면 아주 유용한 알고리즘입니다.

 

Queue에 자주 사용되는 함수는 다음과 같습니다.

 

 

이전에 포스팅한 Stack와 비슷한 용도지만 확실히 다른 개념이기 때문에 헷갈리지 말고 잘 기억해둡니다.

스택하면 나서스! 큐하면 유미!

stack<int> q;	큐를 선언합니다.
q.pop();	가장 먼저 들어왔던 데이터를 삭제합니다.
q.push(n);	데이터를 가장 뒤로 추가합니다.
q.front();	가장 먼저 들어왔던 데이터를 조회합니다.
q.back();	가장 나중에 들어왔던 데이터를 조회합니다.
q.size();	원소의 개수를 확인합니다.
q.empty();	데이터가 비어있는지 체크합니다.

 

다음 작성한 예제는 큐를 구현해본 코드입니다. 

동적 배열로 큐를 처리하였고, front, back의 코드는 구현하지 않았습니다.

#include <iostream>

using namespace std;

struct queue {
	int length = 5;
	int stindex = 0, enindex = 0;
	int* p = new int[length];
	bool empty() {
		return stindex == enindex;
	}
	~queue() {
		delete[] p;
	}

	int size() {
		if (enindex > stindex) return enindex - stindex;
		else return (enindex + (length - stindex)) % length;
	}
	int front() {
		if (Empty() == true) return 0; //비어있는 경우 처리
		return *(p + stindex);
	}
	void push(int num) { //push_back
		if (((enindex + 1) % length) == stindex) { //3만큼 큰 배열 동적할당
			int newSize = length + 3;
			int* temp = new int[newSize];
			for (int i = 0; i < length - 1; ++i) temp[i] = p[(stindex + i) % length];
			p = temp;
			stindex = 0;
			enindex = length - 1;
			length = newSize;
		}
		p[enindex] = num;
		enindex = (enindex + 1) % length;

	}
	void pop() {
		stindex = (stindex + 1) % length;
	}
	bool IsFull() {
		return (enindex + 1) % length == stindex;
	}
};

스택과 마찬가지로 이 알고리즘 또한 <Queue>라는 라이브러리를 통해 C++에 제공되고 있습니다.

 

https://solved.ac/problems/tags/queue

solved.ac

큐를 통한 문제풀이도 재밌으니 한두문제 정도 풀어보시는 것을 추천드립니다.

.

궁금한 점이나 잘못된 사항이 있다면 댓글로 문의 부탁드립니다 감사합니다!

반응형