Chapter 34 - Queues

Question 1

How is an abstract data type created?

Answer 1

» Data type that is created by the programmer, rather than defined within the programming language

Question 2

What are some examples of structures contained in abstract data types?

Answer 2

» Queues
» Stacks
» Trees
» Graphs

Question 3

What is an abstract data type?

Answer 3

» Logical description of how the data is viewed and the operations that can be performed on it

Question 4

What is one good example of data abstraction?

Answer 4

» 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

Question 5

What is a queue?

Answer 5

» A first in First out (FIFO) data structure

Question 6

Where are elements added in a queue?

Answer 6

» At the end of a queue

Question 7

Where are elements retrieved from?

Answer 7

» From the front of a queue

Question 8

What does the sequence of data items in a queue is determined by?

Answer 8

» By the order they are inserted in

Question 9

What is an example of how a queue is in real life?

Answer 9

» 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

Question 10

What is a queue described as?

Answer 10

» An ordered collection of items which are added at the rear of the queue, and remove front the front

Question 11

What happens if the first person in the queue leaves?

Answer 11

» 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

Question 12

What does enQueue(item) do?

Answer 12

» Add a new item to the rear of the queue

Question 13

What does deQueue do?

Answer 13

» Remove the front item from the queue and return it

Question 14

What does isEmpty() do?

Answer 14

» Test to see whether the queue is empty

Question 15

What does isFull() do?

Answer 15

» Test to see whether queue is full

Question 16

What is a front pointer also known as?

Answer 16

» Header pointer

Question 17

What is a queue overflow?

Answer 17

» Where items are enqueued, added to the back in a full queue

Question 18

What is a queue underflow?

Answer 18

» While trying to dequeue an item from an empty queue

Question 19

What is a queue an example of?

Answer 19

» Linear data structure

Question 20

What are the 2 ways an abstract data type can be implemented?

Answer 20

» Using either a dynamic or static data structure

Question 21

What is a dynamic data structure?

Answer 21

» 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

Question 22

What is the heap?

Answer 22

» A portion of memory from which space is automatically allocated or de-allocated as required

Question 23

What is a disadvantage of a dynamic data structure?

Answer 23

» The data structure may cause overflow if it exceeds the maximum memory limit, and the program will crash

Question 24

What are the benefits of inbuilt dynamic data structures?

Answer 24

» Many methods such as append are already written in

Question 25

How can queues be implemented as a dynamic data structure?

Answer 25

» Maximum size of data structure is not known in advance
» Queue can be given some arbitrary maximum to avoid causing memory overflow

Question 26

What is a static data structure?

Answer 26

» such as an array is fixed in size, and cannot increase in size or free up memory while the program is running

Question 27

What is an array suitable for?

Answer 27

» Storing fixed number of items

Question 28

What are the disadvantages of using an array to implement a queue?

Answer 28

» Size of array has to be decided by the programmer in advance

Question 29

What is the 1st way to implement a linear queue in an array or a list?

Answer 29

» As items leave the queue, all items move up one position in allocated memory

Question 30

What is the 2nd way to implement a linear queue?

Answer 30

» 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

Question 31

What is the problem caused by implementing a queue as an array?

Answer 31

» 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

Question 32

What is one way of overcoming the limitation of a static data structure such as an array?

Answer 32

» To implement the queue as a circular queue

Question 33

What happens in a circular queue?

Answer 33

» 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

Question 34

What is a priority queue?

Answer 34

» Is like a queue in that items are dequeued by removing them from the front of the queue

Question 35

What are queues used for?

Answer 35

» Process scheduling
» Transferring data between processors and printer spooling
» Performing breadth-first searches on graph data structures

Question 36

What is peeking?

Answer 36

» Returning the value from the front of the queue without removing it

Question 37

What is the difference between a Queue and a Stack?

Answer 37

» Queue has 2 pointers whereas a Stack has one poitner

Question 38

What are 3 main operations you need to know for a queue?

Answer 38

» 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

Question 39

What are the steps to add an item to a queue?

Answer 39

» 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

Question 40

What are the 2 pointers in a Queue?

Answer 40

» Header pointer
» Back/tail pointer