Queues

• There is behavior that stacks fail to model well
  • What if we want to remove from front instead of from back?
  • Can we model first-in, first-out behavior using other ADTs?
  • Vector: removing from the beginning of a list is an O(n) operation
  • Stack: need two stacks to get the first element (food for thought: how to do this?)
  • Grid: nah
• So, we need a new ADT...

Queues

• queue: ADT that retrieves elements in the order they were added
  • First-in, First-out ("FIFO")
  • Elements are stored in order of insertion, no indexes
  • Can add only to the end of a queue and can only examine or remove the front
• Basic Queue operations
  • enqueue: add an element to the back
  • dequeue: remove the front element
  • peek: examine the front element

Member functions

Food for thought: what is not an O(1) operation?

Example

Queue<int> q;                // {} front -> back
q.enqueue(42);               // {42}
q.enqueue(-3);               // {42, -3}
q.enqueue(17);               // {42, -3, 17}
cout << q.dequeue() << endl; // 42 (q is {-3, 17})
cout << q.peek() << endl;    // -3 (q is {-3, 17})
cout << q.dequeue() << endl; // -3 (q is {17}

Applications

• Real-world examples
  • Bank lines (or token system)
  • Call services -- being on hold
  • Anything first-come-first-serve
• Computers
  • Sending jobs to a printer
  • Uploading photos on social media

Exercise

Queue<int> queue;
for (int i = 1; i <= 6; i++) {
  queue.enqueue(i);
} // {1, 2, 3, 4, 5, 6}
for (int i = 0; i < queue.size(); i++) {
  cout << queue.dequeue() << " ";
}
cout << queue << " size " << queue.size() << endl;

A. 1 2 3 4 5 6 {} size 0
B. 1 2 3 {4, 5, 6} size 3
C. 1 2 3 4 5 6 {1, 2, 3, 4, 5, 6} size 6
D. none of the above

Exercise: Write a function duplicate that accepts a queue of integers and replaces every element with two copies of itself. For example, {1, 2, 3} becomes {1, 1, 2, 2, 3, 3}.

void duplicate(Queue<int>& q) {
  int size = q.size();
  for (int i = 0; i < size; i++) {
    int n = q.dequeue();
    q.enqueue(n);
    q.enqueue(n);
  }
}

Tips or using queues:

• Don't use size() directly

  int size = q.size();
  for (int i = 0; i < size; i++) {
    // do something with q.dequeue();
    // (including possibly re-adding it to the queue)
  }
  

• As with stacks, must pull contents out of queue to view them

  //process (and destroy) an entire queue
  while (!q.isEmpty()) {
     //do something with q.dequeue();
  }
  

Mixing stacks and queues

Queue<int> q {1, 2, 3};  // q={1, 2, 3}
Stack<int> s;

while (!q.isEmpty()) { //transfer queue to stack
  s.push(q.dequeue()); //q = {}, s = {1, 2, 3}
}

while (!s.isEmpty()) { //transfer stack to queue
  q.enqueue(s.pop());  //q = {3, 2, 1}, s = {}
}

cout << q << endl;   // {3, 2, 1}

Exercise: Write a function mirror that accepts a queue of strings and appends the queue's contents to itself in reverse order. For example, {"a", "b", "c"} becomes {"a", "b", "c", "c", "b", "a"}.

void mirror(Queue<string>& q) {
  Stack<string> s;
  int size = q.size();
  for (int i = 0; i < size; i++) {
    string str = q.dequeue();
    s.push(str);
    q.enqueue(str);
  }
  while (!s.isEmpty()) {
    q.enqueue(s.pop());
  }
}

Brief introduction to Dequeues: doubly-ended queues (pronounced "deck")

• deque: double-ended queue, pronounced "deck"
  • Can add/remove from either end
  • Combines many of the benefits of stack and queue
• Basic deque operations:
  • enqueueFront, enqueueBack
  • dequeueFront, dequeueBack
  • peekFront, peekBack
• Get queue and stack functionality in one data structure!

Mapping to C++ STL functions

Member functions (first Stanford function, then STL function, then description): reference http://www.cplusplus.com/reference/queue/queue/:

q.isEmpty()	q.empty()	returns true if queue has no elements
q.peek()	q.front()	returns front value without removing it; throws an error if queue is empty
q.dequeue()	q.pop()	C++ STL version only removes front value (but does not return it); throws an error if queue is empty
q.enqueue(value)	q.push(value)	places given value on top of queue, increasing its size by one
q.size()	q.size()	returns number of elements in queue.