Stacks and Queues

Stack ADT
Stack implementations
Queue ADT

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 1
 Announcements

• PA1 due Tuesday, May 27, 22:00

▪ pair work is highly recommended
▪ Document group via PrairieLearn group setting
▪ Choose carefully, you cannot leave your group or create a new one after your initial group setting
• But since it's the first official PL groupwork, contact Geoff if you make a mistake with your group settings
Use Google document for lecture Q&A
• Labs this week:
▪ Lab_linkedlists, due Tuesday May 27, 22:00
▪ Lab_quacks, due Thursday May 29, 22:00

• PA2 will release on Friday, May 23

• MT1 registration expected to open on Friday, May 23, 08:00

▪ register at https://us.prairietest.com/

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 2
 Stacks in practical usage

main()
CircleArea()
Sq()

4 5 + 7 2 - * 3 -
Distance()

Image from dennys.ca

Sq()
Sq()
sqrt()
( [ ( ) ( { } ) ] [ ( { [ ] } { } ) ] )

Common characteristic: the action happens at the top of the stack

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 3
 Stack abstract data type (ADT)

• ADT describes a data collection and the operations that can be

performed on the collection
▪ The effects of operations are well-understood (i.e. what happens)
▪ But how the operations are implemented are not described
Push(3)
Push(8)
template <class LIT> Push(4)
class Stack { Pop()
public: Push(6)
Stack(); // + copy, destructor etc. Push(2)
bool IsEmpty() const; Pop()
void Push(const LIT& e); // insert at top of stack Push(5)
LIT Pop(); // remove and return from top of stack Pop()
private: Pop()
// ??? Pop()
}; Pop()
The private members will reveal some details about the implementation,
but knowledge of only the public interface allows full usage and interaction
2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 4
 Stack implementation
Using a singly-linked list
• Make the front of the list serve as the top of the stack
▪ All operations can be done in 𝑂 1 time

a a
18 18

27 27

52 52

34 34

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 5
 Stack implementation

• Using a singly-linked list template <class LIT> template <class LIT>

class Stack { bool Stack<LIT>::IsEmpty() const {
public: return top == nullptr;
Stack(); }
bool IsEmpty() const;
void Push(const LIT& e);
LIT Pop();
template <class LIT>
private:
LIT Stack<LIT>::Pop() {
struct Node {
assert(!IsEmpty());
LIT data;
LIT ret = top->data;
Node* next; };
Node* temp = top;
Node* top;
top = top->next;
int size;
delete temp;
};
return ret;
}
template <class LIT>
void Stack<LIT>::Push(LIT d) {
Node* newnode = new Node(d);
newnode->next = top;
top = newnode;
}
2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 6
 Stack implementation
Using an array
• Make the most recently occupied index the top of the stack

6 3 8

top 2

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 7
 Stack implementation

• Using an array template <class LIT> template <class LIT>

class Stack { bool Stack<LIT>::IsEmpty() const {
public: return items.size() == 0;
Stack(); }
bool IsEmpty() const;
void Push(const LIT& e);
LIT Pop(); template <class LIT>
private: LIT Stack<LIT>::Pop() {
vector<LIT> items; assert(!IsEmpty());
}; LIT ret = items[items.size() - 1];
items.pop_back();
Notice that the public interface of this return ret;
}
implementation and of the linked list
implementation are exactly the same

template <class LIT>

void Stack<LIT>::Push(LIT d) {
Push should actually be a bit more
items.push_back(d);
} complicated than this

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 8
 Array resizing

• What if the array fills up?

▪ a vector is able to resize itself, but we may need more specific control over how
it resizes

6 3

6 3 8 5

Over a sequence of 𝑛 push operations, what happens? How many items will be copied?

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 9
 Array resizing

• What if we resized this differently?

Over a sequence of 𝑛 push operations, what happens? How many items will be copied?

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 10
 Stack implementation
Summary
• Linked list implementation:
▪ 𝑂 1 for all operations

• Array-based implementation:

▪ _________ pop

▪ _________ push

▪ Cost over 𝑂 𝑛 pushes is _________ for an average of ________ per push

• Why consider an array?

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 11
 Break time!

© 2004 Sega Corporation

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 12
 Queue ADT

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 13
 Queues

• In a queue items are inserted at the back (end/tail) and removed from the front (head)
• Queues are FIFO (First In First Out) data structures – fair data structures
• Applications include:
▪ Server requests
• Instant messaging servers queue up incoming messages
• Database requests
▪ Print queues
▪ Operating systems often use queues to schedule CPU jobs
▪ The waiting list for this course! (it’s presumably fair)
▪ Various algorithm implementations

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 14
 Queue operations

