대기열 소개 및 배열 구현 - TECHCODEVIEW.COM

큐와 유사하게 데이터 저장을 위해 작업이 수행되는 특정 순서를 따르는 선형 데이터 구조가 있습니다. 순서는 선입선출(First In First Out)입니다 (FIFO) . 대기열은 줄의 시작 부분부터 시작하여 순차적으로 무언가를 받기 위해 기다리는 사람들의 줄로 상상할 수 있습니다. 이것은 삽입이 후면이라고 하는 한쪽 끝에서 수행되고 삭제가 전면이라고 알려진 다른 쪽 끝에서 수행되는 순서 목록입니다. 대기열의 좋은 예는 먼저 온 소비자가 먼저 제공되는 리소스에 대한 소비자 대기열입니다.
스택과 큐의 차이점은 제거에 있습니다. 스택에서 가장 최근에 추가된 항목을 제거합니다. 대기열에서 가장 최근에 추가된 항목을 제거합니다.

추천 연습배열을 이용한 대기열 구현해 보세요!

대기열 데이터 구조

대기열의 기본 작업:

enqueue(): 대기열의 끝, 즉 뒤쪽 끝에 요소를 삽입합니다. dequeue(): 이 작업은 대기열의 프런트 엔드에 있는 요소를 제거하고 반환합니다. front(): 이 작업은 요소를 제거하지 않고 프런트 엔드에 있는 요소를 반환합니다. Rear(): 이 작업은 요소를 제거하지 않고 뒤쪽 끝에 있는 요소를 반환합니다. isEmpty(): 이 작업은 대기열이 비어 있는지 여부를 나타냅니다. isFull(): 이 작업은 대기열이 가득 찼는지 여부를 나타냅니다. size(): 이 작업은 대기열의 크기, 즉 포함된 요소의 총 개수를 반환합니다.

대기열 유형:

순환 대기열 : 순환 대기열에서 대기열의 요소는 순환 링 역할을 합니다. 순환 큐의 작동 방식은 마지막 요소가 첫 번째 요소에 연결된다는 점을 제외하면 선형 큐와 유사합니다. 장점은 메모리를 더 나은 방식으로 활용한다는 것입니다. 이는 빈 공간이 있는 경우, 즉 대기열의 특정 위치에 요소가 없으면 모듈로 용량을 사용하여 해당 위치에 요소를 쉽게 추가할 수 있기 때문입니다( %N ).
우선순위 대기열 : 이 대기열은 특별한 유형의 대기열입니다. 그 특징은 우선 순위에 따라 대기열의 요소를 정렬한다는 것입니다. 우선순위는 가장 높은 값을 가진 요소가 우선순위를 가지므로 값의 순서가 감소하는 대기열을 생성하는 것일 수 있습니다. 우선 순위는 가장 낮은 값을 가진 요소가 가장 높은 우선 순위를 가져서 값의 순서가 증가하는 대기열을 생성하는 것과 같을 수도 있습니다. 미리 정의된 우선순위 큐에서 C++는 가장 높은 값에 우선순위를 부여하는 반면 Java는 가장 낮은 값에 우선순위를 부여합니다.
따라서 : Dequeue는 Double Ended Queue라고도 합니다. 이름에서 알 수 있듯이 더블 엔드형은 한쪽 끝에서만 요소를 삽입하거나 제거할 수 있는 다른 큐와 달리 큐의 양쪽 끝에서 요소를 삽입하거나 제거할 수 있음을 의미합니다. 이 속성으로 인해 First In First Out 속성을 따르지 않을 수 있습니다.

대기열의 응용:

Queue는 즉시 처리할 필요는 없고, 시간 내에 처리해야 하는 경우에 사용됩니다. 에프 첫째 나 N 에프 첫째 영형 너 주문은 좋아 너비 우선 검색 . Queue의 이 속성은 다음과 같은 종류의 시나리오에서도 유용합니다.

여러 소비자가 리소스를 공유하는 경우. 예로는 CPU 스케줄링, 디스크 스케줄링이 있습니다.

대기열의 배열 구현:

