Small exercise Implement MyLinkedStack (constructor, push, pop, peek and isEmpty
ID: 3726111 • Letter: S
Question
Small exercise
Implement MyLinkedStack (constructor, push, pop, peek and isEmpty) and MyLinkedQueue using head,tail variables(constructor, offer, poll, peek and isEmpty), and write the following two program to test them.
For stack testing, write a program to check if a string has matching parenthesis such as “(())”, but not “)(“.
For stack testing, use it to “Evaluating Expressions”
Phase 1: Scanning the expression
The program scans the expression from left to right to extract operands, operators, and the parentheses.
1.1. If the extracted item is an operand, push it to operandStack.
1.2. If the extracted item is a + or - operator, process all the operators at the top of operatorStack and push the extracted operator to operatorStack.
1.3. If the extracted item is a * or / operator, process the * or / operators at the top of operatorStack and push the extracted operator to operatorStack.
1.4. If the extracted item is a ( symbol, push it to operatorStack.
1.5. If the extracted item is a ) symbol, repeatedly process the operators from the top of operatorStack until seeing the ( symbol on the stack.
Phase 2: Clearing the stack
Repeatedly process the operators from the top of operatorStack until operatorStack is empty.
Explanation / Answer
import java.util.EmptyStackException;
/**
* A class of stacks whose entries are stored in a chain of nodes.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
public final class LinkedStack<T> implements StackInterface<T> {
private Node topNode; // References the first node in the chain
public LinkedStack() {
topNode = null;
} // end default constructor
public void push(T newEntry) {
topNode = new Node(newEntry, topNode);
// Node newNode = new Node(newEntry, topNode);
// topNode = newNode;
} // end push
public T peek() {
if (isEmpty())
throw new EmptyStackException();
else
return topNode.getData();
} // end peek
public T pop() {
T top = peek(); // Might throw EmptyStackException
assert (topNode != null);
topNode = topNode.getNextNode();
return top;
} // end pop
/*
* // Question 1, Chapter 6: Does not call peek public T pop() { if
* (isEmpty()) throw new EmptyStackException(); else { assert (topNode !=
* null); top = topNode.getData(); topNode = topNode.getNextNode(); } // end
* if
*
* return top; } // end pop
*/
public boolean isEmpty() {
return topNode == null;
} // end isEmpty
public void clear() {
topNode = null; // Causes deallocation of nodes in the chain
} // end clear
public void displayUtil(Node topNode){
if(topNode==null)
return;
displayUtil(topNode.getNextNode());
System.out.print(topNode.getData() + " ");
}
public void display() {
// YOUR CODE HERE!
if(isEmpty())
System.out.println("The stack is empty.");
else{
System.out.print("BOTTOM ");
displayUtil(topNode);
System.out.print("TOP");
}
}
private class Node {
private T data; // Entry in stack
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node linkPortion) {
data = dataPortion;
next = linkPortion;
} // end constructor
private T getData() {
return data;
} // end getData
private void setData(T newData) {
data = newData;
} // end setData
private Node getNextNode() {
return next;
} // end getNextNode
private void setNextNode(Node nextNode) {
next = nextNode;
} // end setNextNode
} // end Node
} // end LinkedStack
========================================================================================
//interface QueueInterface {
// public void enqueue(Object item);
//
// // Effect: Adds item to the rear of this queue.
// // Precondition: This queue is not full.
// // Postcondition: item is at the rear of this queue.
// public Object dequeue();
//
// // Effect: Removes front element from this queue and returns it.
// // Precondition: This queue is not empty.
// // Postconditions: Front element has been removed from this queue.
// // Return value = (the removed element)
// public boolean isEmpty();
//
// // Effect: Determines whether this queue is empty.
// // Postcondition: Return value = (this queue is empty)
// public boolean isFull();
// // Effect: Determines whether this queue is full.
// // Postcondition: Return value = (queue is full)
// public int size();
//}
public class LinkedQueue {
private class QueueNode
// Used to hold references to queue nodes for the linked queue
// implementation
{
private String info;
private QueueNode link;
}
private QueueNode front; // reference to the front of this queue
private QueueNode rear; // reference to the rear of this queue
public LinkedQueue()
// Constructor
{
front = null;
rear = null;
}
public void enqueue(String item)
// Adds item to the rear of this queue.
{
QueueNode newNode = new QueueNode();
newNode.info = item;
newNode.link = null;
if (rear == null)
front = newNode;
else
rear.link = newNode;
rear = newNode;
}
public Object dequeue()
// Removes front element from this queue and returns it.
{
Object item;
item = front.info;
front = front.link;
if (front == null)
rear = null;
return item;
}
public boolean isEmpty()
// Determines whether this queue is empty.
{
if (front == null)
return true;
else
return false;
}
public String peek()
// Determines whether this queue is empty.
{
if (front == null)
return null;
else
return front.info;
}
public int size()
// Determines whether this queue is empty.
{
QueueNode curr = front;
int count = 0;
while (curr != null) {
++count;
curr = curr.link;
}
return count;
}
public String toString()
// Determines whether this queue is empty.
{
QueueNode curr = front;
String res = "";
while (curr != null) {
res = res + curr.info + " ";
curr = curr.link;
}
return res;
}
public static void main(String args[]) {
LinkedQueue queue = new LinkedQueue();
queue.enqueue("dog");
queue.enqueue("cat");
queue.enqueue("mouse");
queue.enqueue("pig");
queue.enqueue("bird");
System.out.println(queue.toString());
System.out.println("Queue Size: " + queue.size());
queue.enqueue("puppy");
System.out.println(queue.toString());
System.out.println("Queue Size: " + queue.size());
queue.dequeue();
queue.dequeue();
System.out.println("Queue Size: " + queue.size());
queue.dequeue();
System.out.println(queue.peek());
queue.dequeue();
queue.dequeue();
System.out.println("Queue Size: " + queue.size());
System.out.println("Queue IsEmpty: " + queue.isEmpty());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.