<자료구조 알고리즘> 큐 구현

 

 

 

 

큐 구현

이번에는 큐을 구현해보자.

동적 배열을 이용해서도 구현을 할 수 있기는 하겠지만 크기가 계속 바뀌어야 하니 굉장히 비효율 적일 것이다. 또한 중간에 있는 데이터에 접근하는 일도 없을 테니 연결리스틀 사용하는 것이 더 효율적일 것이다.

데이터를 삽입하는 곳을 rear(뒤) 삭제하는 곳을 front(앞)이라고 하고 연결리스트 양 끝의 주소를 rearNode와 frontNode에 계속 저장해 놓을 것이다. 연결리스트가 연결되어있는 방향을 잘 보아야 한다. 위 사진과 같이 각 노드의 다음노드는 더 늦게 추가된 데이터를 가르키고 있어야 한다.

삽입 할 때에는 연결리스트의 한쪽 끝(rear)에 데이터를 넣고 그 주소를 rearNode에 저장한다.

삭제 할 때에는 frontNode에 다음 노드를 저장(frontNode = frontNode.next)하고 연결리스트의 반대쪽 끝(front)에 있는 데이터를 삭제한다.

 

유의 해야 할 떄가 빈 큐에 첫 원소를 추가할 떄이다. 이때는 rearNode의 값만 바꾸는 것이 아니라 frontNode의 값도 새로 추가한 데이터의 주소로 설정해 주어야 한다.

코드로 구현해 보면 다음과 같다.

 

 

template<typename T>
struct node
{
	T val;
	node* next;
	node(T val) : val(val), next(NULL) {};
	node() : val(NULL), next(NULL) {};
};

template<typename T>
class queue
{
private:
	node<T>* frontNode;
	node<T>* rearNode;
	int length;

public:
	queue() {
		frontNode = NULL;
		rearNode = NULL;
		length = 0;
	}

	void push(T val) {
		node<T>* curNode = new node<T>;
		curNode->val = val;
		if (length == 0) {
			frontNode = curNode;
		}
		else {
			rearNode->next = curNode;
		}
		rearNode = curNode;
		length++;

	}
	void pop() {
		if (length) {
			frontNode = frontNode->next;
			length--;
		}
	}
	T front() {
		if (length)
			return frontNode->val;
		else return NULL;
	}
	T back() {
		if (length)
			return rearNode->val;
		else return NULL;
	}
	int size() {
		return length;
	}
	bool empty() {
		if (length)
			return false;
		else
			return true;
	}
};

 

제대로 구현했는지 확인하기

https://www.acmicpc.net/problem/18258

18258번: 큐 2

백준에 18258번 문제를 이용하면 제대로 잘 구현했는지 확인 해 볼 수있다.

자신이 구현한 큐를 이용하여 위 문제를 풀어보자.

시간초과 난다면
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(0); 추가해 보세요.

 

#include <iostream>
#include <string>

using namespace std;

template<typename T>
struct node
{
	T val;
	node* next;
	node(T val) : val(val), next(NULL) {};
	node() : val(NULL), next(NULL) {};
};

template<typename T>
class queue
{
private:
	node<T>* frontNode;
	node<T>* rearNode;
	int length;

public:
	queue() {
		frontNode = NULL;
		rearNode = NULL;
		length = 0;
	}

	void push(T val) {
		node<T>* curNode = new node<T>;
		curNode->val = val;
		if (length == 0) {
			frontNode = curNode;
		}
		else {
			rearNode->next = curNode;
		}
		rearNode = curNode;
		length++;

	}
	void pop() {
		if (length) {
			frontNode = frontNode->next;
			length--;
		}
	}
	T front() {
		if (length)
			return frontNode->val;
		else return NULL;
	}
	T back() {
		if (length)
			return rearNode->val;
		else return NULL;
	}
	int size() {
		return length;
	}
	bool empty() {
		if (length)
			return false;
		else
			return true;
	}
};
int main() {
	int n, input;
	string s;
	queue<int> q;
	cin.tie(NULL);				//입출력 속도 빠르게 없으면 시간 초과 뜸
	cout.tie(NULL);
	ios::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		if (s == "push") {
			cin >> input;
			q.push(input);
		}
		else if (s == "pop") {
			if (q.size()) {
				cout << q.front() << "\n";
				q.pop();
			}
			else
				cout << -1 << "\n";

		}
		else if (s == "size") {
			cout << q.size() << "\n";
		}
		else if (s == "empty") {
			cout << q.empty() << "\n";
		}
		else if (s == "front") {
			if (q.size())
				cout << q.front() << "\n";
			else
				cout << -1 << "\n";
		}
		else if (s == "back") {
			if (q.size())
				cout << q.back() << "\n";
			else
				cout << -1 << "\n";
		}
	}
}

 

stl queue

맨날 구현해서 사용할 수는 없으니 이제는 C++ 표준라이브러리에서 제공하는 큐에 대해 알아보자

 

헤더파일

#include<queue>

선언

<>안에 자료형 맨 뒤에 이름 괄호 안에 크기를 적어 선언 할 수 있다.

queue<int> q;
queue<int> q(2); //크기 2

함수

 

q.empty();

큐가 비었으면 true 아니면 false 리턴

상수 시간 복잡도

 

q.size();

큐의 크기 리턴

상수 시간복잡도

 

q.back();

가장 마지막에 추가된 데이터 리턴

상수 시간복잡도

 

q.front();

가장 처음에 추가된 데이터 리턴

상수 시간복잡도

 

q.pop();

 

가장 처음 추가된 데이터 삭제

리턴값 없음

상수 시간 복잡도

 

q.push();

추가할 데이터 매개변수로 전달하면 추가

리턴 값 없음

상수 시간 복잡도

 

q1.swap(q2);

두 큐의 값을 서로 바꿈

바꾸고 싶은 큐를 매개변수로 전달

리턴 값 없음

상수 시간 복잡도

 

더 자세히 알아보고 싶다면 밑에 링크 참고

https://www.cplusplus.com/reference/queue/queue/