S7 - 34 Queues Flashcards
what is an abstract data type?
one that’s created by the programmer, rather than defined within the programming language
what do abstract data types include?
abstract data types include queues, stacks, trees and graphs
what data structure is a queue?
A queue is a first in first out data structure (FIFO)
where are new elements added?
New elements are added at the end of the queue
where are elements retrieved?
elements are retrieved from the front of the queue
the size of the queue depends on…
the number of items in it (like a supermarket queue)
how is the sequence of data items in a queue determined?
the sequence of data items in a queue is determined by the order in which they are inserted
state the uses of a queue
+ characters typed on a keyboard are in a queue in a keyboard buffer
+ output waiting to be printed is commonly stored in a queue on a disk (first come first serve)
what are the operations that can be performed on a queue?
+ enQueue(me) # adds the string me to the queue
+ deQueue() # removes the item at the front of the queue
+ isEmpty() # test to see wether queue is empty
+ isFull() # test to see wether queue is full
what happens when an item is added or removed from a queue?
When an item is removed the front pointer moves to the next item closest to the front.
When an item is added, the rear pointer moves to the next item closest to the rear.
define dynamic data structure
A dynamic data structure refers to a collection of data in memory that has the ability to grow or shrink
what is the heap?
The heap is a portion of memory from which space is automatically allocated or de-allocated as required
why is a dynamic data structure useful?
Dynamic data structures are useful for implementing data structures (such as queues) when the maximum size of the data structure is not known in advance
how can memory overflow be avoided in a queue?
The queue can be given some arbitrary maximum to avoid causing memory overflow
