Lecture 13:

Queues

CS 136: Spring 2024

Katie Keith

• Working on Lab 4 this week
• CS movie night tomorrow!

📣 Announcements

• Implement a Stack with Arrays
• Define a Queue
• Implement a Queue with Arrays

🎯 Today’s Learning Objectives

📚Readings

• Sedgewick & Wayne. Algorithms. Section 1.3.

Review Stack

A stack is a linear collection of elements with operations based on a last-in-first-out (LIFO) policy. A push operation adds an element to the stack and a pop operation removes an element.

Figure credit

Review: Example Stack Use: Back button

• Your browser displays the new page (and pushes onto a stack).
• You can keep clicking on hyperlinks to visit new pages.
• But you can also always revisit the previous page by clicking the back button (popping it from the stack).

Review: ADT vs. Data Structures

Last week

Today!

This past Monday

Today!

Lab 4!

I am going to use an array to implement a Stack ADT.

​

I want to be able to dynamically grow the size of my stack so I implement the following:

• When push() is called: increase size of array by 1
• When pop() is called: decrease size of array by 1

​

1. Is my resizing decision efficient? If not, what should I do?
2. When I push and pop, where in the array should I put the items? Why?

Example array

💡Think-pair-share

StackWithArrays.java

💻

“Ugly” Cast 😞

s = (Item[]) new Object[capacity];

😞

Java 8 doesn’t allow direct creation of generic arrays

• Implement a Stack with Arrays
• Define a Queue
• Implement a Queue with Arrays

✅

🎯 Today’s Learning Objectives

Queue

A queue is a linear collection of elements with operations based on a first-in-first-out (FIFO) policy.

We use operations enqueue (add to the back of the queue) and dequeue (remove from the front of the queue).

​

Figure credit

Queue in the “real world”

Queue interface

public interface Queue<Item>{

// Returns true if the queue is empty

public abstract boolean isEmpty();

// Returns the number of items in the queue

public abstract int size();

// Adds an item to the end of the queue

public abstract void enqueue(Item item);

// Returns the first in the queue (and removes that item from the queue)

public abstract Item dequeue();

// Returns the element that is first in the queue (but does NOT remove it)

public abstract Item peek();

}

​

Example Queue Use: Printing jobs

For a printer, jobs submitted to the printer are stored in a queue. Then, the first job sent to the printer is the first one printed (first-in-first-out).

1. What does the following code fragment print for n=5?
2. What is this code doing in general?
3. What is the big-O runtime of this code fragment?

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

q.enqueue(0);

q.enqueue(1);

for (int i =0; i<=n; i++){

int a = q.dequeue();

int b = q.dequeue();

q.enqueue(b);

q.enqueue(a + b);

System.out.println(a);

}

​

💡Think-pair-share

• Implement a Stack with Arrays
• Define a Queue
• Implement a Queue with Arrays

✅

✅

🎯 Today’s Learning Objectives

Design sketch: Implementing a Queue with Arrays

Can wrap around!

Next available slot

QueueWithArrays.java

💻

Wrapping around: Enqueue

public void enqueue(Item item) {

if(n == q.length){

resize(GROWTH_FACTOR*q.length);

}

​

q[tail++] = item;

if (tail == q.length){

tail = 0;

}

n++

}

​

“a”

We enqueued this item

tail == 0

Next item will go here

head == 2

Wrapping around: Dequeue

public Item dequeue() {

Item item = q[head];

n --;

head ++;

if(head == q.length){

head = 0;

}

return item;

}

​

tail == 1

head == q.length -1

“a”

Before dequeue

After dequeue

null

tail == 1

head == 0

Suppose we declare and create a queue q and enqueue to it a number of Strings.

​

​

​

What does the following code fragment do to the queue q?

​

​

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

while(!q.isEmpty()){

s.push(q.dequeue());

}

while(!s.isEmpty()){

q.enqueue(s.pop());

}

​

“c”

“d”

head of queue

tail of queue

💡Think-pair-share

• Implement a Stack with Arrays
• Define a Queue
• Implement a Queue with Arrays

✅

✅

✅

🎯 Today’s Learning Objectives

Design Sketch: Implementing a Stack with Arrays

• Create an instance variable that stores the number of items in the stack
• Create another instance variable that is an array of Items
• Most recently inserted item in array[n-1] and the least recently inserted item in array[0]
• This policy allows us to add and remove items at the end without moving any of the other items in the stack
• We must resize the array if need be

Design sketch: Implementing a Queue with Arrays

• Create an instance variable that stores the number of items in the queue
• Create another instance variable that is an array of Items
• Keep track of the index of the first and last elements in the queue (also instance variables)
• Enqueue and deque elements based on our first/last index
• We must resize the array after enqueuing if need be