Queue Flashcards
what is the order of operations in a queue?
FIFO
First in First Out
is the queue a concrete class or an ADT
it’s both as an ADT is merely that the class implements a specific behavior to be a queue
what are other types of queues?
Deque :
double ended queue meaning u can remove or add at the end of beginning of a queue which operates like a stack
Priority Queue:
u add the element to the queue according to it’s priority
what are the operations of a queue?
Enqueue
Dequeue
Empty
all of them are O(1) but with an array dequeue is O(N)
how to implement a queue?
with a linked list or an array
what is a circular queue?
it’s a data structure that uses a single, fixed size buffer as if it were connected from end to end and is used in buffering data streams
Uses of a circular queue or Deque
it’s useful because the property doesn’t need to be shuffled around when consumed and it makes good strategy when it’s of a fixed size and one of the problems that it solves is the producer-consumer-problem as it operates that the producer overwrites old data that the consumer couldn’t keep up with getting
when do u put the first element in a circular queue?
u can put it in any index
what happens when u write on a circular queue when it’s full?
it depends but in most cases it overwrites the oldest data present but u could also raise an exception
how to know that a circular queue is empty or full?
if the start pointer is equal to the end pointer then it’s empty and if the end pointer is one less than the first pointer then it’s full
what is the producer-consumer problem?
it’s when a producer puts data in a buffer and a consumer takes from that buffer taking into account that the producer wouldn’t put into a full queue and the consumer wouldn’t take from an empty queue
what are some solutions to producer-consumer problem
https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem
wake and sleep which produce a deadlock
semaphores
monitors
