[C++로 쉽게 풀어쓴 자료구조] 4장 원형 큐와 원형 덱에 대해서 알아보는 시간!

안녕하세요 여니입니다!

오늘은 쉽게 풀어쓴 C++ 4장 예제소스에 대한 포스팅을 진행하려고 합니다~

지금 제가 올리는 원형큐 소스파일 인데요!

소스파일을 하나하나 분석하면서 공부하셔야 됩니다!

(그래야 이해가 되더라구요.. 저도 지금 그렇게 하는 중입니다)

 

<CircularQueue.h>

#include <cstdio>
#include <cstdlib>
#define MAX_QUEUE_SIZE 100
inline void error(const char * str) {
	printf("%s", str);
	exit(1);
}
class CircularQueue {
protected:
	int front; //front값
	int rear; // rear 값
	int data[MAX_QUEUE_SIZE]; //int형 배열 선언
public:
	CircularQueue() { front = rear = 0; } // 기본생성자, 초기화
	bool isEmpty() { return front == rear; } // 공백상태인지 확인
	bool isFull() { return rear == MAX_QUEUE_SIZE - 1; } // 포화상태인지 확인
	void enqueue(int x) { // 데이터를 넣는 함수
		if (isFull()) {
			error("Error : 큐가 포화상태 입니다");
		}
		else {
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = x;
		}
	}
	int dequeue() { //데이터를 삭제하는 함수
		if (isEmpty()) {
			error("Error: 큐가 공백상태입니다");
		}
		else {
			front = (front + 1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}
	int peek() { //데이터를 삭제하지 않고 반환만 하는함수
		if (isEmpty()) {
			error("Error: 큐가 공백상태입니다");
		}
		else {
			return data[(front + 1) % MAX_QUEUE_SIZE];
		}
	}
	void display() { // 담고 삭제한 큐 상태를 보여주는 함수 
		printf("큐 내용: ");
		int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
		for (int i = front + 1; i <= maxi; i++) {
			printf("[%2d]", data[i % MAX_QUEUE_SIZE]);
			
		}
		printf("\n");
	}
};

[출처]https://eboong.tistory.com/

 

헤더파일과 소스파일을 분할해서 저장해서 사용하는 습관을 들이는게 좋대서!

파일을 분할해서 했어요!

 

빌드하는건 cpp파일에서 하시면 됩니다

 

 

<Queue.cpp>

#include "CircularQueue.h"
void main() {
	CircularQueue q;
	for (int i = 1; i < 9; i++) {
		q.enqueue(i);
	}
	q.display();
	q.dequeue();
	q.dequeue();
	q.dequeue();
	q.display();
}

[출처]https://eboong.tistory.com/

 

결과값은 이렇게 나와요

 

한번씩 다들 돌려보세요~

 

이번엔 원형덱에 대해서 알아보려고 합니다

좀전에 원형큐에 대한 예제소스 다들 지우지 마세요!!!

왜냐면 원형큐 소스파일을 이용해서 원형덱을 구현할 것이기 때문이죠~!

 

일단 결과화면부터 보여드릴게요

덱은 큐랑 다르게 앞뒤에 데이터 추가가 가능하고 삭제도 가능합니다!

 

 

큐는 뒤에서 추가를 하고 앞에서부터 삭제를 했잖아요!?

그때 정의한 함수들을 재정의해서 덱 소스파일에서 활용할거에요!

 

<CircularDeque.h>

#include "CircularQueue.h" // 원형큐의 헤더파일을 include 시킵니다
class CircularDeque :public CircularQueue { // 원형큐 클래스를 상속합니다
public:
	CircularDeque(){}
	// 원형큐의 enqueue,dequeue,peek을 재정의해서 사용한다.
    
    void addRear(int val) { enqueue(val); } //큐를 이용한 원형 덱이라서 큐의 함수들을 재정의해서 사용한다.
	// addRear -> enqueue , deleteFront() --> dequeue, getFront()->peek();
	int deleteFront() { return dequeue(); }
	int getFront() { return peek(); }
    
    // 여기서부터의 함수들은 큐에 없는 기능이라 새로 정의합니다
	void addFront(int val) {
    
		if (isFull()) {
			error("error : 덱이 포화상태입니다");
		}
		else {
			data[front] = val;
			front = ((front - 1) % MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
		}
	}
	int deleteRear() {
		if (isEmpty()) {
			error("error : 덱이 공백상태입니다");
		}
		else {
			int ret = data[rear];
			rear = (rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
			return ret;
		}
	}
	int getRear() {
		if (isEmpty()) {
			error("error: 덱이 공백상태입니다");
		}
		else {
			return data[rear];
		}
	}
	void display() {
		printf("덱의 내용 ; ");
		int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
		for (int i = front + 1; i <= maxi; i++) {
			printf("[%2d]", data[i % MAX_QUEUE_SIZE]);
		}
		printf("\n");
	}

};

 

<덱 소스파일.cpp>

#include "CircularDeque.h"
void main() {
	CircularDeque d;
	for (int i = 1; i < 9; i++) {
		if (i % 2)d.addFront(i);
		else d.addRear(i);
	}
	d.display();
	d.deleteFront();
	d.deleteRear();
	d.display();

}

다음 포스팅에서 또 만나요!!