Lecture Preview: Stacks and Queues

(Suggested book reading: Programming Abstractions in C++, section 5.2 - 5.3)

In this lecture we will talk about two new data structures:

  • A stack is a collection where you add elements to the "top" of the ordering, and remove from the "top" as well. The only accessible element is the one added latest. A stack is sometimes called a Last In, First Out ("LIFO") structure.

    stack

  • A queue is a collection where you add elements to the "back" of the ordering, and remove from the "front" of the ordering. The only accessible element is the one added earliest. A queue is sometimes called a First In, First Out ("FIFO") structure.

    queue

When you declare a stack or queue, you write the type of data it will contain in < > brackets. Here is a short code example that uses a stack: 

Stack<int> s;                  // {}     bottom -> top
s.push(42);                    // {42}
s.push(-3);                    // {42, -3}
s.push(17);                    // {42, -3, 17}

cout << s.pop() << endl;       // 17   (s is {42, -3})
cout << s.peek() << endl;      // -3   (s is {42, -3})
cout << s.pop() << endl;       // -3   (s is {42})

Here is a short code example that uses a queue: 

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})
This document and its content are copyright © Marty Stepp and Julie Zelenski, 2019. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.