CSE 143

Lecture 4: Stacks and Queues

 Stacks and queues
• Sometimes it is good to have a collection that is less powerful, but is
optimized to perform certain operations very quickly.

• Today we will examine two specialty collections:

– stack: Retrieves elements in the reverse of the order they were added.
– queue: Retrieves elements in the same order they were added.
push pop, peek

front back
top 3 remove, peek add
1 2 3
2
queue
bottom 1
stack
2
 Abstract data types (ADTs)
• abstract data type (ADT): A specification of a collection of data and
the operations that can be performed on it.
– Describes what a collection does, not how it does it

• We don't know exactly how a stack or queue is implemented, and we

don't need to.
– We just need to understand the idea of the collection and what
operations it can perform.

(Stacks are usually implemented with arrays; queues are often

implemented using another structure called a linked list.)

3
 Stacks
• stack: A collection based on the principle of adding elements and
retrieving them in the opposite order.
– Last-In, First-Out ("LIFO")
– The elements are stored in order of insertion,
but we do not think of them as having indexes.
– The client can only add/remove/examine
the last element added (the "top").
push pop, peek

• basic stack operations:

– push: Add an element to the top. top 3
– pop: Remove the top element. 2
– peek: Examine the top element. bottom 1
stack
4
 Stacks in computer science
• Programming languages and compilers:
– method calls are placed onto a stack (call=push, return=pop)
– compilers use stacks to evaluate expressions
return var
method3 local vars
parameters
return var
• Matching up related pairs of things: method2 local vars
parameters
– find out whether a string is a palindrome return var
method1 local vars
parameters
– examine a file to see if its braces { } match
– convert "infix" expressions to pre/postfix

• Sophisticated algorithms:
– searching through a maze with "backtracking"
– many programs use an "undo stack" of previous operations
5
 Class Stack
Stack<E>() constructs a new stack with elements of type E
push(value) places given value on top of stack
pop() removes top value from stack and returns it;
throws EmptyStackException if stack is empty
peek() returns top value from stack without removing it;
throws EmptyStackException if stack is empty
size() returns number of elements in stack
isEmpty() returns true if stack has no elements

Stack<Integer> s = new Stack<Integer>();

s.push(42);
s.push(-3);
s.push(17); // bottom [42, -3, 17] top
System.out.println(s.pop()); // 17

– Stack has other methods, but we forbid you to use them. 6

 Stack limitations/idioms
• Remember: You cannot loop over a stack in the usual way.
Stack<Integer> s = new Stack<Integer>();
...
for (int i = 0; i < s.size(); i++) {
do something with s.get(i);
}

• Instead, you must pull contents out of the stack to view them.
– common idiom: Removing each element until the stack is empty.

// process (and destroy) an entire stack

while (!s.isEmpty()) {
do something with s.pop();
}
7
 Exercise
• Consider an input file of exam scores in reverse ABC order:
Woods Vivyan 64
VanHofwegen Raquel 92
Rhodehamel Derek 95
Pendleton Anna 87
...

• Write code to print the exam scores in ABC order using a stack.

– What if we want to further process the exams after printing?

8
 Queues
• queue: Retrieves elements in the order they were added.
– First-In, First-Out ("FIFO")
– Elements are stored in order of
insertion but don't have indexes.
– Client can only add to the end of the
queue, and can only examine/remove
the front of the queue.
front back
remove, peek add
1 2 3

• basic queue operations: queue

– add (enqueue): Add an element to the back.
– remove (dequeue): Remove the front element.
– peek: Examine the front element.
11
 Queues in computer science
• Operating systems:
– queue of print jobs to send to the printer
– queue of programs / processes to be run
– queue of network data packets to send

• Programming:
– modeling a line of customers or clients
– storing a queue of computations to be performed in order

• Real world examples:

– people on an escalator or waiting in a line
– cars at a gas station (or on an assembly line)
12
 Programming with Queues
add(value) places given value at back of queue
remove() removes value from front of queue and returns it;
throws a NoSuchElementException if queue is empty
peek() returns front value from queue without removing it;
returns null if queue is empty
size() returns number of elements in queue
isEmpty() returns true if queue has no elements

Queue<Integer> q = new LinkedList<Integer>();

q.add(42);
q.add(-3);
q.add(17); // front [42, -3, 17] back
System.out.println(q.remove()); // 42

– IMPORTANT: When constructing a queue you must use a new

LinkedList object instead of a new Queue object.
• This has to do with a topic we'll discuss later called interfaces. 13
 Queue idioms
• 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.remove();
}

– another idiom: Examining each element exactly once.

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

• Why do we need the size variable?

14
 Mixing stacks and queues
• We often mix stacks and queues to achieve certain effects.
– Example: Reverse the order of the elements of a queue.
Queue<Integer> q = new LinkedList<Integer>();
q.add(1);
q.add(2);
q.add(3); // [1, 2, 3]

Stack<Integer> s = new Stack<Integer>();

while (!q.isEmpty()) { // Q -> S
s.push(q.remove());
}
while (!s.isEmpty()) { // S -> Q
q.add(s.pop());
}
System.out.println(q); // [3, 2, 1]
15
 Exercise
• Modify our exam score program so that it reads the exam scores into
a queue and prints the queue.

– Next, filter out any exams where the student got a score of 100.

– Then perform your previous code of reversing and printing the

remaining students.

• What if we want to further process the exams after printing?

16
 Exercises
• Write a method stutter that accepts a queue of integers as a
parameter and replaces every element of the queue with two copies
of that element.
– front [1, 2, 3] back
becomes
front [1, 1, 2, 2, 3, 3] back

• Write a method mirror that accepts a queue of strings as a

parameter and appends the queue's contents to itself in reverse
order.
– front [a, b, c] back
becomes
front [a, b, c, c, b, a] back
17