Chapter 34 - Queues Flashcards by Anonymous T

How is an abstract data type created?

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

How well did you know this?

Not at all

Perfectly

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

» Queues
» Stacks
» Trees
» Graphs

How well did you know this?

Not at all

Perfectly

What is an abstract data type?

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

What is a queue?

» A first in First out (FIFO) data structure

How well did you know this?

Not at all

Perfectly

Where are elements added in a queue?

» At the end of a queue

How well did you know this?

Not at all

Perfectly

Where are elements retrieved from?

» From the front of a queue

How well did you know this?

Not at all

Perfectly

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

» By the order they are inserted in

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

What does enQueue(item) do?

» Add a new item to the rear of the queue

How well did you know this?

Not at all

Perfectly

What does deQueue do?

» Remove the front item from the queue and return it

How well did you know this?

Not at all

Perfectly

What does isEmpty() do?

» Test to see whether the queue is empty

How well did you know this?

Not at all

Perfectly

What does isFull() do?

» Test to see whether queue is full

How well did you know this?

Not at all

Perfectly

What is a front pointer also known as?

» Header pointer

How well did you know this?

Not at all

Perfectly

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