Karteikarten
Queues
Karten in diesem Stapel (10)
- 1Define: 1. Abstract data type (ADT) 2. Queue1. A data type created by the programmer rather than defined by the actual programming language. It provides a logical description of how the data is to be viewed while abstracting the actual data types used to store it
2. An abstract First In First Out (FIFO) data structure, with a size dependent on the number of items it holds - 2Explain what is meant by First In First Out (FIFO)Elements may only be added to one end and retrieved from the other in the order they were added
- 3Uses of a queueOutput waiting to be printed utilises a queue on a disc to ensure documents are not mixed
Typed characters are stored in a queue until they are processed
Simulations e.g. a simulation of customers at checkouts in a supermarket, arriving at random times and taking random times to process.
Queues are thread-safe - they can be used to pass data from one thread to another during concurrent processing. - 4Name the four operations on a queue and describe their functions1. enQueue(item): Add a new item to the rear of the queue
2. deQueue(): Remove the front item from the queue and return it. Not to be confused with double-ended queue (dqueue) where the queue can go in both directions
3. isEmpty(): Checks whether the queue is empty
4. isFull(): Checks whether the queue is full - 5Describe static and dynamic data structures and state their differencesDynamic: A collection of data in memory with the ability to grow or shrink in size. It makes use of a heap - a portion of memory from which space is automatically allocated or de-allocated where required
Static: A data structure of a fixed size, which cannot increase in size or free up memory - 6Advantages and disadvantages of dynamic data structuresAdvantages:
1. Maximum size does not need to be known in advance
2. Many methods or functions may already be written and can be used to implement more abstract data structures
Disadvantages:
1. The data structure may cause an overflow if it exceeds the maximum memory limit, causing the program to crash - 7Advantages and disadvantages of static data structuresAdvantages:
1. No risk of overflow as it cannot exceed its maximum limit
Disadvantages:
1. Maximum size must be decided in advance - 8Describe two ways of implementing a linear queue1. As items leave the queue from one end, all other items are moved up from main memory. This is easy to implement but will require more processing time for longer queues
2. An array with pointers to the front and rear of the queue. This is more complicated to implement as it also needs an integer with a maximum size of the array and a variable giving the number of items in the queue. Problems will also arise when the front sets of data are free but the rear sets are not. - 9Describe a circular queueSpace is allocated from the front of an array, but pointers move from the front to the rear of the array then circle back around
- 10Briefly describe a priority queue and give an example of why it might be usedItems are dequeued in order of priority - items with the highest priority are dequeued before items with the lowest priority, even if they were enqueued later.
A priority queue might be used if a program has to schedule tasks according to a set of requirements e.g. length of time or difficulty
Informationen
- Beschreibung
- A level OCR A level Computer Science (Topic 7 - Data Structures) Karteikarten am Queues, erstellt von James Norman am 28/05/2019.
- Erstellt von
- James Norman
- Aufrufe
- 1
- Bewertung