Another ADT: Queues

This page provides lecture notes for an additional example of an abstract data type. Due to time constraints, I didn’t have time to present this during class, but it may help provide additional examples to clarify the concept of ADTs.

Queues

• Previously we developed a stack ADT
• Stacks are LIFO: last in, first out
  • Common in computing, but real life is often “first come first served”
• Queues are FIFO: first in, first out
  • Waiting in line to get coffee
  • Pull a number to get service

Queues in CS

• Access to shared resources:
  • Printers
  • CPU/GPU time
  • Network bandwidth
• Also, our good friend the input buffer is a sort of queue!

Characteristics

• Just like stacks, queues are a linear data structure of a homogeneous type
• Queues are ordered by time added, with the oldest data at the “front” or head and the newest data at the “back” or tail
• It follows that we can only add data to the tail and remove data from the head
• Like stacks, queues can have a finite capacity or be unbounded
• As an ADT, queue implementation is not specified

Queue operations

• enqueue: add an item to the tail of the queue
• dequeue: remove an item from the head of the queue
• empty: check if the queue is empty
• full: check if the queue is full - only applies to bounded queues!

Other potential queue operations

• peek: return the item at the head of the queue without removing it
  • In the stack ADT, this could be implemented as pop followed by push
  • In the queue ADT, could we dequeue then enqueue?
• length: return the number of items in the queue
• What about the following?
  • exit the queue
  • search the queue for a particular item
  • insert an item at a particular position

A queue of integers: interface

class IntQueue {
public:
    IntQueue();
    ~IntQueue();

    void enqueue(int item); // add an item to the tail
    int dequeue(); // remove an item from the head
    bool empty() const; // check if the queue is empty
private:
    ???
};

This assumes we are implementing an unbounded queue. What would change if we wanted a bounded queue?

A queue of integers: sample usage

IntQueue q;
int n;
source >> n;
while (!source.eof()) {
    q.enqueue(n);
    source >> n;
}

while (!q.empty()) {
    cout << q.dequeue() << ' ' << endl;
}

Assume source contains integers from 1 to 5. What is the output?

Usage challenge

Given a queue of integers as shown, replace the contents of the queue with the product of all the numbers

Approach:

1. Dequeue the first two items
2. Multiply them together
3. Enqueue the result
4. Repeat until the queue is empty

Queue implementation

• Just like stacks, queues can be implemented using a linked list or an array
• Let’s focus on the linked list implementation
  • Why? More practice with linked data structures, but also linked lists are unbounded by default
• While stacks just needed to know the head pointer, queues need to know both the head and tail pointers
• Once more, we’ll implement it as a nested data structure

Queue implementation using linked lists

class IntQueue {
public:
...
private:
    struct Node {
        int data;
        Node *next;
    };
    Node *head;
    Node *tail;
};

Queue: constructor/destructor and helpers

IntQueue::IntQueue() {
    head = NULL;
    tail = NULL;
}

IntQueue::~IntQueue() {
    while (!empty()) {
        dequeue();
    }
}

bool IntQueue::empty() const {
    return head == NULL;
}

int IntQueue::peek() const {
    if (empty())
        ???;
    return head->data;
}

• What should happen in peek if the queue is empty?
• Goes back to the question of who is responsible for checking
• For now we’ll delegate to the client code

Queue: enqueue and dequeue

void IntQueue::enqueue(int item) {
    Node *new_node = new Node;
    new_node->data = item;
    new_node->next = NULL;
    if (empty())
        head = new_node;
    else
        tail->next = new_node;
    
    tail = new_node;
}

int IntQueue::dequeue() {
    int result = head->data;
    Node *dying = head;
    head = head->next;
    delete dying;
    if (empty())
        tail = NULL;

    return result;
}

• Note that the first item we enqueue becomes both the head and the tail
• Similarly if we dequeue the last item, head and tail must both be NULL