Queue

생성일: 2021년 10월 8일 오후 5:15

ADT Stack Operation

Transformers

• MakeEmpty
• Enqueue
• Dequeue

Observers

• IsFull
• IsEmpty

얼마나 Queue의 공간이 필요한지는 application level의 사용자만 알고 있다.

따라서 그들이 원하는 공간을 할당 할 수 있도록 item의 개수인 maxQue를 동적할당하여 사용한다.

(runtime에서 user에게 크기를 받아옴)

• template 사용

ItemType.h

#pragma once
#include <iostream>

const int MAX_ITEM = 25;
enum RelationType
{
	LESS,
	EQUAL,
	GREATER
};

class ItemType
{
public:
	RelationType ComparedTo(ItemType otherItem) const;
	void Print() const;
	void Initialize(int number);

private:
	int value;
};

RelationType ItemType::ComparedTo(ItemType otherItem) const
{
	if (value < otherItem.value)
		return LESS;
	else if (value > otherItem.value)
		return GREATER;
	else
		return EQUAL;
} //두 아이템을 비교하여 enum을 리턴

void ItemType::Print() const
{
	using namespace std;
	cout << value << endl;
}

void ItemType::Initialize(int number)
{
	value = number;
}

QueType.h

#pragma once
#include "ItemType.h"

template<class ItemType>
class QueType
{
public:
	QueType();
	QueType(int max);
	~QueType();	//Desctructor 동적 할당 해제를 위해 필수
	bool IsFull() const;
	bool IsEmpty() const;
	void Enqueue(ItemType item);
	void Dequeue(ItemType& item);
private:
	int front;
	int rear;
	int maxQue;
	ItemType* items;	//동적 할당을 위해 주소로 저장

};

template<class ItemType>
QueType<ItemType>::QueType()
{
	maxQue = 25;
	//Array의 제일 뒷칸으로 front와 rear를 위치시킴
	front = maxQue - 1;
	rear = maxQue - 1;
	items = new ItemType[maxQue]; //동적 할당
}

template<class ItemType>
QueType<ItemType>::QueType(int max)
{
	maxQue = max + 1;
	//Array의 제일 뒷칸으로 front와 rear를 위치시킴
	front = maxQue - 1;	
	rear = maxQue - 1;
	items = new ItemType[maxQue]; //동적 할당
}

template<class ItemType>
QueType<ItemType>::~QueType()
{
	delete[] items;
}

template<class ItemType>
bool QueType<ItemType>::IsEmpty() const
{
	return (rear == front);
}

template<class ItemType>
bool QueType<ItemType>::IsFull() const
{
	return ((rear + 1) % maxQue == front); //나머지(modular)연산 활용하여 circular structure에서 비교 가능
}

template<class ItemType>
void QueType<ItemType>::Enqueue(ItemType newItem)
{
	rear = (rear + 1) % maxQue;
	items[rear] = newItem;
}

template<class ItemType>
void QueType<ItemType>::Dequeue(ItemType& item)
{
	front = (front + 1) % maxQue;	//reserved공간 다음칸으로 이동
	item = items[front];
}

ContedQue.h

#pragma once
#include "QueType.h"

template<class ItemType>
class CountedQueType : public QueType<ItemType>	//상속
{
public:
	CountedQueType();
	void Enqueue(ItemType newItem);
	void Dequeue(ItemType& item);
	int LengthIs() const;

private:
	int length;	//변수에 현재 아이템 개수를 계속 트래킹 함.
};

template<class ItemType>
CountedQueType<ItemType>::CountedQueType() : QueType<ItemType>()
{
	length = 0;
}

//LengthIs 함수를 자주 사용한다면 CountedQueType이 적합하다.
template<class ItemType>
int CountedQueType<ItemType>::LengthIs() const
{
	return length;
}

template<class ItemType>
void CountedQueType<ItemType>::Enqueue(ItemType newItem)
{
	length++;	//이 작업이 계속되면 퍼포먼스 저하 => reserved공간을 남겨두는 방식을 더 자주 사용
	QueType<ItemType>::Enqueue(newItem);
}

template<class ItemType>
void CountedQueType<ItemType>::Dequeue(ItemType& item)
{
	length--;
	QueType<ItemType>::Dequeue(item);
}

Main.cpp

#include <iostream>
#include <ctype.h>
#include "QueType.h"
#include "CountedQueType.h"
#include "StackType.h"
using namespace std;

int main()
{
	//QueType<int> q;
	//q.Enqueue(1);
	//q.Enqueue(2);
	//q.Enqueue(3);
	//q.Enqueue(4);

	//int test;
	//q.Dequeue(test);
	//cout << test << endl;

	//cout << q.IsEmpty() << endl;
	//cout << q.IsFull() << endl;

	//cout << "Counted Test" << endl;

	//CountedQueType<int> countedQ;
	//countedQ.Enqueue(1);
	//countedQ.Enqueue(2);
	//countedQ.Enqueue(3);
	//countedQ.Enqueue(3);
	//countedQ.Enqueue(3);
	//countedQ.Enqueue(3);

	//cout << countedQ.IsEmpty() << endl;
	//cout << countedQ.IsFull() << endl;
	//cout << countedQ.LengthIs() << endl;

	//palindrome test(회문)
	StackType<char> stack;
	QueType<char> que;
	char ch;
	char sItem, qItem;
	int mismatches = 0;

	cout << "Enter string: " << endl;
	while (cin.peek() != '\n') {
		cin >> ch;
		if (isalpha(ch)) {
			if (!stack.IsFull())
				stack.Push(toupper(ch));
			if (!que.IsFull())
				que.Enqueue(toupper(ch));
		}
	}
	while ((!que.IsEmpty()) && (!stack.IsEmpty())) {
		sItem = stack.Top();
		stack.Pop();
		que.Dequeue(qItem);

		if (sItem != qItem)
			++mismatches;
	}
	if (mismatches == 0)
		cout << "That is palindrome" << endl;
	else
		cout << "That is not a palindrome" << endl;

	cout << mismatches << endl;
	return 0;
}