[C++] 큐(Queue)를 연결리스트로 구현해보자

큐의 정의 : 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 스택과는 달리 리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트. 가장 먼저 리스트에 삽입된 원소가 가장 먼저 삭제되므로 선입 선출(先入先出)인 FIFO(first in first out) 리스트라고 한다.

[네이버 지식백과] 큐 [queue] (컴퓨터인터넷IT용어대사전, 2011. 1. 20., 전산용어사전편찬위원회)

 

#include <iostream>
using namespace std;

class LinkedList {
private:    
    class Node {
    public:
        int data;
        Node* next;
    };    

    Node* Head = new Node;    
    Node* newNode = new Node;    
public:                                          
    LinkedList() { 
        Head->next = NULL;                                
    }

    void insert(int num) {       
        Node* Cursor = Head;
        Node* newNode = new Node;        
        newNode->data = num;                       
        
        //노드가 없을 때
        if (Head->next == NULL) {
            Head->next = newNode;
            newNode->next = NULL;
        }
        else {      //노드가 하나라도 있을 때
            while (Cursor->next != NULL) {
                Cursor = Cursor->next;
            }

            Cursor->next = newNode;
            newNode->next = NULL;
        }        
    }

    void printall() {        
        Node* Cursor;
        Cursor = Head->next;

        while (Cursor != NULL) {
            cout << Cursor->data << "-->";
            Cursor = Cursor->next;
        }
        cout << "끝" << endl;
    }

    int remove() {
        Node* temp = Head->next;
        if (Head->next != NULL) {
            int tempNum = temp->data;
            Head->next = Head->next->next;

            delete(temp);
            return tempNum;
        }
        else {
            return -1;
        }        
    }

    int isEmpty() {
        if (Head->next == NULL) {
            return 1;
        }
        else {
            return 0;
        }
    }    
};

int main() {
    LinkedList myList;  int num;
    //myList.init();  // 시작 포인터 초기화 생성자를 배웠으므로 생략
    while (cin >> num) {
        myList.insert(num);
    }
    myList.printall();  // 모든 항목을 입력된 순서대로 출력한다.

    //// 이제 하나씩 빼자.    
    while (!myList.isEmpty()) {
        num = myList.remove();
        cout << "빼낸 항목: " << num << endl;
        myList.printall();  // 남은 항목을 출력
    }
    return 0;
    
}

 

Linked list로 구성된 정수를 삽입할 수 있는 큐를 구현해봤습니다.

 

insert 메소드에서 삽입한 순서대로 저장되며 ( 예: 1, 2, 3 을 입력했다면  1-> 2-> 3 순서로 저장)
remove 메소드는 첫째 항목을 삭제하면서 동시에 값을 돌려줍니다.


실행 예: 
11 22 33 44 입력시:

시작: 11-->22-->33-->44-->끝
빼낸 항목: 11
시작: 22-->33-->44-->끝
빼낸 항목: 22
시작: 33-->44-->끝
등등