Skip to Main Content

Data Structures

Computer Science Department

Pancake Stack - 10 Course Points

The purpose of this assignment is to learn how to implement the methods of a linked list based stack.

You can download and submit the project files via Autolab.

Refer to our Programming Assignments FAQ for instructions on how to install VSCode, how to use the command line and how to submit your assignments.

See this video on how to import the project into VSCode and how to submit into Autolab.

 

The assignment has one component:

– Coding (10 points) submitted through Autolab.

Overview

The PancakeStack.java class has a linked list representation of a stack. The class attributes and the constructor are provided. 

You must fill in the code for the push() and pop() methods to finish the implementation, and to allow the Driver visualization to work.  

There are two class attributes provided:

  • LLNode<String> topPancake
    • This contains the reference to the top node in the stack, at first this will be null but as nodes get added to the stack this will be updated
  • int numPancakes
    • Keeps track of how many pancakes (nodes) are in the stack, starts at 0

A stack is a last in first out (LIFO) data structure. The newest node added into the stack will go at the very top of the stack. When we remove a node from the stack, we remove the node at the very top. For this reason a linked list representation of a stack only needs one pointer to the node at the very top. We can then add and remove items from the stack in O(1) time. 

Overview of files provided

  • PancakeStack.java – This file contains the linked list representation of a stack of strings, this is the file that you have to edit. This will be submitted to Autolab. 
  • Driver.java – this is used to visualize the stack of strings, and will only start to work once you fill in the methods in the PancakeStack class. This will not be submitted.

UPDATE and SUBMIT the PancakeStack.java file to Autolab

Working with LLNode<> objects

For assignments/labs in CS112, we will use a cs112.jar file containing useful classes. This includes the LLNode<> class, which implements a single linked list node. There are other classes in this jar file, which you will be introduced to in later labs/assignments.

  • The LLNode class takes in a generic type, which means it can store any type of data. In this lab you will be working with nodes that have String data – to have nodes with String data we can use LLNode<String> 
  • Making a node: LLNode<T> newNode = new LLNode<>(data) — replace T with a type
    • Note that the data must be passed in for the constructor, and the data of a node can not be changed later (aka it is immutable)
  • Methods: 
    • getNext() – returns the next node in the linked list 
    • getData() – returns the data stored in the current node
    • setNext(LLNode<T> nextNode) – sets the next node of the current node to nextNode

Implementation Notes

  • YOU MAY only update the methods with the WRITE YOUR CODE HERE line 

  • DO NOT add any instance variables to the PancakeStack class

  • DO NOT add any public methods to the PancakeStack class

  • DO NOT change the headers of ANY of the given functions

  • DO NOT add any import statements 

  • DO NOT change the class name

  • DO NOT use System.exit()

Programming

First, ensure that you are working in the correct directory. See this image: 

Methods to be implemented by you:

1. push(String pancakeType)

Add a Node to the top of the stack. The top of the stack is referenced to by the pointer called topPancake. 

  • Make a new node with the String pancakeType as the data 
  • Then make this node the node at the top of the stack, look at the description for the setNext method above and remember to update the topPancake reference to this new node

Then, increment numPancakes by 1 to show that you have added an item to the stack. 

2. pop()

Remove the node at the top of the stack, and return the String data of the removed node. 

If the stack does not contain any nodes, then return null

Otherwise:

  • Store the String data of the top node of the stack 
  • Remove the top node in the stack
  • Return the String that you stored earlier, this String has the String data of the node which was just removed

Finally, decrement numPancakes by 1 to show that an item was removed from the stack.  

Driver

Once you implement your code, you can run the Driver.java file and interact with the driver. It will show a visualization of a stack of pancakes, with buttons to push three different types of pancakes as well as pop the top pancake.

You can use this Driver to test your code, but it is still useful to write JUnit test cases.

Writing JUnit Tests 

You do not have to submit this, this is for you to test your own code.

Since this stack implementation contains public methods, and represents a generalized stack of strings, we can test it independently of the driver using a test class.

In the main project folder, there exists a “test” folder next to the “src” folder. This contains a JUnit test class, which can run and test pieces of your code. To compile and run these tests, you must install the Test Runner extension. See the Programming FAQ for more info on VScode extensions.

There are two tests for push() and pop(), and you must fill these tests in order for them to work. Once you do, remove the fail() statements at the bottom and run. 

You are provided with a premade JUnit test class for PancakeStack. You can finish writing the test methods, by using JUnit test methods (such as assertTrue(), assertFalse(), assertEquals()) in order to test your code.

Tests not running? 

First, make sure you’re in the right folder and the tests are implemented. Next, if you have the “Code Runner for Java” or Oracle “Java” extension, make sure you uninstall those extensions. Remember that you must fill in the tests for push() and pop().

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

Importing VSCode Project

  1. Download PancakeStack.zip from Autolab Attachments.

  2. Unzip the file by double clicking.

  3. Open VSCode

    • Import the folder to a workspace through File > Open Folder

Executing and Debugging

  • You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.

  • How to debug your code

  • You can hit the triangle “Run Java” button at the top of the Driver.java class, or right click on Driver.java and select “Run Java”

NOTE: if you have PancakeStack (2) -> PancakeStack or CS112 -> PancakeStack in VS Code, open the INNERMOST PancakeStack through File -> Open Folder.

Before submission

REMOVE all print statements you have written in PancakeStack.java 

Collaboration policy. Read our collaboration policy on the course syllabus.

Submitting the assignment. Submit PancakeStack.java separately via the web submission system called Autolab. To do this, go to Autolab and find the correct assignment and submit your Java file.

  

Getting help

If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza.

  • Find instructors and Lead TAs office hours here
  • Find tutors office hours on Canvas -> Tutoring
  • In addition to office hours we have the Coding and Social Lounge (CSL), a community space staffed with lab assistants which are undergraduate students further along the CS major to answer questions.

By Sulaiman Hasan