Queue

0 phút đọc

Quick Reference

Worst Case
space O(n)
enqueue O(1)
dequeue O(1)
peek O(1)

A queue stores items in a first-in, first-out (FIFO) order.

Picture a queue like the line outside a busy restaurant. First come, first served.

Strengths

  • Fast operations. All queue operations take $$O(1)$$ time.

Uses

  • Breadth-first search uses a queue to keep track of the nodes to visit next.
  • Printers use queues to manage jobs—jobs get printed in the order they're submitted.
  • Web servers use queues to manage requests—page requests get fulfilled in the order they're received.
  • Processes wait in the CPU scheduler's queue for their turn to run.

Implementation

Queues are easy to implement with linked lists:

  • To enqueue, insert at the tail of the linked list.
  • To dequeue, remove at the head of the linked list.

You could implement a queue with an array or dynamic array, but it would get kinda messy. Try drawing it out. You'll notice that you'd need to build out a "scoot over" or "re-center" operation that automatically fires when your queue items hit the bottom edge of the array.

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào

Avatar TechMely Team
Được viết bởi

TechMely Team

Bạn cần sự hiểu biết và sáng tạo nên cuộc sống đã ban cho bạn đôi bàn tay và trí óc để khám phá và làm việc
Khoá học javascript từ cơ bản đến chuyên sâuYoutube Techmely