Queue Using Linked List
A. Pengertian
Struktur data queue (antrian) dapat diimplementasikan dengan menggunakan array maupun linked list sebagai penyimpanan datanya. Dalam contoh program berikut ini saya gunakan double linked list untuk implementasi queue. Secara umum, operasi dalam queue ada 2 yang utama yaitu enqueue dan dequeue. Enqueue berarti memasukkan item baru ke dalam antrian. Sedangkan dequeue untuk mengeluarkan item dari antrian. Queue bersifat FIFO, First In First Out. Item yang pertama kali masuk akan menjadi yang pertama keluar. Pintu masuk dan pintu keluar queue ada sendiri-sendiri. Berbeda dengan stack yang hanya ada satu. Item baru akan masuk dari pintu belakang (rear), sedangkan data keluar dari pintu depan (front). Berikut adalah contoh programnya.
B. Contoh Program Queue Linked List
1. Kode Program
import java.util.*;
class Node
{
protected int data;
protected Node link;
public Node()
{
link = null;
data = 0;
}
public Node(int d, Node n)
{
data = d;
link = n;
}
public void setLink(Node n)
{
link = n;
}
// Function to set data to current Node
public void setData(int d)
{
data = d;
}
// Function to get link to next node
public Node getLink()
{
return link;
}
// Function to get data from current Node
public int getData()
{
return data;
}
}
class linkedQueue
{
protected Node front, rear;
public int size;
public linkedQueue()
{
front = null;
rear = null;
size = 0;
}
// Function to check if queue is empty
public boolean isEmpty()
{
return front == null;
}
// Function to get the size of the queue
public int getSize()
{
return size;
}
// Function to insert an element to the queue
public void insert(int data)
{
Node nptr = new Node(data, null);
if (rear == null)
{
front = nptr;
rear = nptr;
}
else
{
rear.setLink(nptr);
rear = rear.getLink();
}
size++;
}
// Function to remove front element from the queue
public int remove()
{
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
Node ptr = front;
front = ptr.getLink();
if (front == null)
rear = null;
size--;
return ptr.getData();
}
// Function to check the front element of the queue
public int peek()
{
if (isEmpty())
throw new NoSuchElementException("Underflow Exception");
return front.getData();
}
// Function to display the status of the queue
public void display()
{
System.out.print("\nQueue = ");
if (size == 0)
{
System.out.print("Empty\n");
return;
}
Node ptr = front;
while (ptr != rear.getLink())
{
System.out.print(ptr.getData() + " ");
ptr = ptr.getLink();
}
System.out.println();
}
}
class LinkedQueueImplement
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
linkedQueue lq = new linkedQueue();
System.out.println("Linked Queue Test\n");
char ch;
System.out.println("\nQueue Operations");
System.out.println("1. Insert");
System.out.println("2. Remove");
System.out.println("3. Peek");
System.out.println("4. Check empty");
System.out.println("5. Size");
do
{
System.out.print("Enter choice : ");
int choice = scan.nextInt();
switch (choice)
{
case 1:
System.out.print("Enter integer element to insert : ");
lq.insert(scan.nextInt());
break;
case 2:
try
{
System.out.println("Removed Element = " + lq.remove());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 3:
try
{
System.out.println("Peek Element = " + lq.peek());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 4:
System.out.println("Empty status = " + lq.isEmpty());
break;
case 5:
System.out.println("Size = " + lq.getSize());
break;
default:
System.out.println("Wrong Entry \n ");
break;
}
// display queue
lq.display();
System.out.print("\nDo you want to continue (Type y or n) : ");
ch = scan.next().charAt(0);
}
while (ch == 'Y' || ch == 'y');
}
}
2. Hasil output program
Linked Queue Test
Queue Operations
1. Insert
2. Remove
3. Peek
4. Check empty
5. Size
Enter choice : 1
Enter integer element to insert : 25
Queue = 25
Do you want to continue (Type y or n) : y
Enter choice : 1
Enter integer element to insert : 36
Queue = 25 36
Do you want to continue (Type y or n) : y
Enter choice : 1
Enter integer element to insert : 98
Queue = 25 36 98
Do you want to continue (Type y or n) : y
Enter choice : 2
Removed Element = 25
Queue = 36 98
Do you want to continue (Type y or n) : y
Enter choice : 3
Peek Element = 36
Queue = 36 98
Do you want to continue (Type y or n) : y
Enter choice : 4
Empty status = false
Queue = 36 98
Do you want to continue (Type y or n) : y
Enter choice : 5
Size = 2
Queue = 36 98
Do you want to continue (Type y or n) : n
C. Hasil Screenshoot
1. Kode Program
2. Screenshoot Hasil Output
