큐 (Queue)

큐

큐는 선착순에 비유할 수 있다.

먼저 온 사람이 먼저 들어가는 것처럼, 큐라는 자료구조 안에서는 먼저 들어온 데이터가 먼저 나간다.

이러한 구조를 FIFO (First-In, First-Out. 선입선출)라고 한다.

빈 큐.

큐에서는 앞부분, 즉 머리를 Front로 나타내고 뒷부분, 즉 꼬리를 Rear로 나타낸다.

데이터를 넣은 모습. (enqueue)

데이터가 하나뿐이므로 데이터=front=rear이다.

데이터를 이렇게 더 채워넣은 상태에서 데이터 삭제 함수(dequeue)를 호출하면 가장 앞의 데이터가 빠져나간다. 

따라서 front는 2라는 값을 가진 노드를 가리키게 된다.

양방향 연결 리스트로 구현하였습니다~ (거꾸로도 출력할 수 있어서..)

연결 리스트를 이용한 큐 구현

0 구조체 정의+초기화

#include<iostream> using namespace std; typedef struct _node{ int data; struct _node *next; struct _node *before; }Node; typedef struct _queue{ Node *front; Node *rear; int NumOfData; }Queue; void Initialize(Queue *q){ q->front = NULL; q->rear = NULL; q->NumOfData = 0; }

1 Enqueue

void EnQueue(Queue *q, int data){ Node *newnode = (Node*)malloc(sizeof(Node)); newnode->data = data; if (isEmpty(q)){ q->front = newnode; q->front->before = NULL; } else{ q->rear->next = newnode; newnode->before = q->rear; } q->rear = newnode; q->rear->next = NULL; (q->NumOfData)++; }

2 Dequeue

void DeQueue(Queue *q){ if (isEmpty(q)){ cout << "큐에 삭제할 수 있는 데이터가 없습니다" << endl; return; } Node *Dummy = (Node*)malloc(sizeof(Node)); Dummy = q->front; int result = Dummy->data; q->front = q->front->next; q->front->before = NULL; free(Dummy); cout << "Dequeued: " << result << endl; (q->NumOfData)--; }

3 isEmpty?

bool isEmpty(Queue *q){ if (q->NumOfData == 0) return true; return false; }

4 데이터 출력

void PrintQueue(Queue *q){ if (isEmpty(q)){ cout << "큐에 출력할 데이터가 없습니다" << endl; return; } Node *current = (Node*)malloc(sizeof(Node)); current = q->front; int num = q->NumOfData; cout << "----큐의 처음부터 출력합니다" << endl; while (num > 0){ cout << current->data << " "; current = current->next; num--; } cout << endl << endl; }

5 테스트용 메인 함수 + 결과

int main(){ Queue *q = (Queue*)malloc(sizeof(Queue)); Initialize(q); EnQueue(q, 1); EnQueue(q, 2); EnQueue(q, 3); PrintQueue(q); DeQueue(q); PrintQueue(q); return 0; }

+) 그러고보니 따로 쓰진 않았지만 제 코드에서는 데이터 삽입/삭제 부분에서 isEmpty함수를 쓰기 때문에 삽입/삭제 함수보다 먼저 써줘야 해요..!

-----------------------------------------------------------------------------------------------------------

참고용으로 봐주시고 부족한 부분 지적해주시면 감사드리겠습니다~