[자료구조] Queue

• ADT( abstract data type): 자료구조의 추상화(요약)
  
  • data가 저장되어 있어야 함
  • data에 대한 기능이 나타나야 함
  • 예외처리가 나타나야 함

---

• Queue ADT: 임의의 객체를 저장하는 ADT, 추가와 삭제는 후입선출(FIFO,first in first out)을 따른다.
• 주요기능
  • enqueue: 가장 뒤(Rear)에 Data를 추가
  • dequeue: 가장 앞(Front)에 저장된 Data를 삭제

 

• 부가기능
  • front: 가장 앞에 저장된 Data를 반환
  • rear: 가장 뒤에 저장된 Data를 반환
  • size: 저장된 Data의 개수를 반환
  • empty: Queue가 비어있는지를 판단
• 예외 처리
  • Dequeue -> Queue가 비어 있는 경우
  • Enqueue -> Queue의 크기가 array의 size와 같은 경우(array기반 queue의 경우)
  • front, rear -> Queue가 비어 있는 경우
• 수행 시간 
  • Queue의 저장된 element수를 n이라 할 때
  • 공간은 O(n) 사용
  • 각 기능의 O(1) 시간 소요

#include <iostream>
#include <string>

using namespace std;

class node{//Linked List의 Node
private:
    node* next = nullptr;
    node* prev = nullptr;
    int data;
public:
    friend class Queue;
};//Double Linked List를 만들기 위해 next포인터와 prev포인터를 선언
class Queue{
private:
    node* head = nullptr;
    node* tail = nullptr;
    int size = 0;
public:
    bool empty(){return (getsize()==0);}//Queue가 비어있는지 판단하는 함수
    int getsize(){return size;}//size를 반환하는 함수
    void setsize(int size){this->size = size;}//size를 설정하는 함수
    void front(){//Queue의 front를 출력하는 함수
        if(empty()){//Queue가 비어있는 경우
            cout<<"Empty"<<endl;
        }
        else{//Queue가 비어있지 않으면 front의 data출력
            cout<<head->data<<endl;
        }
    }
    void rear(){//Queue의 rear를 출력하는 함수
        if(empty()){//Queue가 비어있는 경우
            cout<<"Empty"<<endl;
        }
        else{//Queue가 비어있지 않으면 rear의 data출력
            cout<<tail->data<<endl;
        }

    }
    void enQueue(int data){//Queue의 rear에 새로운 data 추가하는 함수
        node* newNode = new node;
        newNode->data = data;
        if(empty()){//Queue가 비어있는 경우
            head = tail = newNode; //추가된 노드가 front이자 rear
        }
        else{
            newNode->prev = tail;//새로운 노드의 prev는 기존 rear 노드를 가리킴
            tail->next = newNode;//기존 rear노드의 next는 새로운 노드로
            tail = newNode;//rear를 새로운 노드로 업데이트
        }
        setsize(getsize()+1);//노드가 추가 되었으므로 size증가
    }
    void deQueue(){//Queue의 front 삭제
        front();//삭제될 노드를 출력하기 위해 front함수 선언
        if(empty()){return;}//Queue가 비어있는 경우
        else if(getsize() == 1){//Queue에 data가 하나인 경우
            tail = head = nullptr;//front도 rear도 없음
        }
        else{
            head = head->next;//기존 front의 다음노드가 새로운 front로 업데이트
        }
        setsize(getsize()-1);//노드가 삭제 되었으므로 size감소
    }
    
};
int main(){
    int T = 0;
    Queue q;
    cin>>T;
    while(T--){
        string cmd;
        cin >> cmd;
        if (cmd == "enqueue"){
            int x;
            cin>>x;
            q.enQueue(x);
        }
        else if(cmd == "dequeue" ){
            q.deQueue();
        }
        else if(cmd == "isEmpty"){
            if(q.empty()){cout<<"True"<<endl;}
            else{cout<<"False"<<endl;}
        }
        else if(cmd == "front"){q.front();}
        else if(cmd == "rear"){q.rear();}
        else if(cmd == "size"){cout<< q.getsize() << endl;}
    }
    return 0;
}