본문 바로가기

Programming/Data Structure

자료구조 · C++로 구현한 큐



큐 (Queue)


큐는 선입선출(FIFO; First in First out) 방식의 선형 자료구조이다.

선입선출이란, 먼저 들어간 것이 먼저 나온다는 뜻이다. 즉, 큐는 먼저 들어간 데이터를 먼저 처리하는 자료구조이다.






Queue C++ 구현 소스코드


#include <iostream>
using namespace std;

const int MAX = 1e5;

class Queue {
private:
    int data[MAX];
    int index_front;
    int index_back;
public:
    Queue();
    bool empty();
    void push(int x);
    void pop();
    int front();
    int back();
    int size();
};

Queue::Queue() {
    index_front = 0;
    index_back = 0;
}

bool Queue::empty() {
    return index_front == index_back;
}

void Queue::push(int x) {
    index_back = (index_back+1) % MAX;
    data[index_back] = x;
}

void Queue::pop() {
    index_front = (index_front+1) % MAX;
}

int Queue::front() {
    return data[(index_front+1)%MAX];
}

int Queue::back() {
    return data[index_back];
}

int Queue::size() {
    return (index_back-index_front+MAX)%MAX;
}

int main() {
    Queue q;
    for (int i=1; i<=10; i++) q.push(i); // Push 1~10
    for (int i=1; i<=4; i++) q.pop(); // Pop 1~4
    for (int i=1; i<=4; i++) q.push(i); // Push 1~4
    cout << "* Size: " << q.size() << '\n';
    while (!q.empty()) {
        cout << "Pop: " << q.front() << '\n';
        q.pop();    // Pop all
    }
    return 0;
}


# main 함수 출력 결과


* Size: 10
Pop: 5
Pop: 6
Pop: 7
Pop: 8
Pop: 9
Pop: 10
Pop: 1
Pop: 2
Pop: 3
Pop: 4


✓ 배열로 구현한 원형 큐(Circular Queue)이다. 선형 큐(Linear Queue)보다 메모리 공간 활용이 더 효율적이다.

✓ 모듈러 연산을 통해 큐 내부를 순환하면 된다.

✓ 예외 처리는 하지 않았다.





Queue 클래스 설명


const int MAX = 1e5;

class Queue {
private:
    int data[MAX];
    int index_front;
    int index_back;
public:
    Queue();
    bool empty();
    void push(int x);
    void pop();
    int front();
    int back();
    int size();
};


✓ MAX는 큐의 최대 사이즈이다. 값을 바꾸면 최대 사이즈를 조절할 수 있다.

✓ Data는 큐에 넣은 원소를 저장하는 배열이다.

✓ index_front는 가장 먼저 넣은 원소의 위치를 가리키는 변수다.

✓ index_back은 가장 나중에 넣은 원소의 위치를 가리키는 변수다.



# 생성자와 empty 함수


Queue() {
    index_front = 0;
    index_back = 0;
}

bool empty() {
    return index_front == index_back;
}


✓ 생성자를 이용하여 Front 인덱스, Back 인덱스를 둘 다 0으로 초기화한다.

✓ empty 함수는 큐가 비어있는지 확인하는 함수이다. Front 인덱스와 Back 인덱스가 서로 같다면, 큐가 비어있는 상태이다.



# push 함수


void push(int x) {
    // Full check, if (index_front == (index_back+1)%MAX)
    index_back = (index_back+1) % MAX;
    data[index_back] = x;
}


✓ 큐에 원소를 집어넣는다. Back 인덱스를 1 증가시키고, 그 위치에 원소를 저장한다.

✓ 원소를 넣기 전에, 큐가 꽉 찬 상태인지 확인하여 예외 처리를 해야 한다. index_front == (index_back+1) % MAX 로 확인하면 된다. 큐 사이즈를 넉넉하게 두는 편이 좋다.



# pop 함수


void pop() {
    // Empty check
    index_front = (index_front+1) % MAX;
}


✓ 큐에서 가장 먼저 넣은 원소를 뺀다. Front 인덱스를 1증가시키면 된다.

✓ 원소를 빼기 전에, 큐가 비어있는 상태인지 확인하여 예외 처리를 해야 한다. 위에서 구현한 empty() 함수를 이용하면 된다.



# front, back 함수


int front() {
    // Empty check
    return data[(index_front+1)%MAX];
}

int back() {
    // Empty check
    return data[index_back];
}


✓ front 함수는 가장 먼저 넣은 원소가 무엇인지 보는 함수이다.

✓ back 함수는 가장 나중에 넣은 원소가 무엇인지 보는 함수이다.

✓ 두 함수 모두, 큐가 비어있는 상태인지 확인하여 예외 처리를 해야 한다.



# size 함수


int size() {
    return (index_back-index_front+MAX)%MAX;
}


✓ 큐에 몇 개의 원소가 들어있는지 확인하는 함수이다.



  • 혹시 2019.08.15 22:15 댓글주소 수정/삭제 댓글쓰기

    void Queue::push(int x) {
    index_back = (index_back+1) % MAX; ==> 이곳
    data[index_back] = x;
    }

    혹시 질문이있는데,, 위에 제가 화살표로 표시한 곳에 %MAX는 왜 해주는건가요..? 그냥 index_back을 +1만 해주고 뒤로 한칸 미뤄주기만 하면 되지 않나요..!?

    • 지나가는 사람 2019.09.03 02:37 댓글주소 수정/삭제

      %MAX를 붙히지 않으면 큐가 동작하긴 하지만 선형큐로 배열안에 공간을 일회성으로 밖에 쓰지 못합니다. 본문에 작성자님이 원형큐로 작성한다고 하셨고, %MAX(큐의최대사이즈) 연산을 하게 될경우 index_back이 최대인덱스를 가질때 0으로 초기화 되고, 그렇지 않을 경우 (index_back+1 ) % MAX = index_back+1 연산값이 나오게됩니다. 즉 다시말하면 index_back 최대값을 가지면 0으로 초기화 되어서 큐의 배열공간을 0인덱스부터 사용할 수 있게 되고 그렇지 않을 경우 그대로 값만 증가시키게 됩니다.