[Chap5] 연결 리스트 과제

문제 ) 교재에 있는 LinkedQueue를 Dequeue로 상속한다음, 앞에서추가하는 함수, 뒤에서 삭제하는 함수 를 추가하도록 고친다. 그리고, 앞에서 2번째 노드를 제거하고 1번째와 3번째 노드를 연결하는 메소드인 delete2nd를 추가한다. 이때, 3번째 노드가 없는 경우에는 NO를 출력한다.

#include <iostream>
using namespace std;

class Node {
private:
	int data;
	Node* link;
public:
	Node(int val = 0) : data(val),link(NULL) {}
	Node* getLink() { return link; }
	void setLink(Node* next) { link = next; }
	void display() { cout << data << endl; }
};

class LinkedQueue {
protected:
	Node* front;
	Node* rear;
public:
	LinkedQueue(): front(NULL), rear(NULL){}
	~LinkedQueue() { while (!isEmpty()) delete dequeue(); }
	bool isEmpty() { return front == NULL; }
	void enqueue(Node* p) {
		if (isEmpty()) front = rear = p;
		else {
			rear->setLink(p); //rear이 가리키는 노드가 노드p를 가리키도록
			rear = p; //rear이 이제 노드 p를 가리키도록
		}
	}
	Node* dequeue() {
		if (isEmpty()) return NULL;
		Node* p = front; //front가 가리키는 노드를 p가 가리키도록
		front = front->getLink(); //front가 다음 노드를 가리키도록
		if (front == NULL) rear = NULL; //만약 노드가 하나뿐이면 처리후 front가 null되는데, rear도 같이 0으로 만든다
		return p;
	}
	Node* peek() { return front; }

	void display() {
		cout << "[큐 내용] : " << endl;
		for (Node* p = front; p != NULL; p = p->getLink())
			p->display();
	}
};

여기까지 LinkedQueue이다. 이해하는데 많은 시간이 걸렸다.

class LinkedDeque : public LinkedQueue {
public:
	LinkedDeque(){}
	void enqueue(Node* p) { enqueue(p); }
	Node* dequeue() { return dequeue(); }
	Node* peek() { return peek(); }
	Node* getRear() { return rear; }
	void enqueueFront(Node* n) {
		if (isEmpty()) front = rear = n;
		else {
			n->setLink(front); //front가 가리키는 노드를 노드n를 가리키도록
			front = n; //front가 이제 노드 n를 가리키도록

		}
	}
	Node* dequeueRear() {
		if (isEmpty()) return NULL;
		Node* n = rear; //rear가 가리키는 노드를 n이 가리키도록
		if (front == rear) { // 큐에 노드가 하나만 있는 경우
			front = rear = NULL;
		}
		else {
			Node* prev = front; //front에서 시작해서 찾기
			while (prev->getLink() != rear) {
			//find의 링크가 rear로 연결되지 않으면(= 마지막의 바로 전이 아니면) 다음으로 넘어가기
			//이게 끝나면 find는 마지막의 바로 전 노드가 됨
				prev = prev->getLink();
			}
			rear = prev;
			rear->setLink(NULL);
		}
		return n;
	}

	void delete2nd() {
		if (front == NULL || front->getLink() == NULL) { // 노드가 0개 또는 1개인 경우
			cout << "NO" << endl;
			return;
		}
		Node* p = front; // 첫 번째 노드
		Node* q = p->getLink(); // 두 번째 노드
		Node* r = q->getLink(); // 세 번째 노드
		p->setLink(r); // 첫 번째 노드의 링크를 세 번째 노드와 연결
		delete q; // 두 번째 노드 삭제
		if (r == NULL) rear = p; // 삭제 후 마지막 노드인 경우 rear 변경
	}
};
int  main() {
	LinkedDeque que;
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		static int j = 1;
		int number;
		cin >> number;
		if (number == 1) {
			que.enqueueFront(new Node(j));
			j++;
		}
		else if (number == 2) {
			que.dequeueRear();
		}
		else if (number == 3) {
			que.delete2nd();
		}
	}
	que.display();
}