Section 7 Chapter 37 - Queues

Question 1

Elementary data type

Answer 1

basic, built in data types such as integer

Question 2

Composite data types

Answer 2

Built in a data types that area composed of elementary data types, for instance a list

Question 3

Abstract data type

Answer 3

A data type that is viewed by how the data is viewed and the operations that can be performed on it, without knowing actually how these are done. For instance you may use a queue but not know if it stored as circular or linear queue

Question 4

Queue

Answer 4

A data structure that functions as a first in first out storage of elements. Elements can (in most cases) only be added to the back of the queue and elements are only taken from the front of the queue.

Question 5

Example of uses of queues (3)

Answer 5

• Print queue
• Typed characters
• Simulation of a supermarket

Question 6

Operations on a queue (4)

Answer 6

• Add (enQueue)
• Remove (deQueue)
• Check if empty
• Check if full

Question 7

Static data structure

Answer 7

A data structure that is fixed in size. It cannot have new memory allocated to it and it cannot free up memory that it isn’t using

Question 8

Dynamic data structure

Answer 8

A data structure that has the ability to grow or shrink in size. When it requires new memory it can be allocated some heap memory, which can then be de-allocated when it is not needed

Question 9

Advantages of dynamic data structures (3)

Answer 9

• Can free up unused memory
• Can increase in size if it gets full
• Do not need to specify a size when creating them

Question 10

Disadvantage of dynamic data structures (1)

Answer 10

Can be more complicated to program one

Question 11

Advantage of static data structure (1)

Answer 11

In much the same way that a constant is useful, a static data structure can serve as a reminder to a programmer that its size is not meant to change

Question 12

Disadvantages of static data structures (3)

Answer 12

• Must specify size when created
• Can’t free up memory that it isnt using
• Can’t allocate new memory when it is full

Question 13

Linear Queue

Answer 13

A list of items that are in the same order of that in which they were added. Has functionality to add an element to the back or to dequeue an element from the front

Question 14

The two ways to implement a linear queue

Answer 14

• When an item is dequeued, every other item is moved forward one place
• Pointers are created pointing to the front and back of the queue. These are changed as items are added and removed

Question 15

Circular queue

Answer 15

An implementation of a queue where the elements are stored in a list, with pointers referencing the front and back indexes. When either pointer would be incremented off the end of the list it would instead wrap around through the use of modular arithmetic.

Question 16

Disadvantage of a circular queue

Answer 16

The maximum size must be known in advance

Question 17

Priority queue

Answer 17

A queue where elements are not necessarily added to the back but are instead place in the queue according to their assigned priority. Higher priority elements will be placed towards the front of the queue.

Question 18

How you would add an element to a priority queue

Answer 18

Scan the queue from front to back until you find an element with a lower priority than that of the element being added. Insert the element being added in front of the found element