대기열을 구현하려면 앞과 뒤의 두 인덱스를 추적해야 합니다. 항목을 뒤쪽에 대기열에 추가하고 앞쪽에서 항목을 대기열에서 제거합니다. 단순히 전면 및 후면 인덱스를 증가시키면 문제가 발생할 수 있으며 전면이 배열의 끝에 도달할 수 있습니다. 이 문제에 대한 해결책은 앞뒤를 원형으로 늘리는 것입니다.

대기열에 추가하는 단계:

대기열이 꽉 찼는지 확인하세요.
가득 차면 오버플로를 인쇄하고 종료합니다.
대기열이 가득 차지 않으면 tail을 증가시키고 요소를 추가합니다.

대기열 제거 단계:

대기열이 비어 있는지 확인하십시오.
비어 있으면 언더플로우를 인쇄하고 종료합니다.
비어 있지 않으면 헤드에 요소를 인쇄하고 헤드를 증가시킵니다.

다음은 대기열에서 위 작업을 구현하는 프로그램입니다.

C++

// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->용량 = 용량;> >queue->전면 = 대기열->크기 = 0;> >// This is important, see the enqueue> >queue->후면 = 용량 - 1;> >queue->배열 =>new> int>[queue->용량];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->크기 == 대기열->용량);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->크기 == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->후면 = (큐->후면 + 1)> >% queue->용량;> >queue->배열[queue->rear] = 항목;> >queue->크기 = 대기열->크기 + 1;> >cout << item <<>

' enqueued to queue
'>

;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->배열[큐->앞];> >queue->앞 = (큐->앞 + 1)> >% queue->용량;> >queue->크기 = 대기열->크기 - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->배열[큐->앞];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->배열[큐->리어];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>

' dequeued from queue
'>

;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra>

씨

// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->용량 = 용량;> >queue->전면 = 대기열->크기 = 0;> >// This is important, see the enqueue> >queue->후면 = 용량 - 1;> >queue->배열 = (>int>*)>malloc>(> >queue->용량 *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->크기 == 대기열->용량);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->크기 == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->후면 = (큐->후면 + 1)> >% queue->용량;> >queue->배열[queue->rear] = 항목;> >queue->크기 = 대기열->크기 + 1;> >printf>(>

'%d enqueued to queue
'>

, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->배열[큐->앞];> >queue->앞 = (큐->앞 + 1)> >% queue->용량;> >queue->크기 = 대기열->크기 - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->배열[큐->앞];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->배열[큐->리어];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>

'%d dequeued from queue

'>

,> >dequeue(queue));> >printf>(>

'Front item is %d
'>

, front(queue));> >printf>(>

'Rear item is %d
'>

, rear(queue));> >return> 0;> }>

자바

// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>

' dequeued from queue
'>

);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani>

파이썬3

# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()>

씨#

// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }>

자바스크립트

> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> >

자바의 스캐너

산출

10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>

복잡성 분석:

시간 복잡도

운영	복잡성
대기열에 넣기(삽입)	오(1)
데크(삭제)	오(1)
앞(앞으로 나가기)	오(1)
후방(후방 확보)	오(1)
IsFull(큐가 꽉 찼는지 확인)	오(1)
IsEmpty(큐가 비어 있는지 확인)	오(1)

어레이 구현의 장점:

구현하기 쉽습니다.
대용량 데이터를 쉽고 효율적으로 관리할 수 있습니다.
선입선출(First In First Out) 원칙을 따르므로 삽입, 삭제 등의 작업을 쉽게 수행할 수 있습니다.

어레이 구현의 단점:

정적 데이터 구조, 고정된 크기.
대기열에 대기열에 넣기와 대기열에서 빼기 작업의 수가 많은 경우 어떤 시점(전면 및 후면 인덱스가 선형으로 증가하는 경우) 대기열이 비어 있어도 대기열에 요소를 삽입하지 못할 수 있습니다(이 문제는 방지됩니다) 순환 큐를 사용하여).
대기열의 최대 크기를 먼저 정의해야 합니다.

TechCodeview

대기열의 도입 및 배열 구현