3.21 Lab 2: Queue using Linked List

Implement Queue using Linked List A queue works in a first-in-first-out fashion (see sections 3.15 and 3.16 for details). You will implement the following methods using Linked List methods made available to you:

• public void enqueue( ) which adds an element at the end of the queue.
• public int dequeue( ) which removes the first element from the queue and returns it.
• public int peek( ) which returns the first element without removing it from the queue.

///////////////////////////// Node Class

public class Node{ int data; Node next; public Node(int data){ this.data = data; next = null; } }

// end

///////////////////// QueueList class

import java.util.Scanner;

public class QueueList { LinkedListBasic queueList = new LinkedListBasic();

// Adds new elements to the end of the queue public void enqueue(int data) { // Complete this method }

// Removes the front element from the queue public void dequeue() { // Complete this method } // returns the front element of the queue but does not remove it. public int peek() { // Complete this method }

public void print() { queueList.print(); }

public static void main(String[] args) { QueueList queue = new QueueList(); Scanner input = new Scanner(System.in); while (true) { int data = input.nextInt(); if (data == -1) break; queue.enqueue(data); }

// printing queue elements System.out.println("Queue elements:"); queue.print(); // printing the value peek returns int peek_item = queue.peek(); System.out.printf("%nPeek returns: %d%n", peek_item); // printing queue elements after pop queue.dequeue(); queue.dequeue(); System.out.println(" After popping twice:"); queue.print(); }

}

// end

/////////////////////// LinkedListBasic class

import java.util.Scanner;

public class LinkedListBasic { Node head; Node tail; // inserts data to the end of the list only using the head pointer public void append(int data){ if(head == null){ Node newNode = new Node(data); head = newNode;

} else { Node newNode = new Node(data); Node currentNode = head; while(currentNode.next != null){ currentNode = currentNode.next; } currentNode.next = newNode; } } // inserts data to the beginning of the list public void prepend(int data){ if(head == null){ Node newNode = new Node(data); head = newNode; return; } Node newNode = new Node(data); newNode.next = head; head = newNode; } // insert a new data after the given one public void insertAfter(int givenData, int newData){ if(head == null){ Node newNode = new Node(newData); head = newNode; return; } else{ Node currentNode = head; while(currentNode.next != null){ if(currentNode.data == givenData){ Node newNode = new Node(newData); newNode.next = currentNode.next; currentNode.next = newNode; } } } } // check if the list is empty public boolean isEmpty(){ return (head == null); } // prints the list public void print(){ if(isEmpty()){ System.out.println("Empty."); } Node currentNode = head; while(currentNode != null){ System.out.printf("%d ", currentNode.data); currentNode = currentNode.next; } } public Node removeFirst(){ Node first = head; head = head.next; return first; } public void removeLast(){ if(head == null){ return; } Node current = head; while(current.next.next != null){ current = current.next; } current.next = null; } }