C++로 구현하는 자료구조 (7) - Queue

c++로 구현하는 자료구조

이번 포스팅에서는 큐를 연결리스트를 이용해서 손쉽게 구현하는 방법을 알아보려고 한다. 큐는 그래프 탐색 방법 중 넓이 우선 탐색에서도 주로 사용되는 자료구조로 꼭 알아둬야 할 자료구조이다. 스택과 마찬가지로 내용은 쉬우나, 큐를 이용해서 문제를 풀이하는 방법을 떠올리는 연습을 해야한다.

 

---

1. Queue

First-in, First-out

큐는 이전 포스팅과 같은 선형자료구조로 First-in, First-out 형태를 지니고 있다. 큐는 일상생활에서도 많이 볼 수 있는 형태이다. 매표소에서 표를 받기위해 기다리는 사람들도 큐 형태이다. 큐도 스택처럼 연결리스트를 이용하면 매우 쉽게 구현할 수 있다. 메모리를 아끼는 방법으로 배열을 이용해서 환형으로 구성하는 방법도 있다.

 

2. Queue의 기능들

큐 자료구조를 지원하는 대부분의 언어들은 공통적으로 다음과 같은 연산들을 지원하고 있다.

• push : 자료를 큐의 끝 부분에 삽입한다.

• pop : 처음에 삽입한 자료를 제거한다. 경우에 따라서 리턴받는 경우도 있다.

• top : 처음에 삽입한 자료를 리턴받는다.

 

3. 소스코드

#pragma once
#include "LinkedList.h"

template<typename T>
class Queue {
private:
    int size;
    LinkedList<T>* container;
public:
    Queue() {
        this->size = 0;
        this->container = new LinkedList<T>();
    }

    void push(T element) {
        this->container->add(element);
    }

    T top() {
        return this->container->get(0);
    }

    void pop() {
        this->container->remove(0);
    }

    ~Queue() {
        delete this->container;
    }
};

#include <iostream>
#include <string>
#include "datastructure/Queue.h"

int main() {
    Queue<std::string>* queue = new Queue<std::string>();
    queue->push("test1");
    queue->push("test2");
    queue->push("test3");
    std::cout << queue->top() << std::endl;

    queue->pop();
    std::cout << queue->top() << std::endl;

    queue->pop();
    std::cout << queue->top() << std::endl;

}