JAVA Stacks Data Structures | Stack Implementation Create a class called ArrayBa
ID: 3863483 • Letter: J
Question
JAVA Stacks
Data Structures | Stack
Implementation
Create a class called ArrayBasedStack. Declare the following variables:
• data: references an array storing elements in the list
• topOfStack: an int value representing the location of the stack top in the array
• INITIAL_CAPACITY: the default capacity of the stack
public class ArrayBasedStack <E> {
private E[] data;
private int topOfStack;
private static final int INITIAL_CAPACITY = 5;
}
Add a constructor that will initialize the stack with a user-defined initial capacity. The top of the stack
will be assigned a value of -1 to indicate that the stack is currently empty.
public ArrayBasedStack(int capacity) {
data = (E[]) new Object[capacity];
____________ = -1;
}
Another constructor takes no parameters and sets the capacity of the data array to the default value:
public ArrayBasedStack() {
this(INITIAL_CAPACITY);
}
Add a method that will expand the array when necessary. The method is very similar to that in the
ArrayBasedList activity. To reduce the amount of code to 1 line, you could also use the copyOf method in
java.util.Arrays.
private void expand(int amount) {
E[] temp = (E[]) new Object[data.length + amount];
for (int i = 0; i <= topOfStack; i++) {
temp[i] = data[i];
}
data = temp;
}
Add a method called push that will add an element to the top of the stack:
public void push(E newElement) {
}
Data Structures Stacks
Data Structures | Stack 5
• If the array is full, increase the length of the array by the following amount (approximately 65%
of its current size):
if (topOfStack == data.length - 1) {
expand((data.length * 3) / 2 + 1);
}
• Increase the top of the stack to point to the new element and insert the new element into the stack:
topOfStack++;
data[topOfStack] = newElement;
Create a new ArrayBasedStack in interactions and open a viewer on the stack object. Answer the
following questions and use the viewer to verify your answers:
• What will be the value of topOfStack after each line of code is executed?
• How many times will the internal array expand? What will its size be after each expansion?
ArrayBasedStack stack = new ArrayBasedStack(3);
stack.push(3);
stack.push(6);
stack.push(4);
stack.push(8);
The isEmpty method will return whether the stack has elements. If the top of the stack is less than 0 then
there are no elements currently in the stack:
public boolean isEmpty() {
return __________ < 0;
}
The pop method will remove the last element that was added to the stack.
public E pop() {
}
• If stack is empty, throw an EmptyStackException. Import the EmptyStackException class which
is in the java.util package.
if (isEmpty()) {
Data Structures Stacks
Data Structures | Stack 6
// stack underflow
throw new EmptyStackException();
}
• If there are elements, get the element at the end of the stack (index is topOfStack) and decrement
the index of the top of the stack. Set the previous top of the stack to null.
E returnObj = data[__________];
data[topOfStack] = null;
• Decrement the index of the top of the stack and return the previous top.
topOfStack--;
return __________;
Run the following in interactions with a viewer open on the stack object. Answer the following questions
and then use the viewer to verify your answers:
• What will the stack look like after invoking the push operation on String objects "1st", "2nd", and
"3rd"?
• What would a pop operation return at this point? What would a second pop operation return?
ArrayBasedStack stack = new ArrayBasedStack(3);
stack.isEmpty()
true
stack.push("1st");
stack.isEmpty()
false
stack.push("2nd");
stack.push("3rd");
stack.pop()
3rd
stack.pop()
2nd
stack.push("4th");
stack.pop()
4th
stack.pop()
1st
stack.isEmpty()
true
If you had used a linked list implementation of the stack, how would your stack differ from the
array implementation?
Add a method called peek that will return the top of the stack but will not remove the element from the
stack.
public E peek() {
Data Structures Stacks
Data Structures | Stack 7
}
• If the stack is empty, throw an exception.
if (isEmpty()) {
throw new EmptyStackException();
}
• Otherwise, return the element at the top of the stack.
return data[__________];
Test your class as follows in the interactions pane. Answer the following questions and verify your
answers using the viewer:
• At what point is the internal array expanded, if at all?
• What are the contents of the stack before the push operation is performed on object "o"?
ArrayBasedStack stack = new ArrayBasedStack(3);
stack.isEmpty()
true
stack.push("b");
stack.push("e");
stack.peek()
e
stack.pop()
e
stack.peek()
b
stack.pop()
b
stack.push("o");
stack.pop()
o
stack.isEmpty()
true
stack.pop()
Exception in evaluation thread java.util.EmptyStackException
Deliverables:
Implement a stack using a linked implementation. First, implement the SinglyLinkedNode class
from the activity on singly linked list. Use the following hints to create your stack and use the same
operations in the interactions pane from the array-based version to test your stack's functionality.
import java.util.EmptyStackException;
public class LinkedStack<E> {
private SinglyLinkedNode<E> topNode = null;
Data Structures Stacks
Data Structures | Stack 8
public void push(E newElement) {
// create a node that holds the new element
// set the next node reference of the new node to the current top
// set the top node to reference the new element
}
public boolean isEmpty() {
// empty if the topNode is null
}
public E pop() {
// throw an exception if stack is empty
// store data from current top node (type E)
// set the top node to reference the next node in the stack
// return the stored data
}
public E peek() {
// throw an exception if stack is empty
// return the data from the top node
}
}
Submit both the ArrayBasedStack class and the LinkedStack class implementations
Explanation / Answer
//============================ ArrayBasedStack.java ===================//
public class ArrayBasedStack<E>{
protected int capacity;
public static final int INITIAL_CAPACITY = 5;
protected E[] stackRep;
protected int top = -1;
public ArrayBasedStack() {
this(INITIAL_CAPACITY); // default capacity
}
public ArrayBasedStack(int capacity) {
this.capacity = capacity;
stackRep = (E[])new Object[capacity];
}
public int size() {
return (top + 1);
}
public boolean isEmpty() {
return (top < 0);
}
public void push(E newElement) throws Exception {
if (size() == capacity)
expand((stackRep.length * 3) / 2 + 1);
stackRep[++top] = newElement;
}
private void expand(int amount ) {
int length = size();
E[] newstack=(E[])new Object[length+amount];
System.arraycopy(stackRep,0,newstack,0,length);
stackRep=newstack;
}
public E top() throws Exception {
if (isEmpty())
throw new Exception("Stack is empty.");
return stackRep[top];
}
public E pop() throws Exception {
E data;
if (isEmpty())
throw new Exception("Stack is empty.");
data = stackRep[top];
stackRep[top--] = null;
return data;
}
public String toString() {
String s;
s = "[";
if (size() > 0)
s += stackRep[0];
if (size() > 1)
for (int i = 1; i <= size() - 1; i++) {
s += ", " + stackRep[i];
}
return s + "]";
}
}
//============================ LinkedStack.java ===================//
package Stack;
import java.util.EmptyStackException;
public class LinkedStack<E>{
private int length;
private StackNode<E> top;
public LinkedStack() {
length = 0;
top = null;
}
public void push (E data) {
StackNode<E> temp = new StackNode<E> (data);
temp.setNext(top);
top = temp;
length++;
}
public E pop() throws EmptyStackException{
if (isEmpty())
throw new EmptyStackException();
E result = top.getData();
top = top.getNext();
length--;
return result;
}
public E peek() throws EmptyStackException{
if (isEmpty())
throw new EmptyStackException();
return top.getData();
}
public boolean isEmpty(){
return (length == 0);
}
public int size(){
return length;
}
public String toString(){
String result = "";
StackNode<E> current = top;
while (current != null){
result = result + current.toString() + " ";
current = current.getNext();
}
return result;
}
}
//================================= StackNode.java ================================//
package Stack;
public class StackNode<E>{
public StackNode<E> next;
public E data;
public StackNode(){
next = null;
data = null;
}
public StackNode (E data){
next = null;
this.data = data;
}
public StackNode<E> getNext(){
return next;
}
public void setNext (StackNode<E> node){
next = node;
}
public E getData(){
return data;
}
public void setdata (E elem){
data = elem;
}
public String toString (){
return data.toString();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.