Java has a Stack class that holds elements of type Object. However, many languag
ID: 3829023 • Letter: J
Question
Java has a Stack class that holds elements of type Object. However, many languages do not provide stack types,
so it is useful to be able to define your own. File StackADT contains an interface representing the ADT for
a stack of objects and LinkedStack contains a skeleton for a class that uses a linked list to implement this
interface. It depends on the Node class in Node. (This could also be defined as an inner class.) Fill in code
for the following public methods:
- void push(Object val)
- int pop()
- boolean isEmpty()
- boolean isFull()
In writing your methods, keep in mind that in a linked implementation of a stack, the top of stack is always at
the front of the list. This makes it easy to add (push) and remove (pop) elements.
File StackTest contains a simple driver to test your stack. Save it to your directory, compile it, and make
sure it works.
Deliverables:
StackADT.java
LinkedStack.java
Node.java
StackTest.java
Explanation / Answer
Please find my implementation.
Please let me know in case of any issue.
######## Node.java #############
public class Node {
private Object data;
private Node next;
public Node(Object d) {
data = d;
next = null;
}
public Object getData() {
return data;
}
public Node getNext() {
return next;
}
public void setData(Object data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return data.toString();
}
}
##############
/**
* Defines the interface to a stack collection.
*
* @author Java Foundations
* @version 4.0
*/
public interface StackADT<T>
{
/**
* Adds the specified element to the top of this stack.
* @param element element to be pushed onto the stack
*/
public void push(T element);
/**
* Removes and returns the top element from this stack.
* @return the element removed from the stack
*/
public T pop();
/**
* Returns without removing the top element of this stack.
* @return the element on top of the stack
*/
public T peek();
/**
* Returns true if this stack contains no elements.
* @return true if the stack is empty
*/
public boolean isEmpty();
/**
* Returns the number of elements in this stack.
* @return the number of elements in the stack
*/
public int size();
/**
* Returns a string representation of this stack.
* @return a string representation of the stack
*/
public String toString();
}
###############
//***************************************************************
//LinkedStack.java
//
//A linked implementation of an Object stack class with operations push,
//pop, and isEmpty and isFull.
//
//***************************************************************
public class LinkedStack implements StackADT
{
private Node top; // reference to top of stack
// ---------------------------------------------------
// Constructor -- initializes top
// ---------------------------------------------------
public LinkedStack()
{
top = null;
}
// ---------------------------------------------------
// Adds element to top of stack if it's not full, else
// does nothing.
// ---------------------------------------------------
public void push(Object val)
{
Node newNode = new Node(val);
newNode.setNext(top);
top = newNode;
}
// ---------------------------------------------------
// Removes and returns value at top of stack. If stack
// is empty returns null.
// ---------------------------------------------------
public Object pop()
{
if(top == null)
return null;
Object item = top;
top = top.getNext();
return item;
}
// ---------------------------------------------------
// Returns true if stack is empty, false otherwise.
// ---------------------------------------------------
public boolean isEmpty()
{
return top==null;
}
// ---------------------------------------------------
// Returns true if stack is full, false otherwise.
// ---------------------------------------------------
public boolean isFull()
{
return false;
}
@Override
public Object peek() {
// TODO Auto-generated method stub
if(top == null)
return null;
return top;
}
@Override
public int size() {
int count = 0;
Node temp = top;
while(temp != null){
count++;
temp = temp.getNext();
}
return count;
}
}
#############
//*******************************************************
//StackTest.java
//
//A simple driver that exercises push, pop, isFull and isEmpty.
//Thanks to autoboxing, we can push integers onto a stack of Objects.
//
//*******************************************************
public class StackTest
{
public static void main(String[] args)
{
StackADT stack = new LinkedStack ();
//push some stuff on the stack
for (int i=0; i<10; i++)
stack.push(i*2);
//pop and print
//should print 18 16 14 12 10 8 6 4 2 0
while (!stack.isEmpty())
System.out.print(stack.pop() + " ");
System.out.println();
//push a few more things
for (int i=1; i<=6; i++)
stack.push(i);
//should print 6 5 4 3 2 1
while (!stack.isEmpty())
System.out.print(stack.pop() + " ");
System.out.println();
}
}
/*
Sample run:
18 16 14 12 10 8 6 4 2 0
6 5 4 3 2 1
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.