Queues

The name "queue" likely comes from the everyday use of the term.
Consider: queue of people waiting at a bus stop, as pictured in fig. below.
Each new person who comes and takes his or her place at the end of the line, and when
the bus comes, the people at the front of the line board first
Clearly, the first person in the line is the first person to leave.
Thus queues are also called first-in first-out (FIFO) lists.

Another example of a queue is a batch of jobs waiting to be processed, assuming no job

has higher priority than the others.

Outline

Definition of Queue
Queue Operations
o Insertion (Enqueue)
o Removing (Dequeue)
Variety of queue.
Applications of the Queues
1. DEFINITION OF QUEUE

 A Queue is an ordered collection of items from which items may be deleted at one end (called the
front of the queue) and into which items may be inserted at the other end (the rear of the queue).

The terms "front" and "rear” are used in describing a linear list only when it is implemented as, a queue.

 The first element inserted into the queue is the first element to be removed. For this reason a
queue is sometimes called a fifo (first-in first-out) list as opposed to(contrasts with) the stack, which is
a lifo (last-in first-out).
2. QUEUE OPERATIONS
Initialize the queue
Insert to the rear of the queue (also called as Enqueue)
Remove (Delete) from the front of the queue (also called as Dequeue)
Is the Queue Empty
Is the Queue Full
2.1 INITIALIZE THE QUEUE (USING LINEAR ARRAY)
The queue is initialized by having the rear set to -1, and front set to -1.
Let us assume that maximum number of the element we have in a queue is 3 elements as
shown below.

2.2 INSERT / REMOVE ITEMS

an item (A) is inserted at the Rear of the queue. A new item (B) is inserted at the Rear of the queue

an item(A) is removed from the front of the queue. A new item (C) is inserted at the Rear of the queue
 an item(B) is removed from the front of the queue. an item(C) is removed from the front of the queue.

Is the Queue Empty front==rear

Is the Queue Full rear==maxSize-1

3. Implementation of Queue

3.1 Linear Queue

Queues may be represented in the computer in various ways, usually by means of one-way lists or linear
arrays.

Using linear arrays

Each of our queues will be maintained by a linear array Q and two pointer variables:
front, containing the location of the front element of the queue; and
rear, containing the location of the rear element of the queue.

class QueueX
{
private:
int maxSize; //size of stack vector
vector<double> queueVect; //stack vector
int front;
int rear;
}

Status representation
• Initial Status : front = rear = -1
• Empty Status: front = rear
• Full Status : rear = maxSize-1

 Initialize Queue
 //--------------------------------------------------------------
QueueX(int s) : maxSize(s), front(-1), rear(-1) //constructor
{
queueVect.resize(maxSize); //size the vector

} //--------------------------------------------------------------

Algorithm for checking whether empty or full

bool isEmpty() //true if queue is empty

{
return (front == rear);
}

bool isFull() //true if queue is full

{
return (rear == maxSize-1);
}

Insert algorithm
• 마지막 원소의 뒤에 삽입해야 하므로
② 마지막 원소의 인덱스를 저장한 rearear의 값을 하나 증가시켜 삽입할 자리 준비
② 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장

void enQueue(double x)
{
if(isFull())
{
printf("Queue is full!");
exit(1);
}
else
{
rear++;
queueVect[rear]=x;
}
}

Removing algorithm

• 가장 앞에 있는 원소를 삭제해야 하므로

① fronf의 위치를 한자리 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비
② 그 자리의 원소를 삭제하여 반환
 double deQueue()
{
double p;
if(isEmpty())
{
printf("Queue is empty");
exit(1);
}
else
{
front++;
p=queueVect[front];

return p;
}
}

Search algorithm

• 가장 앞에 있는 원소를 검색하여 반환하는 연산

① 현재 fronf의 한자리 뒤(front+1)에 있는 원소, 즉 큐에 있는 첫 번째 원소를 반환

