In: Computer Science
In the Stack Module I gave you a project that shows how to create a Stack using doubly linked nodes.
StackWithDoublyLinkedNodes.zip
It is a template class that needs the Node class. You must use this same Node class (no alterations) to create a Queue class .
public class Queue <T>{
}
Use the NetBeans project above as an example.
I have put a driver program (q1.java) in the module. Also here: q1.java This driver program should then run with your Queue class (no modifications allowed to the driver program).
Your Queue class should have at least the following methods: one or more constructors, enqueue, dequeue, peek, isEmpty, size, makeEmpty.
MUST INCLUDE:
Template Class
constructor
enqueue
dequeue
peek
isEmpty
size
makeEmpty
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Q1.java
public class Q1 {
public static void main(String[] args) {
Queue <String> myQ = new Queue<String>(); //string Q
String[] names = {"harry", "mary", "mosi", "sadie","tom", "janice"};
for (int i=0; i<names.length;i++)
myQ.enqueue(names[i]);
System.out.println("Size is " + myQ.getSize());
for (int i=0; i<6; i++)
System.out.println(myQ.dequeue()); //test that it also works for integers
Integer[]numbers={4,5,6,7,8,17,100};
Queue<Integer> myI = new Queue<Integer>(); //Integer Q
for (int i=0; i<numbers.length;i++)
myI.enqueue(numbers[i]);
System.out.println("Size is " + myI.getSize());
//Verify it adds (and is an integer Q) and doesn't concatenate(String Q)
int total=0;
int tempSize=myI.getSize();
System.out.println("Integers in Queue are:");
for (int i=0; i<tempSize; i++)
//cannot use getSize() here because it changes every time you dequeue
{Integer val = myI.dequeue();
System.out.print(val+ " ");
total=total+val;
}
System.out.println("\nTotal is:" + total);
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
StackWithDoublyLinkedNodes.java
public class StackWithDoublyLinkedNodes {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack<Integer> s = new Stack<Integer>();
Integer[] x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < x.length; i++) {
Integer t = x[i];
s.push(t);
}
while (!s.isEmpty()) {
System.out.println(s.pop());
}
//verify the stack is empty and that
//we took care of the issues
//of trying to pop an empty stack
//and peek at the top of an empty stack
System.out.println(s.pop());
System.out.println(s.peek());
System.out.println("********************************");
//repeat using a stack of Strings
System.out.println("Repeat using a Stack of Strings");
Stack<String> s1 = new Stack<String>();
String[] x1 = {"Hi", "Bye", "One", "Four","CMPSC"};
for (int i = 0; i < x1.length; i++) {
String t1 = x1[i];
s1.push(t1);
}
while (!s1.isEmpty()) {
System.out.println(s1.pop());
}
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Stack.java
public class Stack<T> {
private Node head;
private int size;
Stack() {
head = null;
size = 0;
}
public void push(T newItem) {
Node temp = new Node(newItem);
if (this.isEmpty()) {
head = temp;
} else {
temp.setNext(head);
head.setPrev(temp);
head = temp;
}
size++;
}
public T pop() {
if (isEmpty()) {
return (T)"Empty List";
}
T temp = (T) head.getItem();
head = head.getNext();
if (head != null) {
head.setPrev(null);
}
size--;
return temp;
}
public T peek() {
if(isEmpty()){
return (T)"Empty List";
}
return (T) head.getItem();
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Node.java
public class Node<T> {
//Node makes item, next, and prev all private
//and therefore has to provide accessors
//and mutators (gets and sets)
private T item;
private Node next;
private Node prev;
Node(T newItem) {
item = newItem;
next = null;
prev = null;
}
Node(T newItem, Node nextNode, Node prevNode) {
item = newItem;
next = nextNode;
prev = prevNode;
}
/**
* @return the item
*/
public T getItem() {
return item;
}
/**
* @param item the item to set
*/
public void setItem(T item) {
this.item = item;
}
/**
* @return the next
*/
public Node getNext() {
return next;
}
/**
* @param next the next to set
*/
public void setNext(Node next) {
this.next = next;
}
/**
* @return the prev
*/
public Node getPrev() {
return prev;
}
/**
* @param prev the prev to set
*/
public void setPrev(Node prev) {
this.prev = prev;
}
}
Lets see the answer :-
// Queue.java
public class Queue <T>{
private Node front; // reference to first node
private Node last; // reference to last node
private int size; // number of nodes in queue
// constructor to create an empty queue
public Queue()
{
front = null;
last = null;
size = 0;
}
// method to insert item at the end of queue
public void enqueue(T item)
{
// create a new node to store item
Node node = new Node(item);
if(isEmpty()) // empty queue
{
// set front and last node to node
front = node;
last = node;
}
else // insert at end
{
// set prev of node to last
node.setPrev(last);
// set next of last to node
last.setNext(node);
last = node; // update last to node
}
size++; // increment size of queue
}
// method to remove and return the front element of queue
public T dequeue()
{
if(isEmpty()) // empty queue, return dummy value
return (T) "Empty List";
else
{
Node node = front; // get the node at front
T data = (T)node.getItem();
front = front.getNext(); // set front to node next to front
if(front == null) // queue has become empty, set last to null
last = null;
else
front.setPrev(null); // if non-empty set prev of front to null
size--; // decrement size
node.setNext(null); // set next of node to null
return data; // return the front element
}
}
// method to return the front element
public T peek()
{
if(isEmpty()) // empty queue
return (T) "Empty list";
else // non-empty queue
return (T)front.getItem();
}
// method to return the number of elements in the queue
public int getSize()
{
return size;
}
// method to delete all the elements of the queue
public void makeEmpty()
{
// set front and last to null
front = null;
last = null;
size = 0; // set size to 0
}
// method to return true if queue is empty else return false
public boolean isEmpty()
{
return size == 0;
}
}
//end of Queue.java
// Q1.java
public class Q1 {
public static void main(String[] args) {
Queue <String> myQ = new Queue<String>(); //string Q
String[] names = {"harry", "mary", "mosi", "sadie","tom", "janice"};
for (int i=0; i<names.length;i++)
myQ.enqueue(names[i]);
System.out.println("Size is " + myQ.getSize());
for (int i=0; i<6; i++)
System.out.println(myQ.dequeue()); //test that it also works for integers
Integer[]numbers={4,5,6,7,8,17,100};
Queue<Integer> myI = new Queue<Integer>(); //Integer Q
for (int i=0; i<numbers.length;i++)
myI.enqueue(numbers[i]);
System.out.println("Size is " + myI.getSize());
//Verify it adds (and is an integer Q) and doesn't concatenate(String Q)
int total=0;
int tempSize=myI.getSize();
System.out.println("Integers in Queue are:");
for (int i=0; i<tempSize; i++)
//cannot use getSize() here because it changes every time you dequeue
{
Integer val = myI.dequeue();
System.out.print(val+ " ");
total=total+val;
}
System.out.println("\nTotal is:" + total);
}
}
// end of Q1.java