4.2 - Queues Flashcards
What are data structures?
Data structures are containers within which data used by the computers is stored.
What are arrays?
Arrays are an indexed set of related elements.
Arrays must be FINITE, INDEXED and only contain elements with the same data type.
ArrayName = {“George”,”Sue”,”Mo”}
What are Fields, records and files?
Information is stored by computers as a series of FILES.
Each File is made up of RECORDS, a which are composed of a number of FIELDS.
What are abstract data structures?
Abstract data structures are data structures that do not exist in their own right.
Instead, they make use of other pre existing data structures such as arrays to form a new way of storing data.
What are Queues and how do they work?
A queue is an abstract data structure that utilises arrays.
In a queue, the first item added into the array will be the first to be removed (think like a queue at a shopping line). Because of this, queues are referred to as “FIRST IN, FIRST OUT” (FIFO) abstract data structures.
They are used by computers in keyboard buffers, where each key press is added to the queue and then removed when the computer has processed the key press. This ensures that letters appear on the screen in the same order that they were typed.
Functions of a Queue: Enqueue(), Dequeue(), IsEmpty(), IsFull()
How does a Linear Queue work logically?
A linear queue has TWO POINTERS: a FRONT pointer and a REAR pointer.
These are used to identify where to place a new item in a queue or to identify which item is at the front of the queue.
The rear pointer always points to the next available position in the queue.
If the front and rear pointer values are the same, the queue is empty. If there are no available positions behind the front pointer, the queue is full.
How does a Circular Queue work logically?
Circular queues are a type of queue in which the front and rear pointers can move over the two ends of the queue. This is a more memory efficient data structure than Linear Queues.
If the Rear Pointer is at the end of the queue (there are no more free spaces), the pointer will return to the left hand side of the queue. This would not be possible in a linear queue as there would have been no available spaces behind the front pointer.
How does a Priority Queue work logically?
In a priority queue, items are assigned a priority. Items with the highest priority are dequeued before lower priority items.
In the case that items may have the same priority, the items are removed in the usual First In, First Out order.
