Queue Theory: FIFO Principle
Queue Theory: FIFO Principle
Having explored Stacks and their LIFO (Last-In, First-Out) behavior, let's now turn our attention to another fundamental Abstract Data Type (ADT): the Queue. While a stack is like a pile where you add and remove from the top, a queue operates more like a line, introducing a different but equally important principle.
1. The FIFO Principle
The defining characteristic of a Queue is its FIFO (First-In, First-Out) principle. This means that the first element added to the queue will always be the first one to be removed. It's an exact opposite to the LIFO principle of stacks.
-
Concept: Elements are added at one end (traditionally called the "rear" or "tail") and removed from the other end (traditionally called the "front" or "head").
-
Analogy:
- A waiting line: Think of customers waiting in line at a store, or cars waiting at a traffic light. The person (or car) who arrived first is the one who gets served (or moves) first.
- A printer queue: Documents sent to a printer are usually printed in the order they were received.
- A customer service call queue: Calls are typically answered in the order they were placed.
2. Core Queue Operations
Similar to stacks, queues are defined by a specific set of operations that manipulate their elements, adhering strictly to the FIFO rule.
2.1. Enqueue: .enqueue(element)
Adds a new element to the rear (tail) of the queue.
-
Concept:
- Place the
elementat the back of the line. - Increment the queue's size.
- Place the
-
Time Complexity:
O(1)(typically constant time, as you're always operating on one specific end). -
Space Complexity:
O(1)(for the new element).
2.2. Dequeue: .dequeue()
Removes and returns the element from the front (head) of the queue.
-
Concept:
- Check if the queue is empty. If so, indicate an error (or return
null/undefined). - Remove the element currently at the front of the line.
- Decrement the queue's size.
- Return the removed element.
- Check if the queue is empty. If so, indicate an error (or return
-
Time Complexity:
O(1)(typically constant time, as you're always operating on one specific end). -
Space Complexity:
O(1)
2.3. Peek (or Front): .peek() / .front()
Returns the element at the front of the queue without removing it.
-
Concept:
- Check if the queue is empty. If so, indicate an error.
- Return the element currently at the front.
-
Time Complexity:
O(1) -
Space Complexity:
O(1)
2.4. IsEmpty: .isEmpty()
Checks if the queue contains any elements.
-
Concept:
- Return
trueif the queue's size is zero; otherwise, returnfalse.
- Return
-
Time Complexity:
O(1) -
Space Complexity:
O(1)
2.5. Size: .size()
Returns the number of elements currently in the queue.
-
Concept:
- Return the current count of elements in the queue.
-
Time Complexity:
O(1) -
Space Complexity:
O(1)
Key Takeaway: The FIFO principle is the defining characteristic of a queue. All fundamental operations,
enqueueanddequeue, always happen at opposite ends, ensuring that elements are processed in the order they arrived, usually with efficientO(1)time complexity.
التالي · الدرس 37 من 92
Queue Implementations (Array-based, Linked List-based)
قراءة 7 دقيقة
أنهيت 36 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

