data-structures
열
수색…
대기열 소개
큐는 FIFO (first-in, first-out) 데이터 구조입니다. 즉, 큐에 추가 된 첫 번째 요소는 제거 된 첫 번째 요소입니다 ( "first out").
도움을 기다리는 고객의 사례를 생각해 봅시다. Alice, Bob, Dan은 모두 슈퍼마켓에 있습니다. Alice는 지불 할 준비가되어 있으므로 계산원에 접근합니다. Alice가 대기열에 있습니다. 그녀는 대기열에있는 유일한 사람이므로 그녀는 앞과 뒤에 모두 있습니다.
이제 대기열은 다음과 같습니다.
|-------|
| Alice | cashier
|-------|
▲ ▲
back of queue ──┘ └── front of queue
이제 Bob과 Dan은 계산원에 접근합니다. 큐에 추가됩니다. 앨리스는 여전히 앞쪽에 있고, 댄은 뒤쪽에 있습니다.
|-------||-------||-------|
| Dan || Bob || Alice | cashier
|-------||-------||-------|
▲ ▲
back of queue ──┘ └── front of queue
대기열에 사람을 추가하는 것은 대기열 작업입니다. Alice, Bob 및 Dan이 대기열에 추가되었습니다. 출납원이 각 고객에게 도움을 주면 대기열에서 제거됩니다. 이것은 큐 꺼내기 작업입니다. 대기열의 데이터 요소를 나타내는 고객은 대기열의 전면에서 대기열에서 제외됩니다. 이것은 점원에게 접근 한 첫 번째 고객이 첫 번째 고객 (FIFO)임을 의미합니다.
배열을 사용하여 큐 구현.
도입부에서 언급 한대로 FIFO를 따르십시오. 5 가지 주요 작업 :
- Enqueue (x) : x를 큐의 뒤쪽으로 푸시합니다.
- Dequeue () : 큐의 앞쪽에서 요소를 팝합니다.
- isEmpty () : 큐가 비어 있는지 여부를 찾습니다.
- isFull () : 큐가 가득 차 있는지 여부를 찾습니다.
- frontValue () : 큐의 전면 값을 반환합니다.
모든 연산은 일정한 O (1) 시간입니다.
코드 :
#include<stdio.h>
#define MAX 4
int front = -1;
int rear = -1;
int a[MAX];
bool isFull() {
if(rear == MAX-1)
return true;
else
return false;
}
bool isEmpty() {
if(rear == -1 && front==-1)
return true;
else
return false;
}
void enqueue(int data) {
if (isFull()){
printf("Queue is full\n");
return;
} else if(isEmpty()) {
front = rear =0;
} else {
rear = rear + 1;
a[rear] = data;
}
}
void deque(){
if(isEmpty()){
printf("Queue is empty\n");
return;
} else if(front == rear) {
front =-1;
rear =-1;
} else {
front = front + 1;
}
}
void print(){
printf("Elements in Queue are\n");
for(int i = front;i<=rear;i++){
printf("%d ",a[i]);
}
printf("\n");
}
int frontValue(){
printf("The front element after set of enqueue and dequeue is %d\n", a[front]);
}
int main(){
deque(); // Queue is empty message will be thrown
enqueue(10);
print();
enqueue(20);
print();
enqueue(30);
print();
enqueue(40);
frontValue();
print();
enqueue(50);
frontValue();
deque();
deque();
enqueue(50);
frontValue();
print();
return 0;
}
순환 큐의 구현
메모리는 선형 큐와 비교하여 순환 큐에서 효율적으로 구성됩니다.
선형 대기열에서 :
순환 대기열에서
남은 공간을 사용할 수 있습니다.
동일한 작업 수행을위한 코드 :
#include<stdio.h>
#define MAX 10000
int front = -1;
int rear = -1;
int a[MAX];
bool isFull() {
if((rear+1) % MAX == front)
return true;
else
return false;
}
bool isEmpty() {
if(rear == -1 && front==-1)
return true;
else
return false;
}
void enqueue(int data) {
if (isFull()){
printf("Queue is full\n");
return;
} else if(isEmpty()) {
front = rear = 0;
} else {
rear = (rear+1) % MAX;
a[rear] = data;
}
}
void deque() {
if(isEmpty()){
printf("Queue is empty\n");
return;
} else if(front == rear) {
front =-1;
rear =-1;
} else {
front = (front+1) % MAX;
}
}
int frontValue() {
return(a[front]);
}
int main() {
deque();
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
enqueue(50);
frontValue();
return 0;
}
모든 연산에는 O (1) 시간 복잡도가 있습니다.
대기열의 연결된 목록 표현
링크 된리스트 표현은 메모리 관리 측면에서보다 효율적입니다.
O (1) 시간에 Linklist를 사용하여 대기열에 대기열 및 대기열을 표시하는 코드입니다.
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
node* next;
};
node* front = NULL;
node* rear = NULL;
void enqueue(int data){ //adds element to end
struct node* temp = (struct node*)malloc(sizeof(struct node*));
temp->data = data;
temp->next =NULL;
if(front== NULL && rear == NULL){
front = rear = temp;
return;
}
rear->next = temp;
rear= temp;
}
void deque(){ //removes element from front
node* temp = front;
if(front== NULL && rear == NULL){
return;
}
else if (front==rear){
front =rear = NULL;
}
else
front= front ->next;
free(temp);
}
void print(){
node* temp = front;
for(; temp != rear; temp=temp->next){
printf("%d ",temp->data);
}
//for printing the rear element
printf("%d ",temp->data);
printf("\n");
}
int main(){
enqueue(20);
enqueue(50);
enqueue(70);
printf("After set of enques\n");
print();
deque();
printf("After 1 deque\n");
print();
return 0;
}