Question | Answer |
What is a Queue? | > First in, first out (FIFO) data structure > Contains multiple elements, similar to a one-dimensional array > New elements can only be added to the end > Elements can only be retrieved from the front > Sequence of elements is determined by the order in which they are inserted |
What are some Examples of Queues being Used? | > Multiple documents to be printed on one printer, e.g., in a room of networked computers > Characters typed on a keyboard are held in a queue in a keyboard buffer > Simulation problems, e.g., simulating traffic data |
What Operations can be Performed on a Queue? | > enQueue(item) - Adds a new item to the rear > deQueue() - Removes the front item and returns it > isEmpty() - Returns true if the queue is empty, false if not > isFull() - Returns true if the queue is full, false if not |
How can a Linear Queue be Implemented with Static Data Structures? | One of two ways: 1. When items leave the queue, all other items are moved up one position in the allocated memory, however this could require significant processing time 2. A front and rear pointer are created, which change depending on items entering and exiting the queue, however, as items exit, there is empty space at the front which cannot be filled, so there becomes less and less space: the elements themselves do NOT move |
How can a Circular Queue be Implemented with Static Data Structures? | > A front and rear pointer are created, which change depending on items entering and exiting the queue > Unlike a linear queue, the pointers "wrap" around > Meaning an element that wouldn't fit in the array will go to the beginning (assuming it isn't full) > This requires extra effort to program, and is less flexible than a dynamic data structure (Pseudocode can be found in textbook) |
What is a Priority Queue? | > Acts like a queue, in terms that items are dequeued by removing them from the front > The order of the items in the queue is determined by a priority, not the order they entered / exited > Highest priority items are at the front of the queue, lowest are at the back > Possible that a new item joins at the front, rather than the rear |
Want to create your own Flashcards for free with GoConqr? Learn more.