[자료구조] 스택과 큐를 이용하여 회문 판별 프로그램 만들기(C++)

https://mk-develop.tistory.com/5

[자료구조] 스택(Stack)이란?

https://mk-develop.tistory.com/6

[자료구조] 큐(Queue)란?

---

앞서 설명했던 스택과 큐를 이용하여 회문 판별 프로그램을 만들 수 있다.

스택은 후입선출, 큐는 선입선출 방식임을 응용한다.

---

함수 코드

---

bool Check_Palindrome(const char* _str)
{
	std::stack<char> s;
	std::queue<char> q;

	int len = strlen(_str);//len은 문자열의 길이이다. 
	for (int i = 0; i < len; i++)//문자열 길이만큼 반복. 
	{
		s.push(_str[i]);//큐와 스택에 문자열 push 
		q.push(_str[i]);
	}

	while (!s.empty())//스택이 빌 때까지 반복
	{
		if (s.top() != q.front())  
			return false;
		s.pop();//큐와 스택의 문자가 일치할 시 큐와 스택의 문자를 하나씩 뺌
		q.pop();
	}
	return true;//일치할시 true 반환 
}

문자열을 입력받으면 큐와 스택에 각각 push한 후 각 문자가 일치하는지 확인한다.

만약 일치하지 않는다면 false, 일치한다면 true를 반환한다.

 

level과 apple을 입력한 후 컴파일 결과를 확인해 보겠다.

---

level 입력결과

level은 회문이므로 true가 잘 반환된다.

apple 입력결과

apple은 회문이 아니므로 false가 반환된다.

---

전체코드

---

#include <iostream>
#include <cstring> 
#include <stack>
#include <queue>

using namespace std;

bool Check_Palindrome(const char* _str)
{
	std::stack<char> s;
	std::queue<char> q;

	int len = strlen(_str);//len은 문자열의 길이이다. 
	for (int i = 0; i < len; i++)//문자열 길이만큼 반복. 
	{
		s.push(_str[i]);//큐와 스택에 문자열 push 
		q.push(_str[i]);
	}

	while (!s.empty())//스택이 빌 때까지 반복
	{
		if (s.top() != q.front()) 
			return false;
		s.pop();//큐와 스택의 문자가 일치할 시 큐와 스택의 문자를 하나씩 뺌
		q.pop();
	}
	return true;//일치할시 true 반환 
}

int main(){
	char word[10];
	
	cout << "문자열을 입력해 주세요(최대 10자) : ";
	cin >> word;
	const char *w = word;//문자열 리터럴 상수로 초기화 
	
	cout << boolalpha;
	cout << Check_Palindrome(w);

	return 0;
}

전체코드는 다음과 같다.

main함수에서 문자열을 입력 받은 후, 입력 받은 문자열을 리터럴 상수로 초기화 하는 과정이 필요하다.

만약 초기화를 하지 않는다면 배열을 꽉 채운 문자열이 아닌 이상 항상 false가 출력될 것이다...

항상 포인터를 사용해서 필요한 공간만 할당하는 것이 중요하다.

문자열의 최대 입력값은 배열의 int값을 수정해서 원하는 길이로 받을 수 있게 만들 수 있다.