[C++ Fundamentals of Data Structures/C++ 자료구조론(이석호)] 4.6 연결 스택과 큐 연습 문제

1. 연결 스택을 위한 완전한 C++ 템플릿 클래스를 작성하고 테스트하라.

 

#include <iostream>
using namespace std;

template <class T> class LinkedStack;

template <class T>
class ChainNode {
public:
	ChainNode(T element = 0, ChainNode* next = NULL) {
		data = element;
		link = next;
	}

	friend class LinkedStack<T>;
	template <class T>
	friend ostream& operator<<(ostream& os, LinkedStack<T>& Is);

private:
	T data;
	ChainNode* link;
};

template <class T>
class LinkedStack {
private:
	ChainNode <T>* top;
public:
	LinkedStack() { top = NULL; }
	bool IsEmpty() { return top == NULL; }
	void push(int element) {
		top = new ChainNode<T>(element, top);
		cout << element << "이 추가되었습니다." << endl;
	}
	void pop() {
		ChainNode<T>* delNode = top;
		cout << top->data << "이 삭제되었습니다." << endl;
		top = top->link;
		delete delNode;

	}
	T& Top() { return top->data; }

	template <class T>
	friend ostream& operator<<(ostream& os, LinkedStack<T>& Is);
};

template <class T>
ostream& operator<<(ostream& os, LinkedStack<T>& Is) { 
	ChainNode<T>* cur = Is.top; //pop에 영향 주지 않기 위해
	
	while (1) {
		if (cur->link == NULL) {
			os << cur->data;
			break;
		}
		os << cur->data << "->";
		cur = cur->link;
	}

	os << endl;
	return os;

}

int main() {
	LinkedStack<int> intLS;
	int n;

	cout << "연결 스택 원소의 개수 : ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		int element;
		cout << "원소를 입력하세요 : ";
		cin >> element;
		intLS.push(element);
	}

	cout << endl << intLS << endl;

	intLS.pop();
	cout << intLS << endl;

	return 0;
}

// 출력

 

 

 

 

2. 연결 큐를 위한 완전한 C++ 템플릿 클래스를 작성하고 테스트하라.

 

#include <iostream>
using namespace std;

template <class T> class LinkedQueue;

template <class T>
class ChainNode {
public:
	ChainNode(T element = 0, ChainNode* next = NULL) {
		data = element;
		link = next;
	}

	friend class LinkedQueue<T>;
	template <class T>
	friend ostream& operator<<(ostream& os, LinkedQueue<T>& Iq);

private:
	T data;
	ChainNode* link;
};

template <class T>
class LinkedQueue {
private:
	ChainNode <T>* front;
	ChainNode<T>* rear;
public:
	LinkedQueue() { front = rear = NULL; }
	bool IsEmpty() { return front == NULL && rear == NULL; }

	void push(int element) {
		if (IsEmpty()) {
			cout << element << "이 추가되었습니다." << endl;
			front = rear = new ChainNode<T>(element, 0);
		}
		else {
			rear = rear->link = new ChainNode<T>(element, 0);
			cout << element << "이 추가되었습니다." << endl;
		}
	}

	void pop() {
		if (IsEmpty()) {
			cout << "큐가 비어있습니다. " << endl;
			return;
		}

		ChainNode<T>* delNode = front;
		cout << front->data << "이 삭제되었습니다." << endl;
		front = front->link;
		delete delNode;

	}
	T& Front() { return front->data; }
	T& Rear() { return rear->data; }

	template <class T>
	friend ostream& operator<<(ostream& os, LinkedQueue<T>& Iq);
};

template <class T>
ostream& operator<<(ostream& os, LinkedQueue<T>& Iq) {
	ChainNode<T>* cur = Iq.front; //pop에 영향 주지 않기 위해

	while (1) {
		if (cur == Iq.rear) {
			os << cur->data;
			break;
		}
		os << cur->data << "->";
		cur = cur->link;
	}

	os << endl;
	return os;

}

int main() {
	LinkedQueue<int> intLQ;
	int n;

	cout << "연결 큐 원소의 개수 : ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		int element;
		cout << "원소를 입력하세요 : ";
		cin >> element;
		intLQ.push(element);
	}

	cout << endl << intLQ << endl;

	intLQ.pop();
	cout << intLQ << endl;

	return 0;
}

//출력

 

 

* 3,4,5,6번은 생략

* 참고 : https://jaimemin.tistory.com/163