선입선출(FIFO : First-In First-Out)
먼저 들어온 데이터가 먼저 나가는 것.
맛집 웨이팅처럼!
연산
create : 큐를 생성한다
init : 큐를 초기화한다.
is_empty(q) : 큐가 비어있는지 검사한다.
is_full(q) : 큐가 가득찼는지 검사한다.
enqueue(q, e) : 큐의 뒤에 요소를 추가한다.
dequeue(q) : 큐의 앞에 있는 요소를 반환한 다음 삭제한다.
peek(q) : 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.
배열을 이용한 선형큐
front : 첫번째 요소 하나 앞의 인덱스
rear : 마지막 요소의 인덱스
#include <iostream>
#define MAX_QUEUE_SIZE 3
typedef int element;
typedef struct {
element queue[MAX_QUEUE_SIZE];
int front, rear;
}Queue;
void init(Queue *q){
q->front = q->rear = -1;
}
bool is_full(Queue *q){
return q->rear == MAX_QUEUE_SIZE -1;
}
bool is_empty(Queue *q){
return q->front == q->rear;
}
void enqueue(Queue *q, element e){
if(is_full(q)){
std::cerr << "Queue is full\n";
exit(-1);
}
q->queue[++q->rear] = e;
}
element dequeue(Queue *q){
if(is_empty(q)){
std::cerr << "Queue is empty\n";
exit(-1);
}
return q->queue[++q->front];
}
element peek(Queue *q){
if(is_empty(q)){
std::cerr << "Queue is empty\n";
exit(-1);
}
return q->queue[q->front + 1];
}
int main(){
Queue q;
init(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
std::cout << std::boolalpha << is_full(&q) << "\n"; // true
std::cout << dequeue(&q) << "\n"; // 1
std::cout << dequeue(&q) << "\n"; // 2
std::cout << peek(&q) << "\n"; // 3
std::cout << dequeue(&q) << "\n"; // 3
std::cout << std::boolalpha << is_empty(&q) << "\n"; // true
}
연결리스트를 이용한 연결된 큐
front : 첫번째 요소 하나 앞의 인덱스
rear : 마지막 요소의 인덱스
#include <iostream>
typedef int element;
typedef struct QueueNode{
element data;
QueueNode *link;
}QueueNode;
typedef struct{
QueueNode * front, *rear;
}linkedQueue;
void init(linkedQueue *q){
q->front = q->rear = nullptr;
}
bool is_full(linkedQueue *q){
return false;
}
bool is_empty(linkedQueue *q){
return q->front == nullptr;
}
void enqueue(linkedQueue *q, element data){
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
if(temp == nullptr){
std::cerr << "Memory Allocation Error\n";
return;
}
temp->data = data;
temp->link = nullptr;
if(is_empty(q)){
q->front = temp;
q->rear = temp;
}else{
q->rear->link = temp;
q->rear = temp;
}
}
element dequeue(linkedQueue *q){
if(is_empty(q)){
std::cerr << "Queue is empty\n";
exit(-1);
}
QueueNode *temp = q->front;
element data = temp->data;
q->front = q->front->link;
if(q->front == nullptr)q->rear = nullptr;
free(temp);
return data;
}
element peek(linkedQueue *q){
if(is_empty(q)){
std::cerr << "Queue is empty\n";
exit(-1);
}
return q->front->data;
}
int main(){
linkedQueue q;
init(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
std::cout << dequeue(&q) << "\n"; // 1
std::cout << dequeue(&q) << "\n"; // 2
std::cout << peek(&q) << "\n"; // 3
std::cout << dequeue(&q) << "\n"; // 3
std::cout << std::boolalpha << is_empty(&q) << "\n"; // true
}
'공부 > 자료구조' 카테고리의 다른 글
[자료구조] 우선 순위 큐(Priority Queue) (0) | 2023.05.12 |
---|---|
[자료구조] 이진트리(Binary Tree) (0) | 2023.05.11 |
[자료구조] 덱(Deque) (0) | 2023.04.30 |
[자료구조] 스택(Stack) (0) | 2023.04.26 |