10. 스택&큐 활용 -a. 회문 확인하기.

회문 확인하기

  # 문자열을 큐와 스택에 각각 넣고, 빼서 확인하면 큐에 넣은 문자열은 그대로 나오고, 스택에 넣은 문자열은 뒤집어져서 나온다.

  # 이렇게 나온 문자를 각각 확인해서 모두 같으면 그 문자열은 회문이다.

  # 입력된 문자열의 길이를 확인할 수 있으므로 배열 기반 스택, 큐를 사용했다.

  # 배열 기반 큐를 원형큐로 만드는 부분은 삭제했다.

배열 기반 스택

 #pragma once

template <typename T>
class StackArray
{
	T* capacity;
	int size;

	int top;

public:
	bool Push(T data);
	bool Pop();

	T& Peek();
	
	int Count();
	int CapacitySize();

public:
	StackArray(int size);
	virtual ~StackArray();
};

template <typename T>
StackArray<T>::StackArray(int _size)
{
	size = _size;
	capacity = new T[size];
	top = -1;
}

template <typename T>
bool StackArray<T>::Push(T data)
{
	if (top == size - 1) {
		return false;
	}

	capacity[++top] = data;
	return true;
}

template <typename T>
bool StackArray<T>::Pop()
{
	if (top == -1) {
		return false;
	}

	top--;
	return true;
}

template <typename T>
T& StackArray<T>::Peek()
{
	return capacity[top];
}

template <typename T>
int StackArray<T>::Count()
{
	return top + 1;
}

template <typename T>
int StackArray<T>::CapacitySize()
{
	return size;
}

template <typename T>
StackArray<T>::~StackArray()
{
	delete[] capacity;
}

배열 기반 큐

 #pragma once

template <typename T>
class QueueArray
{
	T* capacity;

	int iCount;
	int iSize;

	int iFront;
	int iRear;

public:
	int Add(T data);
	int Remove();
	T   Peek();
	int Count();

public:
	QueueArray(int size);
	virtual ~QueueArray();
};


template <typename T>
QueueArray<T>::QueueArray(int size)
{
	capacity = new T[size];

	iSize = size;
	iCount = 0;

	iFront = 0;
	iRear = 0;
}

template <typename T>
int QueueArray<T>::Add(T data)
{
	if (iCount == iSize) {
		return iSize;
	}

	capacity[iRear++] = data;

	return ++iCount;
}

template <typename T>
int QueueArray<T>::Remove()
{
	if (iCount == 0) {
		return 0;
	}

	iFront++;

	return --iCount;

}

template <typename T>
T QueueArray<T>::Peek()
{
	return capacity[iFront];
}

template <typename T>
int QueueArray<T>::Count()
{
	return iCount;
}

template <typename T>
QueueArray<T>::~QueueArray()
{
	delete[] capacity;
}

메인

 #include "Queue_arrayt.h"
#include "Stack_array.h"

#include <iostream>

#include <tchar.h>

#if defined(UNICODE) || defined(_UNICODE)
#define tcout std::wcout
#define tcin std::wcin

#else
#define tcout std::cout
#define tcin std::cin

#endif

int main()
{
	TCHAR strBuf[256];

	std::cout << "회문인지 확인할 문장을 입력하세요." << std::endl;
	tcin >> strBuf;

	int strLen = _tcslen(strBuf);

	QueueArray<TCHAR> unreverse(strLen);
	StackArray<TCHAR> reverse(strLen);

	for (int i = 0; i < strLen; i++) {
		unreverse.Add(strBuf[i]);
		reverse.Push(strBuf[i]);
	}

	bool Palindromes;

	while (true) {
		if (unreverse.Peek() != reverse.Peek()) {
			Palindromes = false;
			break;
		}

		unreverse.Remove();
		reverse.Pop();

		if (reverse.Count() == 0) {
			Palindromes = true;
			break;
		}
	} 

	tcout << strBuf << std::endl;

	if (Palindromes) {
		tcout << "위 문자열은 회문입니다." << std::endl;
	}
	else {
		tcout << "위 문자열은 회문이 아닙니다." << std::endl;
	}

}