1 Stack Overview A stack is a collection that works in Last-In-First-Out(LIFO) f
ID: 3689697 • Letter: 1
Question
1 Stack Overview A stack is a collection that works in Last-In-First-Out(LIFO) fashion. Think about a box of saltine crackers. If the box is empty and you fill it with crackers, then the bottom cracker is the first you put in, and it will be the last to taken out. Also, the last cracker you put into the box will be the first one you will take out.( Unless you open the other side of the box, which is not the example in this case. ) A stack has two basic operations, pop() and push(). By using the push() operation, we add things to the stack and with pop() operation we take out the last element we put. Many stack operations also have the peek() operation, which returns the top item but doesn’t remove it.
2 Instructions This lab is designed to help you with the Homework ”Simulating with Stacks &Queues”. 1. In the attached code, you can see that we used linked lists to create the ”Stack” data structure. This stack is written in singly linked list fashion. Please change the methods accordingly to make it a doubly linked list. Hints are given in comments, noted as ”TO-DO”. You can remember how to change a singly linked list to a doubly linked list from your Homework 6 and 7. 2. Second important task in this lab is reading a file using a file reader class. We suggest you to use the Scanner class, which is mentioned in Homework ”Simulating with Stacks &Queues”. Please read the ’heroes’ file, as it’s mentioned in that HW ’week1’ part and put the input from the file into the stack. You don’t have to create a long list of heroes, just two will be enough. The goal of this lab to read a file, put the input into the stack and change the stack into a doubly linked list. Then, in your main method, test your file reader and see how it works. A basic test outline and Stack code is provided for you.
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package com.list;
public class Main {
public static void main(String[] args) {
Main mainClass = new Main();
Stack list = new Stack();
String hero1 = new String();
String hero2 = new String();
/** * TO-DO:
* Lab 09: Use scanner class to read the hero names,
* and assign those names to two Strings above.
*/
list.push(hero1);
list.push(hero2);
System.out.println("Length : "+list.size());
list.iterate();
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package com.list;
public class Node {
private String data;
private Node next;
/**
* Lab 09: Stack adjustment for doubly-linked list
*/
private Node previous;
/**
* TO-DO
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* Adjustments required on: constructor, and accessors of 'previous' node
*/
public Node(String data) {
this.data = data;
this.next = null;
}
public Node(String data, Node next){
this.data = data;
this.next = next; }
/**
* @return data
*/
public String getData() {
return data;
}
/**
* @param data :the data to set
*/
public void setData(String data) {
this.data = data;
}
/**
* @return String of the data
*/
public String toString() {
return "Data: "+ data.toString();
}
/**
* @return the next
*/
public Node getNext() {
return next;
}
/**
* @param next :the next to set
*/
public void setNext(Node next) {
this.next = next;
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package com.list;
public class Stack {
private int size = 0;
private Node root = null;
//Lab 09: Stack double-linked list adjustment private Node tail = null;
/* * It has to return the size of the NodeList
*
* @return size
*/
public int size() {
return size;
}
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @param item
*/
// add an element to the stack
public void push(String item) {
Node oldfirst = root;
root = new Node(item, oldfirst);
size++;
}
/** * TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return item
*/
// delete and return the most recently added element
public Object pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
String item = root.getData(); // save item to return
root = root.getNext(); // delete first node
size--;
return item; // return the saved item
}
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return boolean
*/
// is the stack empty? public boolean isEmpty() { return root == null; }
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return
*/
/**
* Start with the head and traverse till you reach null.
*/
public void iterate(){
System.out.println("Iterate forward..."); Node
current = root; while(current!=null){ System.out.println(current.toString()); current = current.getNext(); }
}
}
Explanation / Answer
Hi, I have made necessary changes. Please test it.
import java.util.Scanner;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
Main mainClass = new Main();
Stack list = new Stack();
System.out.print("Enter hero1: ");
String hero1 = input.next();
System.out.print("Enter hero2: ");
String hero2 = input.next();
/** * TO-DO:
* Lab 09: Use scanner class to read the hero names,
* and assign those names to two Strings above.
*/
list.push(hero1);
list.push(hero2);
System.out.println("Length : "+list.size());
list.iterate();
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
class Node {
private String data;
private Node next;
/**
* Lab 09: Stack adjustment for doubly-linked list
*/
private Node previous;
/**
* TO-DO
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* Adjustments required on: constructor, and accessors of 'previous' node
*/
public Node(String data) {
this.data = data;
this.next = null;
}
public Node(String data, Node next){
this.data = data;
this.next = next;
}
/**
* @return data
*/
public String getData() {
return data;
}
/**
* @param data :the data to set
*/
public void setData(String data) {
this.data = data;
}
/**
* @return String of the data
*/
@Override
public String toString() {
return "Data: "+ data.toString();
}
/**
* @return the next
*/
public Node getNext() {
return next;
}
/**
* @param next :the next to set
*/
public void setNext(Node next) {
this.next = next;
}
/**
* @return the previous
*/
public Node getPrevious() {
return previous;
}
/**
* @param previous the previous to set
*/
public void setPrevious(Node previous) {
this.previous = previous;
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
class Stack {
private int size = 0;
private Node root = null;
//Lab 09: Stack double-linked list adjustment private Node tail = null;
/* * It has to return the size of the NodeList
*
* @return size
*/
public int size() {
return size;
}
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @param item
*/
// add an element to the stack
public void push(String item) {
Node oldfirst = root;
root = new Node(item, oldfirst);
if(oldfirst != null)
oldfirst.setPrevious(root);
size++;
}
/** * TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return item
*/
// delete and return the most recently added element
public Object pop() {
if (isEmpty()) throw new RuntimeException("Stack underflow");
String item = root.getData(); // save item to return
root = root.getNext(); // delete first node
root.setPrevious(null); // setting previous of new root node to null
size--;
return item; // return the saved item
}
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return boolean
*/
// is the stack empty?
public boolean isEmpty() { return root == null; }
/**
* TO-DO:
* Lab 09: Made adjustments to make the stack as a doubly-linked list
* @return
*/
/**
* Start with the head and traverse till you reach null.
*/
public void iterate(){
System.out.println("Iterate forward...");
Node current = root;
while(current!=null){
System.out.println(current.toString());
current = current.getNext();
}
}
}
/*
Sample run:
Enter hero1: Pinky
Enter hero2: Alex
Length : 2
Iterate forward...
Data: Alex
Data: Pinky
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.