자료구조-큐

큐(Queue) : First-In First-Out(FIFO) 구조 ex) 매표소의 대기열과 같다

 

배열을 이용해서 큐를 만들기 위해서는 원형큐로 만들어야함

# CircularQueue.h

#define MAX_QUEUE_SIZE 100
#include <cstdio>

class CircularQueue {
protected:
	int front;
    int rear;
    int data[MAX_QUEUE_SIZE];
public:
	CircularQueue() { front = rear = 0; }
    bool isEmpty() { return front == rear; }
    bool isFull() { return (rear+1) % MAX_QUEUE_SIZE == front; }
    void enqueue(int val){
    	if(isFull()){
        	printf("error: 큐가 포화상태입니다\n");}
        else{
        	rear = (rear+1) % MAX_QUEUE_SIZE;
            data[rear] = val;
        }
    }
    int dequeue() {
    	if(isEmpty()){
        	printf("error: 큐가 공백상태입니다\n");}
        else{
        	front = (front+1) % MAX_QUEUE_SIZE;
            return data[front];
        }
   }
   int peek(){
   		if(isEmpty()){
        	printf("error: 큐가 공백상태입니다\n");}
        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");
   }
};

# CircularQueue.cpp

#include "CircularQueue.h"

int main(){
	CircularQueue que;
    for(int i = 1; i<10; i++){
    	que.enqueue(i);}
    que.display();
    que.dequeue();
    que.dequeue();
    que.dequeue();
    que.display();
    return 0;
}

이를 더 개선한 내용이 덱(deque): double-ended queue 이다. 전후단에서 삽입과 삭제가 가능하다.

// 위의 코드와 같이 구현 상속의 개념이 들어간다.
# CircularDeque.h

class CircularDeque : public CircularQueue {
public:
	CircularQueue(){}
    void addRear(int val){ enqueue(val);}
    int deleteFront() { return dequeue(); }
    int getFront() { return peek(); }
    
    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");
    }
    
    int getRear(){
    	if(isEmpty()){
        	printf("error : 덱이 공백상태입니다.\n")}
        else{ return data[rear];}
    }
    
    void addFront(int val){
    	if(isFull()){
        	printf("error : 덱이 포화상태입니다.\n");}
        else{
        	data[front] = val;
            front = (front -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
            }
    }
    int deleteRear(){
    	if(isEmpty()){
        	printf("error : 덱이 공백상태입니다.\n")}
        else{
        	int rest = data[rear]'
            rear = (rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
            return rest;
            }
    }
};

# CircularDeque.cpp

#include "CircularDeque.h"

int main(){
	CircularDeque deq;
    for(int i=1; i<10; i++){
    	if(i % 2){ deq.addFront(i); }
        else{ deq.addRear(i);}
    }
    deq.display();
    deq.deleteFront();
    deq.deleteRear();
    deq.deleteFront();
    deq.display();
    return 0;
}