double peek()
{
double p;
if(isEmpty())
{
printf("Queue is empty");
exit(1);
}
else
return queueVect[front+1];

Printing algorithm

void printQ() // 큐의내용을출력하는연산

{
int i;
cout << " Queue : [";
for(i=front+1; i<=rear; i++)
cout << queueVect[i];
cout << " ] ";
}
 Assume that the rear= MAXQUEUE-1

 What happens if we want to insert a new item F into the queue?

 Although there is some empty space, the queue is full.

 One of the methods to overcome this problem is to shift all the items to occupy the location of deleted item.

 Since all the items in the queue are required to shift when an item is deleted, this method is not preferred.

 The other method is circular queue.

3.2 Circular Queue

 When rear = MAXQUEUE-1, the next element is entered at items[0] in case that spot is free.

• 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고가정하고 사용 ⇒ 원형큐

원형 큐의 논리적 구조

§ 원형 큐의 구조
• 초기 공백 상태 : front = rear = 0
• front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해서 나머지연산자 mod를 사용
− 3 ÷ 4 = 0 …3 (몫=0, 나머지=3)
− 3 mod 4 = 3

사용조건) 공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.

원형 큐에서의 연산 과정

§ 초기 공백 원형 큐 생성 알고리즘
• 크기가 n인 1차원 배열 생성
• front와 rear를 0 으로 초기화
 //--------------------------------------------------------------
CQueueX(int s) : maxSize(s), front(0), rear(0) //constructor
{
queueVect.resize(maxSize); //size the vector

} //--------------------------------------------------------------

원형 큐의 공백상태 검사 알고리즘과 포화상태 검사 알고리즘

• 공백 상태 : front = rear
• 포화 상태 : 삽입할 rear의 다음 위치 = front의 현재 위치
− (rear+1) mod n = front

bool isEmpty() //true if stack is empty

{
return (front == rear);
} //--------------------------------------------------------------

bool isFull() //true if stack is full

{
return ((rear+1)% maxSize == front);
} //--------------------------------------------------------------

원형 큐의 삽입 알고리즘
② rear의 값을 조정하여 삽입할 자리를 준비 : rear ← (rear+1) mod n;
③ 준비한 자리 cQ[rear]에 원소 item을 삽입
 void enQueue(double x)
{
if(isFull())
{
printf("Queue overflow\n");
exit(1);
}
else
{
rear=(rear+1) % maxSize;
queueVect [rear]=x;
}
}

원형 큐의 삭제 알고리즘
① front의 값을 조정하여 삭제할 자리를 준비
③ 준비한 자리에 있는 원소 cQ[front]를 삭제하여 반환

double deQueue()
{
if(isEmpty()){
printf("Queue underflow");
exit(1);
}
else
{
front = (front +1) % maxSize;
return queueVect[front];
}

}
void deleteQ()
{
if(isEmpty())
 {
printf("Queue underflow");
exit(1);
}
else
front = (front +1) % maxSize;
}

 Assume that we have a queue of real numbers. Write a function, QueueSearch to search a
given key element in the queue until the search key is found. Once the search key is found,
the function returns its position in the queue, otherwise returns -1 to indicate that the
searched key is not in the queue.

The following function can be written:

int QueueSearch(double searchkey)
{
int pos = -1,f;
f=front;
while(front != rear)
{
front = (front+1) % maxSize;
if(queueVect[front] == searchkey)
{
pos = front;
front = f;
return pos;
}
}
front=f;
return pos;
}

4. Deque(double-ended queue)
A deque (pronounced either "deck" or "dequeue") is a linear list in which elements can be added or removed at either end but not
in the middle. The term deque is a contraction of the name double-ended queue.
 There are various ways of representing a deque in a computer.

ADT deque
데이터 : 0개 이상의 원소를 가진 유한 순서 리스트
연산 :
DQ∈deque; item∈Element;
createDeque() ∷= create an empty DQ;
// 공백 덱을 생성하는 연산

