Write the construction and five basic functions for the STACK listed below by us
ID: 3600431 • Letter: W
Question
Write the construction and five basic functions for the STACK listed below by using 2D array to simulate Linked List approach. Details for each function:
Construction( ): construct an empty 2D array with capacity of 26 to simulate the OS.
1.Empty( ): test if the STACK is empty
2.Push(element): Add a value at the top of the stack of the 2D array.
3.Top( ): Read the value at the top of the stack
4.Pop( ): Remove the value at the top of the stack
5.Display( ): Displays all the elements in the stack using from Top to Bottom ordering. (Show array index, data value, and next array index)
After you finished the six functions, create an empty stack (with capacity=26) and then start push 10 values (1,2,3,4,5,6,7,8,9,10) by Push( ) consecutively. After that, you will have 10 elements in your STACK. Run Display ( ) to print out the STACK. Then perform 3 times of Push( ) of value (20,30,40) on valid positions, run Display( ) to print out the list every time you insert a new element. Then perform 3 times of Top() and Pop( ), again, run Display( ) to print our the list every time you delete an element.
To visualize the requirement, the code should looks like:
Push(1)
Push(2)
Push(3)
Push(4)
Push(5)
Push(6)
Push(7)
Push(8)
Push(9)
Push(10)
Display()
Push(20)
Display()
Push(30)
Display()
Push(40)
Display()
Top()
Pop()
Display()
Top()
Pop()
Display()
Top()
Pop()
Display()
Explanation / Answer
Please find my implementation.
#########
//***************************************************************
//LinkedStack.java
//
//A linked implementation of an Object stack class with operations push,
//pop, and isEmpty and isFull.
//
//***************************************************************
public class LinkedStack
{
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();
}
}
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;
}
public Object top() {
// TODO Auto-generated method stub
if(top == null)
return null;
return top;
}
public int size() {
int count = 0;
Node temp = top;
while(temp != null){
count++;
temp = temp.getNext();
}
return count;
}
public void display() {
Node t = top;
while(t != null) {
System.out.print(t.data+" ");
t = t.next;
}
System.out.println();
}
}
###########
public class TestStack
{
public static void main(String[] args)
{
LinkedStack stack = new LinkedStack ();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.push(9);
stack.push(10);
stack.display();
stack.push(20);
stack.display();
stack.push(30);
stack.display();
stack.push(40);
stack.display();
System.out.println(stack.top());
stack.display();
System.out.println(stack.top());
System.out.println(stack.pop());
stack.display();
System.out.println(stack.top());
System.out.println(stack.pop());
stack.display();
}
}
/*
Sample run:
10 9 8 7 6 5 4 3 2 1
20 10 9 8 7 6 5 4 3 2 1
30 20 10 9 8 7 6 5 4 3 2 1
40 30 20 10 9 8 7 6 5 4 3 2 1
40
40 30 20 10 9 8 7 6 5 4 3 2 1
40
40
30 20 10 9 8 7 6 5 4 3 2 1
30
30
20 10 9 8 7 6 5 4 3 2 1
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.