배열과 리스트로 큐 구현하기

큐에 대한 정의는 이미 알고 있다고 가정하고 "구현"에 초점을 맞춰 포스팅합니다

 

배열

로 큐를 구현할 때는 front 와 rear 를 가리키는 인덱스를 두개 선언합니다.

구현 자체는 쉽지만 한번 데이터를 꺼내면 해당 인덱스를 사용할 수 없어서 낭비될 수 있다.
-> 이에 보통 원형큐를 이용하여 낭비를 줄인다.

• push : 배열에 값을 삽입하고 rear++
• pop : 배열에서 값을 삭제하고 rear--

 

• front 가 rear를 추월했을 때 -> isEmpty
• rear가 배열 크기와 같아졌을 때 -> isFull

#include <iostream>

using namespace std;

const int maxSize = 5;

class QueueByArray {
public:
    bool isEmpty();
    bool isFull();
    
    void push(int v);
    int pop();
    
private:
    int front = 0;
    int rear = 0;
    
    int queue[maxSize];
};

bool QueueByArray:: isEmpty() {
    if(front == rear) return true;
    else return false;
}

bool QueueByArray:: isFull() {
    if( (rear+1) % maxSize == front) return true;
    return false;
}

void QueueByArray:: push(int v) {
    if(isFull()) return;
    
    rear = (rear+1) % maxSize;
    queue[rear] = v;
}

int QueueByArray:: pop() {
    if(isEmpty()) return -1;
    
    int tmp = front;
    front = (front+1) % maxSize;
    return queue[tmp];
}

리스트

로 큐를 구현할 때는 front 와 rear에 해당하는 노드를 선언한다.

• push : 값에 해당하는 노드 생성 후 rear 노드의 next를 새로운 노드를 가리키도록 설정
• Pop : front 노드의 값을 반환 후 삭제

 

• front 가 Null 일때 -> isEmpty

#include <iostream>

using namespace std;

class QueueByList {
public:
    struct node {
        int data;
        node* next;
    };
    
    bool isEmpty();
    
    void push(int v);
    int pop();
    
private:
    node* front = NULL;
    node* rear = NULL;
    
    int len = 0;
};

bool QueueByList:: isEmpty() {
    if(front == NULL) return true;
    else return false;
}

void QueueByList:: push(int v) {
    node* temp = new node();
    temp -> data = v;
    temp -> next = NULL;
    
    if(isEmpty()) front = rear = temp;
    else {
        rear -> next = temp;
        rear = temp;
    }
    
    len++;
}

int QueueByList:: pop() {
    if(isEmpty()) return -1;
    
    int val = front -> data;
    
    front = front->next;
    
    len--;
    return val;
}