Chapter 34 - Queues Flashcards
How is an abstract data type created?
» Data type that is created by the programmer, rather than defined within the programming language
What are some examples of structures contained in abstract data types?
» Queues
» Stacks
» Trees
» Graphs
What is an abstract data type?
» Logical description of how the data is viewed and the operations that can be performed on it
What is one good example of data abstraction?
» Where its up to the programmer to decide how to construct the data structure
» This encapsulates around the data, hiding the details of implementation from the user
What is a queue?
» A first in First out (FIFO) data structure
Where are elements added in a queue?
» At the end of a queue
Where are elements retrieved from?
» From the front of a queue
What does the sequence of data items in a queue is determined by?
» By the order they are inserted in
What is an example of how a queue is in real life?
» Imagine people printing out work to be printed at more or less the same time
» By putting the output into a queue on disk, the output is printed on a first come first served basis
What is a queue described as?
» An ordered collection of items which are added at the rear of the queue, and remove front the front
What happens if the first person in the queue leaves?
» The front pointer is made to the next point, the elements do not move, when a new person joins the queue, the rear pointer moves to the last item
» Think of a queue, in a doctor’s surgery, people leave and join the queue, but no one moves chairs
What does enQueue(item) do?
» Add a new item to the rear of the queue
What does deQueue do?
» Remove the front item from the queue and return it
What does isEmpty() do?
» Test to see whether the queue is empty
What does isFull() do?
» Test to see whether queue is full
What is a front pointer also known as?
» Header pointer
What is a queue overflow?
» Where items are enqueued, added to the back in a full queue
What is a queue underflow?
» While trying to dequeue an item from an empty queue
What is a queue an example of?
» Linear data structure
What are the 2 ways an abstract data type can be implemented?
» Using either a dynamic or static data structure
What is a dynamic data structure?
» Refers to a collection of data in memory, that has the ability to grow or shrink in size
» Does with the aid of the heap
What is the heap?
» A portion of memory from which space is automatically allocated or de-allocated as required
What is a disadvantage of a dynamic data structure?
» The data structure may cause overflow if it exceeds the maximum memory limit, and the program will crash
What are the benefits of inbuilt dynamic data structures?
» Many methods such as append are already written in
How can queues be implemented as a dynamic data structure?
» Maximum size of data structure is not known in advance
» Queue can be given some arbitrary maximum to avoid causing memory overflow
What is a static data structure?
» such as an array is fixed in size, and cannot increase in size or free up memory while the program is running
What is an array suitable for?
» Storing fixed number of items
What are the disadvantages of using an array to implement a queue?
» Size of array has to be decided by the programmer in advance
What is the 1st way to implement a linear queue in an array or a list?
» As items leave the queue, all items move up one position in allocated memory
What is the 2nd way to implement a linear queue?
» Can be implemented as an array with pointers to the front and rear of the queue
» Integer holding the size of the array is needed
» As well a variable giving the number of items in the array is needed
What is the problem caused by implementing a queue as an array?
» Both back and front pointers are moving in the same direction as items are added and removed from the queue, the array will quickly run out of space
What is one way of overcoming the limitation of a static data structure such as an array?
» To implement the queue as a circular queue
What happens in a circular queue?
» The last element say q[5] will be made to point q[o] when the next person joins the queue, assuming the element is empty
What is a priority queue?
» Is like a queue in that items are dequeued by removing them from the front of the queue
What are queues used for?
» Process scheduling
» Transferring data between processors and printer spooling
» Performing breadth-first searches on graph data structures
What is peeking?
» Returning the value from the front of the queue without removing it
What is the difference between a Queue and a Stack?
» Queue has 2 pointers whereas a Stack has one poitner
What are 3 main operations you need to know for a queue?
» Enqueue - Adding an item to the back of the queue
» Dequeue - Removing an item from the front of the queue
» Peek - Returning the value from the front of the queue without removing it
What are the steps to add an item to a queue?
» Check for queue overflow. Output an error if the queue is full
» Increment the back/tail pointer
» Insert the new item data at the location pointed by the back pointer
What are the 2 pointers in a Queue?
» Header pointer
» Back/tail pointer
