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
마지막원소의뒤에삽입해야하므로 2 마지막원소의인덱스를저장한 rearear의값을하나증가시켜삽입할자리준비 2 그인덱스에해당하는배열원소 Q[rear] 에 item을저장 void enqueue(double x) if(isfull()) printf("queue is full!"); exit(1); else rear++; queuevect[rear]=x; Removing algorithm 가장앞에있는원소를삭제해야하므로 1 fronf의위치를한자리뒤로이동하여큐에남아있는첫번째원소의위치로이동하여삭제할자리준비 2 그자리의원소를삭제하여반환
double dequeue() double p; if(isempty()) printf("queue is empty"); exit(1); else front++; p=queuevect[front]; return p; Search algorithm 가장앞에있는원소를검색하여반환하는연산 1 현재 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); //-------------------------------------------------------------- 원형큐의삽입알고리즘 2 rear의값을조정하여삽입할자리를준비 : rear (rear+1) mod n; 3 준비한자리 cq[rear] 에원소 item을삽입
void enqueue(double x) if(isfull()) printf("queue overflow\n"); exit(1); else rear=(rear+1) % maxsize; queuevect [rear]=x; 원형큐의삭제알고리즘 1 front의값을조정하여삭제할자리를준비 3 준비한자리에있는원소 cq[front] 를삭제하여반환 double dequeue() if(isempty()) printf("queue underflow"); exit(1); else front = (front +1) % maxsize; return queuevect[front]; void deleteq() if(isempty())
else printf("queue underflow"); exit(1); 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 Deletion REMOVE OPERATION The insertion in Priority queues is the same as in non-priority queues. 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: 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