자료구조 · 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;
}

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

저작자표시 비영리 변경금지

티스토리툴바

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

티스토리툴바