Queue Flashcards
A queue is structured in a…
FIFO(First in first out)
What does the dequeue method do?
Removes data from the front of the queue
What does the enqueue method do?
Adds a data item to the rear end of the queue
What does first() operation do?
Returns the data item at the front of the queue without removing it
What does the isEmpty method do?
Determines weather the queue is empty
What does the size method do?
Returns a string representation of the queue
What does the toString method do?
It returns a string representation of the queue
What 3 things is needed to implement a queue?
- A data structure to hold the data items
- A way to indicate the front of the queue
- A way to indicate the rear of the queue
How do you implement a linked list implementation of a queue?
We need 2 pointers, front, rear, and one variable called count to store the number of data items
What 2 cases are mostly considered when dealing with a linked list? Enqueue operation
- The queue is empty
- The queue is not empty
What 3 cases are considered for the Dequeue operation in a linked list?
- The queue is empty
- the queue has one data item
- The queue has more than 1 data item
How would a queue be implemented using an array?
Using 2 variables: front = 0 and count = number of data items
2 cases to consider using an array and the enqueue operation?
- The array is full
- The array is not full
What 2 cases to consider for the dequeue Operation and using an array?
- The queue is empty
- The queue is not empty
What do we need to keep track of when implementing a queue as a circular array?
We need to keep track of the front data item and the rear data item
What must one take into account when using the enqueue operation in a circular array?
The value of the rear is incremented but it needs to loop back to index 0
What line of code is used to loop back to the index 0
rear = (rear + 1) % queue.length
What is a bounded queue?
a queue with a length that does not exceed a specified maximum value
What is an unbounded queue?
is a queue with a length that can grow indefinitely
True or False.
If the maximum length is negative it is bounded.
False. It is unbounded
True or False.
If the maximum length is positive than it is unbounded.
False. It is bounded
What are the advantages of a circular array?
We do not need to shift items when performing a dequeue operation.
Last index in a circular array is
n - 1
