Queue

This post was written based on what I've learn in college class and the materials I looked for. Also, it was written to study while reviewing, so there may be insufficient or wrong information. If there's anything to fix, please leave a comment!

A queue is an example of a linear data structure, or more abstractly a sequential collection. Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes.

Definition of Queue

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

A collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
A structure in which elements are added to the rear and removed from the front; a "First in, First out" (FIFO) structure.

Real-life example of queue

One of the real-life example of queue is that getting in the line to order in McDonald's. The person who comes earlier through the door orders first and leave the line. The other people who come next order next and leave the line. In this situation, the door of this store is the entry(rear) of the queue, the line is the queue, and the other end that people leave after order is the exit(front) of the queue.
Simply we usually call it "First come, First serve".

Difference between Stack and Queue

In a stack we remove the element the most recently added. In a queue, we remove the element the least recently added.

Operation on Queue

Constructor

• new: creates an empty queue

  

Transformers

• enqueue: Adds an element to the rear of a queue. If the queue is full, throws the overflow exception. Similar with 'push()' in stack, but the difference is that 'push()' is added to the front of the stack.

  

• dequeue: Removes an element from the front of the queue. The elements are popped in the same order in which they are pushed. If the queue is empty, throws the underflow exception. Similar with the 'pop()' in stack.

  

Observers
They have no effect on the queue.

• front: Get the front element from queue.
  
• rear: get the last item from queue.
  

Full code (Floating Front Queue)

Full code with Fixed Front Queue

Usage of Queue

• Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
• Computer systems must often provide a "holding area" for messages between two processes, two programs, or even two systems. This holding area is usually called a "buffer" and is often implemented as a queue.
• When a resource is shared among multiple consumers. Such as CPU scheduling, disk Scheduling.
• When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes.Such as IO Buffers, pipes, file IO.

Complexity of Queue (Big-O)

enqueue, dequeue, front, and rear are O(1).

Implementation of Queue

Array-based, Linked-based.

Comparing Queue implementations

Storage size

• Array-based: takes the same amount of memory, no matter how many array slots are actually used, proportional to current capacity.
• Link-based: takes space proportional to actual size of the queue. But each element requires more space than array-based.

Operation efficiency

All operations are O(1), except for the constructors

• Array-based: O(N)
• Linked-based: O(1)

https://github.com/namdarine/DataStructure.git
QueueInterface, QueueOverflowException, QueueUnderflowException, Fixed Front Queue, Floating Front Queue, Wrap around with floating front Queue, and Linked list Queue codes are uploaded in this github repository.

---

큐

본 포스팅은 학교에서 배운 수업내용과 더 찾아본 자료를 기반으로 작성하였습니다.
다시 복습하면서 공부하기위해서 작성하였으므로 부족하거나 잘못된 것이 있을 수 있습니다.
수정 사항이 있다면 댓글 달아주세요!

큐는 선형 데이터 구조의 예이고, 더 추상적으로 순차적 컬렉션이다. 큐는 접근 루틴과 결합된 데이터 구조, 추상 데이터 구조 또는 클래스로 객체 지향 언어로 구현되는 컴퓨터 프로그램에서 흔히 볼 수 있다.

큐의 정의

차례를 기다리거나 진행하기 위해 대기 중인 사람이나 차량의 줄 또는 순서.

시퀀스에서 유지되고 시퀀스의 한 끝에 요소를 추가하고 다른 끝에는 요소를 제거하여 수정할 수 있는 요소들의 집합이다.
요소가 뒤에 추가되고 앞에서 제거되는 구조로 "선입선출" 구조이다.

큐의 실제 예시

우리 일상생활에서 흔히 볼 수 있는 큐의 예시로는 물건을 구입하기 위해 서있는 줄이다. 문을 통해서 사람들이 매장으로 들어오고 주문하기 위해서 줄을 선다. 먼저 들어온 손님은 다른 뒤에 있는 사람보다 먼저 주문하고 줄에서 나간다. 그 다음 손님도 마찬가지로 주문을 하고 줄에서 나간다. 순차적으로 주문을 하고 줄에서 나간다. 여기서 '문'은 큐의 입구, 즉 뒤쪽이다. '줄'은 큐 본체이고, 주문하는 쪽은 큐의 출구, 즉 큐의 앞쪽이다.

스택과 큐의 차이점

스택은 가장 최근에 추가된 요소를 제거한다. 반대로 큐는 가장 먼저 추가된 요소를 제거한다.

큐의 작동

생성자

• new: 새로운 빈 큐를 생성한다.

  

트랜스포머

• enqueue: 큐의 뒤쪽에 요소를 추가한다. 만약 큐가 다 찼다면, overflow exception을 던진다. 스택의 'push()'와 비슷하지만 차이점은 'push()'는 스택의 앞쪽으로 추가한다.

  

• dequeue: 큐의 앞쪽에 있는 요소를 제거한다. 요소는 추가된 순서대로 제거된다. 만약 큐가 비어있다면, underflow exception을 던진다. 스택의 'pop()'과 비슷하다.

  

관찰자
큐에 끼치는 영향은 없다.

• front: 큐의 맨앞의 요소를 반환한다.
  
• rear: 큐의 맨 뒤의 요소를 반환한다.
  

전체 코드 (Floating Front Queue)

Fixed Front Queue 전체 코드

큐의 사용

• 운영 체제는 실행 준비가 되었거나 특정 이벤트가 발생하기를 기다리는 프로세스의 대기열을 유지하는 경우 자주 사용된다.
• 컴퓨터 시스템은 종종 두 프로세스, 두 프로그램 또는 심지어 두 시스템 사이의 메시지를 위한 "보류 영역(holding area)"을 제공해야 한다. 이 보류 영역은 보통 "버퍼(buffer)"라고 불리며 종종 큐로 구현된다.
• 리소스가 여러 소비자 간에 공유되는 경우. 예를 들어 CPU 스케줄링, 디스크 스케줄링 등이 있다.
• 데이터가 두 프로세스 간에 비동기적으로 전송될 때 (데이터를 반드시 동일한 속도로 수신할 필요는 없음). 예를 들어 IO 버퍼, 파이프, 파일 IO 등이 있다.

큐의 복잡성 (Big-O)

enqueue, dequeue, front 그리고 rear 연산은 O(1)이다.

큐의 구현

Array-based, Linked-based

큐 구현방법들의 비교

저장공간

• Array-based: 실제로 사용되는 array 슬롯 수에 관계없이 현재 용량에 비례하여 동일한 양의 메모리를 사용한다.
• Linked-based: 큐의 실제 크기에 비례하는 공간을 사용한다. 그러나 각 요소에는 array 기반보다 더 많은 공간이 필요하다.

작업 효율

생성자를 제외한 모든 연산은 O(1)이다

• Array-based: O(N)
• Linked-based: O(1)

Reference

• CS401-Data Structure. (2021). Micheal Y. Choi, Ph.D. Illinois Institute of Technology.
• Wikimedia Foundation. (2021, September 21). Queue (abstract data type). Wikipedia. Retrieved January 22, 2022, from https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
• Queue: Set 1 (introduction and array implementation). GeeksforGeeks. (2021, September 9). Retrieved January 22, 2022, from https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/?ref=lbp

https://github.com/namdarine/DataStructure.git
이 깃허브 레퍼짓토리에 QueueInterface, QueueOverflowException, QueueUnderflowException, Fixed Front Queue, Floating Front Queue, Wrap arround with floating front Queue, and Linked list Queue 코드들이 있습니다.