09-1 큐

큐: 선입선출, 먼저 들어온 데이터가 먼저 나가는 자료구조
전단: 삭제위치, 후단: 삽입위치

선형큐

• 큐의 시작 포인터: front, 끝 포인터: rear
• 초기 상태: front = rear = -1
• 자료 삽입 -> rear += 1
• 자료 삭제 -> front +=1
• 공백 상테: front == rear
• 포화 상태 = rear = n-1 (베열의 경우)

선형큐의 문제점

• front, rear의 포인터 위치가 정해져 있기 때문에 새로운 데이터를 추가하거나 삭제하는 경우, 공간 낭비가 발생할 수 있다.
  
  

원형큐

• 선형큐의 문제점을 해결한 방법
• 큐의 처음과 끝이 연결되어 있는 구조
• 초기 상태: front = rear = 0
• 공백 상태: front == rear
• 포화 상태: front % MAX == (rear+1) % MAX
• front 포인터가 가리키는 자리는 항상 비어있다
• 삽입과 삭제는 modulo 연산으로 front와 rear의 위치를 계산한다.
• 자료 삽입: rear = (reaer + 1) % MAX
• 자료 삭제: front = (front + 1) % MAX

#include<iostream>
using namespace std;

inline void error(char* str){
	cerr << str << endl;
	exit(1);
};

#define MAX_QUEUE_SIZE 100

class CircularQueue{
protected:
	int front;
	int rear;
	int data[MAX_QUEUE_SIZE];
public:
	CircularQueue(){
		front = rear = 0;
	}
	~CircularQueue(){	}
	bool isEmpty(){return front == rear;}
	bool isFull(){return (rear+1) % MAX_QUEUE_SIZE == front;}
	void enqueue(int val){
		if(isFull()) error("포화상태\n");
		else{
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}

	int dequeue(){
		if(isEmpty()) error("공백상태\n");
		else{
			front = (front +1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}

	int peek(){
		if(isEmpty()) error("공백상태\n");
		else return data[(front+1) % MAX_QUEUE_SIZE];
	}

	void display(){
		cout << "큐 내용 : ";
		int maxi = (front<rear) ? rear : rear + MAX_QUEUE_SIZE;
		for(int i=front+1; i<=maxi; i++){
			cout<<"["<<data[i%MAX_QUEUE_SIZE] << "] ";
		}
		cout << endl;
	}	
};

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

링크드리스트를 이용한 큐

• 장점: 크기가 제한되지 않고 필요한 메모리만 사용할 수 있다.
• 단점: 링크 필드가 추가되기 때문에 메모리 공간을 더 사용한다. 코드가 복잡하다.

#include<iostream>
using namespace std;

class Node{
public:
    int data;
    Node* next;
    Node(int val){
        data = val;
        next = NULL;
    }
};

class CirculaLinkedlist{
private:
    Node* tail;
    int size;
public:
    CirculaLinkedlist(){
        tail = NULL;
        size = 0;
    }

    //add 함수
    void add(int val){
        Node* new_node = new Node(val);
        if(tail == NULL){
            tail = new_node;
            tail -> next = tail;
        }
        else{
            new_node -> next = tail->next;
            tail -> next = new_node;
            tail = new_node;
        }
        size++;
    }
    //remove 함수
    void remove(int val){
        if(tail == NULL) return;
        Node* cur = tail->next;
        Node* prev = tail;
        do{
            if(cur->data == val){
                prev->next = cur -> next;
                if(cur == tail){
                    tail = prev; 
                }
                delete cur;
                size--;
                return;
            }
            prev = cur;
            cur = cur->next;
        }while(cur != tail->next);
    }

    //display 함수
    void display(){
        if(tail==NULL) return;
        Node* cur = tail->next;
        do{
            cout<< cur -> data << " ";
            cur = cur -> next;
        }while(cur != tail->next);
        cout << endl;
    }
    //get_size 함수
    int get_size(){return size;}
};

int main(){
    CirculaLinkedlist list;
    list.add(1);
    list.add(2);
    list.add(3);
    list.display();
    list.remove(2);
    list.display();
    cout<<list.get_size()<<endl;
    return 0;
}