10845 큐 with C++

문제

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

10845번: 큐

자료구조중 하나인 Queue를 직접 구현해보는 문제입니다.

해결한 방법

pop에 대한 고민을 하다보니 먼저 생각난 방법은 front라는 변수를 두고 front값만 더해줘서 실제 배열에는 변화를 주지않는 방법이었습니다. 하지만 이 방법은 메모리를 낭비하게 될 것이라 생각했고 배열의 모든 요소를 다음 요소로 덮어씌우는 방법을 생각하게되었습니다. 제 생각으론 두 방법 모두 장단점이 있다고 생각해서 둘 다 구현하게 되었습니다.

 

첫번째 방법

1. front라는 내부변수를 두어서 pop을 호출할때 마다 front에 1을 더해주어서 다음에 배열에 접근할때 기준을 front로 두어 front보다 인덱스에는 접근을 막았습니다.
2. 그에 따라 나머지 내부함수들 또한 첫 주소인 0과 비교하거나 첫 자리를 호출할때 front를 넣어줬습니다.

#include <iostream>
using namespace std;

class Queue_rotate
{
private:
	int* que;
	int pos;
	int front_pos;
public:
	Queue_rotate() {
		que = new int[10000];
		pos = 0;
        front_pos = 0;
	}
	~Queue_rotate() {
		delete[] que;
	}
	void push(int x) {
		que[pos] = x;
		pos++;
	}
	int pop() {
		if (pos > front_pos) {
			front_pos++;
			return que[front_pos - 1];
		}
		else {
			return -1;
		}
	}
	int size() {
		return pos - front_pos;
	}
	bool empty() {
		return (pos == front_pos);
	}
	int front() {
		if (!empty())
			return que[front_pos];
		else
			return -1;
	}
	int back() {
		if (!empty())
			return que[pos - 1];
		else
			return -1;
	}
};

int main(){
	Queue_rotate myque;
	int line_num;
	cin >> line_num;
	cin.ignore();

	string command;
	int input_n;
	while (line_num--) {
		cin >> command;
		cin.ignore();
		if (command == "push") {
			cin >> input_n;
			cin.ignore();
			myque.push(input_n);
		}
		else if (command == "pop") {
			printf("%d\n", myque.pop());
		}
		else if (command == "size") {
			printf("%d\n", myque.size());
		}
		else if (command == "empty") {
			printf("%d\n", myque.empty());
		}
		else if (command == "front") {
			printf("%d\n", myque.front());
		}
		else {
			printf("%d\n", myque.back());
		}
	}
	return 0;
}

 

두번째 방법

1. pop을 제외한 내부함수들은 stack과 같이 구현했습니다.
2. pop함수는 모든 요소를 다음 요소로 덮어쓰는 방법으로 구현했습니다.

#include <iostream>
using namespace std;

class Queue
{
private:
	int* que;
	int pos;
public:
	Queue() {
		que = new int[10000];
		pos = 0;
	}
	~Queue() {
		delete[] que;
	}
	void push(int x) {
		que[pos] = x;
		pos++;
	}
	int pop() {
		if (pos) {
			int return_value = que[0];
			for (int  i = 0; i < pos-1; i++)
			{
				que[i] = que[i + 1];
			}
			pos--;
			return return_value;
		}
		else {
			return -1;
		}
	}
	int size() {
		return pos;
	}
	bool empty() {
		return (pos == 0);
	}
	int front() {
		if (pos)
			return que[0];
		else
			return -1;
	}
	int back() {
		if (pos)
			return que[pos - 1];
		else
			return -1;
	}
};

int main(){
	Queue myque;
	int line_num;
	cin >> line_num;
	cin.ignore();

	string command;
	int input_n;
	while (line_num--) {
		cin >> command;
		cin.ignore();
		if (command == "push") {
			cin >> input_n;
			cin.ignore();
			myque.push(input_n);
		}
		else if (command == "pop") {
			printf("%d\n", myque.pop());
		}
		else if (command == "size") {
			printf("%d\n", myque.size());
		}
		else if (command == "empty") {
			printf("%d\n", myque.empty());
		}
		else if (command == "front") {
			printf("%d\n", myque.front());
		}
		else {
			printf("%d\n", myque.back());
		}
	}
	return 0;
}

구현해보니 둘 사이 메모리사용량 차이는 없었고 시간소요 차이만 약간 발생했습니다.