Lecture 12:

Stacks

CS 136: Spring 2024

Katie Keith

• Lab 4 released
• Two parts: Written (pen-and-paper), and code
• Evening Midterm next Thursday

📣 Announcements

Midterm material through (and including) March 14 lecture and Lab 4

Thurs March 20: Evening midterm

Lab periods are review Q&A sessions

📣 Announcements

Midterm details:

• On March 20, choose either 6-7:30pm or 8-9:30pm
• No need to tell me which one you’re coming to
• Covers Labs 0-4 and all lecture material through March 14th’s lecture
• Academic Accommodations: Arrange with me by this Friday (March 14)

​

• Emphasis on problem-solving. Some conceptual questions, some writing code (pen-and-paper)
• Closed-book exam (except for a reference sheet)
• Reference sheet: Allowed one 8.5x11in sheet (front & back) of handwritten notes
• Honor code will be enforced on the exam

📣 Announcements

Class Poll

Choice 1:

Give us a different instructor’s CS 136 exam as a practice exam, even though the instructor may have covered different subset of material than us and written an exam with a different level of difficulty. We’d have to sort through this on our own.

Choice 2:

To avoid the confusion, don’t release the practice exam which may not match Katie’s exam.

Midterm study tips

• Form study groups! Quiz each other!
• Go back and do the readings for concepts that are not solidified for you
• Review the important learning aspects from the labs
• 30 minutes of studying every day might help your brain more than a “cram” session

• Define a Stack ADT
• Examples using a Stack
• Implement a Stack (using LinkedLists)

🎯 Today’s Learning Objectives

📚Readings

• Sedgewick & Wayne. Algorithms. Section 1.3.

Review: ADT vs. Data Structures

Review: LinkedLists

first

A linked list is a recursive data structure that is either empty (null) or a reference to a node.

Node x = Node();

x.data = "to";

x.next = y;

Node y = Node();

y.data = "be";

y.next = z;

first = x;

instance variable of outer class

LinkedList.java

💻

// Returns the data at the given index of the list

public String get(int index) {

if (index < 0 || index >= this.size()){

System.out.println("Index out of range");

return null;

}

Node current = this.first;

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

current = current.data;

}

return current.data;

}

There are two mistakes in the Linked List method below. What are they and how would we fix them?

💡Think-pair-share

Doubly Linked Lists (Preview Lab 4)

In a doubly linked list, each node stores a reference to both the next and previous nodes.

first

null

null

last

link to the previous node

ADTs for Collections of Objects

Last week

Today!

This week!

Lab 4!

Lists, Stacks and Queues are all ADTs that involve the collection of objects. But they differ in the specification of which object is to be removed or examined next.

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

Stack Interface

public interface Stack<Item>{

// Pushes an item onto the stack

public abstract void push(Item item);

// Remove the most recently added item

public abstract Item pop();

// Returns true if the stack is empty

public abstract boolean isEmpty();

// Returns the number of items in the stack

public abstract int size();

}

​

ADTs limit operations on data

• We use ADTs not because they provide every available operation, but rather because they limit the types of operations we are allowed to perform.
• This prevents us from performing operations that we don’t want us or the user to do.
• If we are using a Stack, but we want more than just LIFO access, we should choose a different ADT.

1. What does the following code fragment print when n is 6?
2. What is it doing when presented with any positive integer n? Hint: This should remind you of an algorithm you implemented in one of the early labs!

​

​

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

​

while(n>0){

ourStack.push(n % 2);

n = n/2;

}

while(!ourStack.isEmpty()){

System.out.print(ourStack.pop());

}

​

💡Think-pair-share

• Define a Stack ADT
• Examples using a Stack
• Implement a Stack (using LinkedLists)

✅

🎯 Today’s Learning Objectives

Example Stack Use: Back button when web browsing

• 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).

Example Stack Use: Call Stack

A call stack tracks method calls during program execution

• Method call: push stack frame (local environment and return address)
• Method finishes execution (e.g., returns) : pop stack frame

​

Example:

Call stack: LIFO, Last method called is the first to be completed and removed from the stack

Board work

public static int fib(int n) {

if (n == 0|| n == 1) {

return n;

} else {

return fib(n - 1) + fib(n - 2);

}

}

Stack Overflow

In Java, the size of the call stack is limited. Excessive recursion or deeply nested method calls can lead to a StackOverflowError.

Example Stack Use: Call Stack

A call stack tracks method calls during program execution

• Method call: push stack frame (local environment and return address)
• Method finishes execution (e.g., returns) : pop stack frame

Example:

Call stack: LIFO, Last method called is the first to be completed and removed from the stack

Exercise for you!

private static int[] fibCache = new int[100];

​

public static int fib(int n){

if(n == 0|| n == 1){return n;}

if(fibCache[n] > 0){

return fibCache[n];

}

fibCache[n] = fib(n-1) + fib(n-2);

return fibCache[n];

}

0

0

0

0

…

fibCache

• Define a Stack ADT
• Examples using a Stack
• Implement a Stack (using LinkedLists)

✅

✅

🎯 Today’s Learning Objectives

StackWithLinkedLists.java

💻

• Define a Stack ADT
• Examples using a Stack
• Implement a Stack (using LinkedLists)

✅

✅

✅

🎯 Today’s Learning Objectives