Queues Flashcards Preview

Paper 1 - Computer Science > Queues > Flashcards

Flashcards in Queues Deck (19)
Loading flashcards...

What type of data structure is a queue?

It's a FIFO data structure
(First in First out)


What are some real life examples of a queue being used?

- Characters typed into a keyboard are held in a queue in a keyboard buffer
- Output waiting to be printed is stored in a queue on disk. The output is then printed on a first served basis when the printer is free.


How many pointers does a queue data structure have?

It has 2 pointers, the front and the rear


What happens in the queue data structure when items are added/removed?

The front pointer moves. None of the elements move.


What are the 4 operations that can be carried out on a queue?

- enQueue(item)
- deQueue()
- IsEmpty()
- isFull()


What does the enQueue(item) operation do?

Adds a new item to the rear of the queue


What does the deQueue() operation do?

Removes the first item from the front of the queue and returns it


What does the isEmpty() operation do?

Tests to see whether the queue is empty


What does the isFull() operation do?

Tests to see whether the queue is full


What is the heap?

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


What is a static data structure?

Where the size of the data structure is fixed once it is defined. For example an array


What is a dynamic data structure?

Where the size of the data structure can grow or shrink


Why are dynamic data structures useful?

They are useful for implementing data structures (queues) where the size of the data structure is not known in advance


What is an advantage of using a static data structure?

No pointers or excess information about the data structure needs to be stored


What is a disadvantage of using a static data structure?

Memory that has been allocated to the data structure cannot be reallocated even if most of it is unused


What is one way to implement a linear queue in an array or list.

As items are removed, all the other items move up one space so the front of the queue is always the first element of the data structure


How does a circular queue solve the limitations of a implementing a linear queue?

When the array fills up and the rear pointer points to the last element in the array (assuming it is empty) the rear pointer will be made to point to the first element in the array when another item is enqueued.


How does a priority queue act?

It continues to act as a FIFO data structure, however items with a high priority can be added to the front of the queue instead of the rear.


How could a priority queue be implemented?

- By checking the priority of each item in the queue
- starting at the front and moving along one item until an item with the same/lower priority if found
- At which point the item can be inserted