English
Menu

What is Queue?

A first-in, first-out (FIFO) data structure in which the element added first is removed first. Adding to the back is called enqueue and removing from the front is called dequeue. Queues are used for waiting lines of work, passing data between tasks and breadth-first search.

Japanese name: キュー

Queue appears in 12 practice questions across 9 topics, including Data Structures and Algorithms, GPU Programming, Multicore & Synchronization.

Field: Data Structures and Algorithms

Try it: questions about Queue

When waiting on a condition variable until a queue becomes non-empty, why is the condition rechecked in a while loop rather than an if after waking?

  1. AA while loop runs faster than an if statement
  2. BCondition variables cannot be used with if statements
  3. CEven after waking, another thread may have taken the item first or the wake-up may be spurious, so the condition may not hold
Show answer and explanation

Answer: C. Even after waking, another thread may have taken the item first or the wake-up may be spurious, so the condition may not hold

Waiting on a condition variable releases the lock and sleeps; when signaled, the thread reacquires the lock and returns. But before it does, another thread may grab the lock and take the queue element. Implementations are also allowed to wake a thread with no signal at all (a spurious wake-up). So the code checks the condition after waking and waits again if it does not hold, using a while loop.

In an RTOS, what is the advantage of using a queue (message queue) to pass data from a sensor-reading task to a display task?

  1. AData passing through a queue is encrypted automatically
  2. BThe receiver can sleep until data arrives, and differences in speed between sender and receiver are absorbed by the queue
  3. CUsing a queue makes task priorities unnecessary
Show answer and explanation

Answer: B. The receiver can sleep until data arrives, and differences in speed between sender and receiver are absorbed by the queue

Passing data through a shared variable and flag requires guarding against data races and having the receiver check repeatedly. With an RTOS queue, the sender simply puts data in and the receiver waits in a blocked state without using CPU until data arrives. Because several items can be buffered, no data is lost even if the sender is temporarily faster.

Queue in the explanations

Questions that mention Queue (12)

  1. When waiting on a condition variable until a queue becomes non-empty, why is the condition rechecked in a while loop rather than an if after waking?
  2. In an RTOS, what is the advantage of using a queue (message queue) to pass data from a sensor-reading task to a display task?
  3. Elements A, B and C are added to an empty queue in this order. Then one element is removed, D is added and one is removed, and E is added and one is removed. In what order are the elements removed?
  4. A queue uses the 4-element string array q as a ring. head and tail start at 1. enq(v) does q[tail] ← v and then tail ← tail mod 4 + 1; deq() returns the value of q[head] and then does head ← head mod 4 + 1. When the following program runs, in which element of q is "E" stored?
  5. Which interface standard, built on PCI Express, is widely used to connect high-speed SSDs to the host?
  6. What is the main purpose of using multiple CUDA streams?
  7. In CUDA, what generally happens right after the CPU-side program launches a kernel?
  8. What is a characteristic of MSI (message-signaled interrupts) used in PCI Express?
  9. Which correctly describes the basic idea of TCP congestion control?
  10. When the JavaScript above is run in a browser, which of the following is the order in which the characters are shown on the console?
  11. On an empty stack, the operations push 1, push 2, pop, push 3, push 4, pop, pop are performed in this order. In what order are the values removed by pop?
  12. In a graph whose edges have no weights, you want to find the smallest number of edges from a starting vertex to every other vertex. Which pair of search method and data structure is suitable?

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Stack Breadth-first search PCI Express CUDA GPU Condition variable Real-time operating system (RTOS) Variable Array Modulo operation

Back to the glossary