데이터 구조: 대기열

그 기분 아시죠, 좋은 식당에 갔는데 의외로 사람이 별로 없어요.

맛있는 음식을 먹기 위해 줄을 설 필요 없이 행복할 것입니다.

프로그래밍에도 비슷한 것이 있습니다.

대기열이라고 합니다.

대기열이란 무엇입니까?

Let's forget about programming for a second, and let us define the word queue:

A line or sequence of people or vehicles awaiting their turn to be attended to or to proceed.

At its core, a queue is simply a sequence of items waiting to be processed.

Examples include:

Customers in a pizzeria, waiting for their pizza.
Line in a movie theater, waiting for the security guys to verify their ticket.
Vehicles in a gas station, waiting till the person in front of them finishes filling his gas tank.

You get it, there are lots of these examples out there, but coming back to software.

A queue is a linear data structure that follows a particular order in which the operations are performed.

Queues follow the First-In-First-Out methodology, meaning that the first item to be inserted into the queue will be the first item popped out from it. First come, first served.

대기열의 실생활 예

이것은 스택 데이터 구조와 유사하지 않습니까?

예, 비슷하지만 스택과 대기열의 유일한 주요 차이점은 데이터를 처리하는 방법입니다. 스택은 후입선출 방식을 사용하고 대기열은 선입선출 방식을 사용합니다.

스택과 큐의 차이점

어디에 사용됩니까?

The queue is used mostly when you have:

Items that don't have to be processed immediately.
Items that have to be processed in the First-In-First-Out order.
A single resource wanting to be used by many processes.

Let us go over some applications of the queue.

Message Queues — A message queue is a general concept in computer science used for communication between processes. A sender sends a message and if the receiver cannot receive it, due to it being busy with some other process or offline. The message gets sent to a queue, where it waits until the receiver is ready to receive the message. The message is removed from the queue and sent to the receiver.

For example, when you send an email, it waits in a queue called the SMTP queue, until the receiver logs into their inbox. Same concept is applied when you send a message to someone who is not online on a social network. Your message waits in some kind of a queue on a server, and when the recipient comes online, it is sent to them.
Process Scheduling — All the processes running on your computer now, first wait in a queue called ready queue, waiting to be executed by your processor. There are various scheduling algorithms that decide which process should be executed next based on certain criteria like priority.
Data Buffers — A buffer implements a queue and is typically used in communication when there is a difference between the rate at which data is received and the rate at which it can be processed.

For example in video streaming applications, the video is streamed in bursts and stored in a buffer so that even if the network becomes slow for a while, the playback is not interrupted. Say for example the video is playing at 24fps, then the streaming app may store 240 frames in its buffer so that it can continue playing for the next 10 seconds even if the network is interrupted. The buffer is also used for sequencing frames, ie, if frames come out of order, they are sorted in the buffer before being played. Buffers are also used in disk drives, input/output devices, and communication over networks.
Algorithms — A queue is also used in several algorithms such as the Breadth-First Search algorithm, and round-robin algorithm.

대기열의 유형은 무엇입니까?

Yes, you heard right, there are multiple types of queues:

Simple Queue
Circular Queue
Priority Queue
Dequeue (Double Ended Queue)

단순 대기열

삽입이 앞쪽에서 발생하고 삭제가 뒤쪽에서 발생하는 평균 대기열입니다.

순환 대기열

링 버퍼라고도 하며 기본적으로는 단순한 대기열이지만 후면이 전면에 연결되어 있습니다.

우선순위 대기열

우선 순위 대기열은 각 요소가 우선 순위와 연결되고 해당 우선 순위에 따라 제공되는 특수한 유형의 대기열입니다. 우선 순위가 같은 요소가 있으면 대기열의 순서에 따라 제공됩니다.

큐 제거(이중 큐)

기본적으로 삽입과 삭제가 전면과 후면 모두에서 발생할 수 있는 큐입니다.

어떻게 구현됩니까?

Queues can be implemented in different ways, which includes:

An array with front at index 0.
An array with floating front and rear (wrap-around array).
A singly linked list with front.
A singly linked list with front and rear.
A doubly linked list.

As you can probably tell, queues can be implemented in many ways, but they all should include the common methods that all queues have:

Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it

Let us go over some common implementations of the queue.

PS. We are gonna implement a simple queue.

자바

class Queue
{
    private int[] arr;      // array to store queue elements
    private int front;      // front points to the front element in the queue
    private int rear;       // rear points to the last element in the queue
    private int capacity;   // maximum capacity of the queue
    private int count;      // current size of the queue

    // Constructor to initialize a queue
    Queue(int size)
    {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    }

    // Utility function to dequeue the front element
    public void dequeue()
    {
        // check for queue underflow
        if (isEmpty())
        {
            System.out.println("Underflow\nProgram Terminated");
            System.exit(1);
        }

        System.out.println("Removing " + arr[front]);

        front = (front + 1) % capacity;
        count--;
    }

    // Utility function to add an item to the queue
    public void enqueue(int item)
    {
        // check for queue overflow
        if (isFull())
        {
            System.out.println("Overflow\nProgram Terminated");
            System.exit(1);
        }

        System.out.println("Inserting " + item);

        rear = (rear + 1) % capacity;
        arr[rear] = item;
        count++;
    }

    // Utility function to return the front element of the queue
    public int peek()
    {
        if (isEmpty())
        {
            System.out.println("Underflow\nProgram Terminated");
            System.exit(1);
        }
        return arr[front];
    }

    // Utility function to return the size of the queue
    public int size() {
        return count;
    }

    // Utility function to check if the queue is empty or not
    public Boolean isEmpty() {
        return (size() == 0);
    }

    // Utility function to check if the queue is full or not
    public Boolean isFull() {
        return (size() == capacity);
    }
}

파이썬

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

자바스크립트

class Queue {

  constructor(){

     this.data = [];
     this.rear = 0;
     this.size = 10;
   }

  enqueue(element) {
    if(this.rear < this.size ) {
          this.data[this.rear] = element;
          this.rear = this.rear + 1;
     }
  }

  size() {
     return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  peek() {
    if(this.isEmpty() === false) {
        return this.data[0];
    }
  }

  dequeue() {
     if(this.isEmpty() === false) {
          this.rear = this.rear-1;
          return this.data.shift();
     }
  }

}

얼마나 효율적입니까?

Glad you asked my friend, let's go over the time and space complexity of the queue.

Access - to access an item in a queue, in the worst case we should traverse the whole queue, making it a linear time or O(n) complexity.
Search - similar to access, we also have to traverse through each item in the queue, making it too linear time or O(n) complexity.
Insertion (Enqueue) - because insert happens in one place, this makes it constant time or O(1) complexity.
Deletion (Dequeue) - similar to insertion, it is also constant time or O(1) complexity.