[자료구조] 큐 Queue / 연결리스트를 이용한 큐의 구현

연결리스트를 이용한 큐의 구현

• 배열 대신 연결리스트로 원소들을 관리
  
  • 큐의 원소 : 단순 연결 리스트의 노드
  • 큐의 원소의 순서 : 노드의 링크 포인터로 연결
  • 변수 front : 첫 번째 노드를 가리키는 포인터 변수 (초기 null)
  • 변수 rear : 마지막 노드를 가리키는 포인터 변수 (초기 null)
• 주요 특징
  
  • 배열을 이용할 경우에 비해, 크기 제한이 거의 없음
  • 동적 메모리 할당으로 기억장소 사용에 제한이 적음
  • 큐에서 enQueue 및 deQueue 방법은 단순연결리스트의 삽입/삭제 방법과 거의 동일
    배열의 인덱스 대신 포인터 사용에 따른 부담은 존재
• 큐의 상태
  
  • 초기 상태 : front = rear = null
  • 공백 상태 : front = rear = null
  • 초기 상태와 공백 상태가 동일!
  • 큐가 꽉 차서 더 이상의 원소를 추가하지 못하는 경우는 거의 없음

 

#include <iostream>
using namespace std;

typedef int element;

class QNode{
public:
    element data;
    QNode *link;
    
    QNode(element value){
        data = value;
        link = NULL;
    }
};

class Queue{
public:
    QNode *front, *rear; //두개의 포인터 변수
    
    Queue(){
        front = rear = NULL; //초기화
    }
    
    bool is_empty(){
        return(front == NULL);
    }
    
    void enQueue(element value){
        QNode *new_node = new QNode(value);
        
        if(is_empty()){ //if (rear == NULL)
            front = rear = new_node;
        }
        else{
            rear->link = new_node;
            rear = new_node; //rear = rear->link;
        }
    }
    
    element deQueue(){
        if (is_empty()){
            cout<<"Queue UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            element x = front->data;
            front = front->link;
            if(front == NULL) rear = NULL;
            return(x);
        }
    }
    
    element peek(){
        if(is_empty()){
            cout<< "Queue UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return (front->data);
        }
    }
    
    void printQueue(){
        cout << "### Queue 상태: ";
        for(QNode *ptr = front; ptr != NULL; ptr = ptr -> link){
            cout << ptr->data <<" ";
        }
        cout << endl;
    }
};

int main(){
    Queue MyQueue;
    
    MyQueue.enQueue(10); MyQueue.printQueue();
    MyQueue.enQueue(20); MyQueue.printQueue();
    MyQueue.enQueue(30); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
    MyQueue.enQueue(40); MyQueue.printQueue();
    MyQueue.enQueue(50); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
}