isEmpty(DQ) ∷= if (DQ is empty) then return true

else return false;
// 덱이 공백인지 아닌지를 확인하는 연산
insertFront(DQ, item) ∷= insert item at the front of DQ;
// 덱의 front 앞에 item(원소)을 삽입하는 연산

insertRear(DQ, item) ∷= insert item at the rear of DQ;

// 덱의 rear 뒤에 item(원소)을 삽입하는 연산

deleteFront(DQ) ∷= if (isEmpty(DQ)) then return null

else { delete and return the front item of DQ };
// 덱의 front에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산

deleteRear(DQ) ∷= if (isEmpty(DQ)) then return null

else { delete and return the rear item of DQ };
// 덱의 rear에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산

removeFront(DQ) ∷= if (isEmpty(DQ)) then return null

else { remove the front item of DQ };
// 덱의 front에 있는 item(원소)을 삭제하는 연산

removeRear(DQ) ∷= if (isEmpty(DQ)) then return null

else { remove the rear item of DQ };
// 덱의 rear에 있는 item(원소)을 삭제하는 연산

getFront(DQ) ∷= if (isEmpty(DQ)) then return null

else { return the front item of the DQ };
// 덱의 front에 있는 item(원소)을 반환하는 연산

getRear(DQ) ∷= if (isEmpty(DQ)) then return null

else { return the rear item of the DQ };
// 덱의 rear에 있는 item(원소)을 반환하는 연산

End deque
5. PRIORITY QUEUES

A priority queue is an abstract data type for storing a collection of prioritized elements that supports arbitrary
element insertion but supports removal of elements in order of priority, that is, the element with first priority can be
removed at any time.

This special
type of queue allows the item in a queue with the highest priority to be removed from
the queue first.

Priority queues can be used to study the operations of a hospital emergency room, where
patients with heart trouble need to be attended to before a patient with a broken arm, for
example.

In a post office example, a handicapped person may have priority over others. Therefore, when
a clerk is available, a handicapped person is served instead of someone from the front of the
queue.

On roads with tollbooths, some vehicles may be put through immediately, even without
paying(police cars, ambulances, fire engines, etc).

 An ascending priority queue is a collection of items into which items can be inserted arbitrarily and from which only
the smallest item can be removed.

 On the other hand a descending priority queue allows only the largest item to be removed.

Priority QUEUE Operations

 Priority Queue Declaration

The data type of Priority Queue is the same as the Non-priority Queue.

 Insertion
The insertion in Priority queues is the same as in non-priority queues.

 Deletion
Deletion requires a search for the element of highest priority and deletes the element with highest priority.
The following methods can be used for deletion/removal from a given Priority Queue:

REMOVE OPERATION
 PriQremove Operation using removing the element with highest priority and shifting the elements up in the array and
decrementing rear. Consider Ascending Priority Queue.

int PriQremove()
{
int smallest, loc, f, i;
f= front;
if(isEmpty())
{
 printf("Queue underflow");
exit(1);
}

smallest = queueVect[(front+1)%maxSize];
loc = (front+1)%maxSize;

//(front++)%maxSize; /* Circular increment*/

while(front != rear)
{
if(queueVect[(front+1)%maxSize] <smallest)
{
smallest = queueVect[(front+1)%maxSize];
loc = (front+1)%maxSize;
}
front =(front+1)%maxSize; /* Circular inc.*/
}

while(loc != rear)
{
queueVect[loc] = queueVect[(loc+1)%maxSize];
(loc++)%maxSize;
}
front=f;
if(rear == 0) /*Decrement rear after removing one item*/
rear = maxSize -1;
else
rear--;

return smallest;
}

6. 큐의 응용
v 운영체제의 작업 큐
§ 프린터 버퍼 큐
• CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하기
위해서 선입선출 구조의 큐 사용
§ 스케줄링 큐
• CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해서 큐를 사용

John peter muthurimi