• A queue should implement at least the first two of these operations:

▪ enqueue – insert item at the back of the queue
▪ dequeue – remove an item from the front
▪ peek – return the item at the front of the queue without removing it
▪ is_empty – check if the queue does not contain any items
• Like stacks, it is assumed that these operations will be implemented efficiently
▪ That is, in constant time

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 15
 List queue example

Queue q;
q.enqueue(6);
front

back

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 16
 List queue example

Queue q;
q.enqueue(6);
front 6
q.enqueue(4);

back

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 17
 List queue example

Queue q;
q.enqueue(6);
front 6
q.enqueue(4);
q.enqueue(7);
4
q.enqueue(3);
back

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 18
 List queue example

Queue q;
q.enqueue(6);
front 6
q.enqueue(4);
q.enqueue(7);
4
q.enqueue(3);
back

q.dequeue(); 7

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 19
 List queue example

Queue q;
q.enqueue(6);
front
q.enqueue(4);
q.enqueue(7);
4
q.enqueue(3);
back

q.dequeue(); 7

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 20
 Queue ADT

• Linked list implementation template <class T>

bool Queue<T>::enqueue(T d) {
template <class T> Node* newN = new Node(d);
class Queue { if (back == nullptr)
public: front = back = newN;
Queue(); else {
bool is_empty() const; back->next = newN;
void enqueue(const T &e); back = newN;
T dequeue(); } template <class T>
private: } T Queue<T>::dequeue() {
struct Node { assert(!is_empty());
T data; T ret = front->data;
Node* next; Node* temp = front;
}; front = front->next;
Node* front, *back; delete temp;
}; template <class T> return ret;
bool Queue<T>::is_empty() const { }
return front == nullptr;
}
2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 21
 Queue implementation
Using an array
• Consider using an array as the underlying structure for a queue, we could
▪ Make the back of the queue the current size of the array, much like the stack implementation
▪ Initially make the front of the queue index 0
▪ Inserting an item is easy
• What to do when items are removed?
▪ Either move all remaining items down – slow
▪ Or increment the front index – wastes space

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 22
 Circular arrays

• Trick: use a circular array to insert and remove items from a queue
in constant time
• The idea of a circular array is that the end of the array “wraps
around” to the start of the array

7 0

6 1

0 1 2 3 4 5 6 7 5 2

4 3

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 23
 The modulo operator

• The mod operator (%) calculates remainders:

▪ 1%5 = 1, 2%5 = 2, 5%5 = 0, 8%5 = 3
• The mod operator can be used to calculate the front and back positions in a circular array
▪ Thereby avoiding comparisons to the array size
▪ The back of the queue is:
• (front + num) % capacity
• where num is the number of items in the queue Member attributes:
int front;
▪ After removing an item, the front of the queue is:
int capacity;
• (front + 1) % capacity T* arr;
int num;

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 24
 Array queue example

Queue myq; 0 01
front num
myq.enqueue(6);

6
0 1 2 3 4 5
Insert item at (front + num) % capacity, then
increment num

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 25
 Array queue example

Queue myq; 210 34

5
front num
myq.enqueue(6);

myq.enqueue(4);
6 4 7 3 8
myq.enqueue(7);
myq.enqueue(3); 0 1 2 3 4 5
myq.enqueue(8);
Insert item at (front + num) % capacity, then
myq.dequeue(); increment num
myq.dequeue();
Remove item at front, then decrement num
and make front = (front + 1) % capacity

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 26
 Array queue example

Queue myq; 2 453

front num
myq.enqueue(6);

myq.enqueue(4);
5 7 3 8 9
myq.enqueue(7);
myq.enqueue(3); 0 1 2 3 4 5
myq.enqueue(8);
Insert item at (front + num) % capacity, then
myq.dequeue(); increment num
myq.dequeue();
Remove item at front, then decrement num
myq.enqueue(9); and make front = (front + 1) % capacity

myq.enqueue(5);

enqueue is possible as long as the array is not full

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 27
 Array queue resizing

• Suppose we have an array-based queue and we have performed

some enqueue and dequeue operations
▪ Then we perform more enqueues to fill the array
▪ How should we resize the array to allow for more enqueue operations?

12 5 76 33 2 41

front

? ? ? ? ? ? ? ? ? ? ? ?

2025S Will Evans / Steve Wolfman / Cinda Heeren / Jordon Johnson / Seva Lynov / Geoffrey Tien 28