Course contentsShow
← Computer Science
Lesson 377 of 2,8729. Stacks and QueuesFree lesson

Queue Interface and Specification

Formal specification of queue operations, preconditions, postconditions, and error handling.

Queue Interface and Specification

What You'll Learn

You'll learn how to formally specify what a queue must do, including operation contracts, requirements, and how to handle errors.

The Core Idea

An interface describes what operations a data structure provides without dictating how they work internally. A specification documents each operation's expectations (preconditions), guarantees (postconditions), and error behavior.

Think of it like a restaurant menu: it tells you what dishes are available and what you'll receive, but not the kitchen's cooking methods.

Queue Interface Components

Operation Signatures

The queue interface declares operations like enqueue, dequeue, peek, isEmpty, and size with their input/output types.

Preconditions

Requirements that must be true before calling an operation:

  • dequeue: Queue must not be empty
  • peek: Queue must not be empty
  • enqueue: May require available memory or capacity

Postconditions

Guarantees about the state after an operation succeeds:

  • enqueue(x): Element x is now at the rear; size increases by 1
  • dequeue: Front element removed; size decreases by 1; remaining elements maintain order
  • isEmpty: Returns true if and only if size equals 0

Error Handling

When preconditions aren't met:

  • Underflow: Attempting dequeue or peek on an empty queue
  • Overflow: Attempting enqueue when capacity is full (bounded queues)

Common responses: throw an exception, return an error code, or return a special "invalid" value.

Example Specification

dequeue()
Precondition: Queue is not empty
Postcondition: Returns and removes the front element; size decreases by 1
Error: Throws underflow exception if empty

Key Takeaway: A queue specification defines precise contracts for each operation—what must be true before calling it (preconditions), what's guaranteed after (postconditions), and how errors are handled—ensuring consistent, predictable behavior regardless of implementation.