Linear Data Structures(Queue)

Teknik Informatika - Universitas Muhammadiyah Malang (UMM)Tahun Akademik 2010-2011

Oleh : Nur Hayatin, S.ST

Sub Topik

• Queue• Operasi Queue• Implementasi Queue• Latihan

QUEUE(Antrian)

Definisi

• Urutan elemen yang mengikuti konsep FIFO.• FIFO(First In First Out)• Front menunjuk pada elemen yang paling

atas.• Rear menunjuk pada elemen yang paling

belakang.

Gambaran Proses

Front : DepanRear : Belakang

Queue (Antrian)

Front Rear

Queue (Antrian)

Front Rear

Queue (Antrian)

Front Rear

Queue (Antrian)

Front Rear

Queue (Antrian)

Front Rear

Queue (Antrian)

Front Rear

Operasi Queue

Operasi

• Enqueue/put (operasi penambahan elemen)

• Dequeue/remove (operasi penghapusan elemen)

• Get front (operasi pengaksesan elemen terdepan)

• Get rear(operasi pengaksesan elemen paling belakang)

Operasi Enqueue (add)

• Operasi penambahan elemen pada antrian.• Dilakukan pada rear.• Increment rear.

Operasi Dequeue (remove)

• Operasi penghapusan elemen pada antrian.• Untuk Queue array terjadi pergeseran elemen

dari belakang ke depan.• Dilakukan pada Front.• Decrement rear.

Operasi Get Front

• Pengambilan/pengaksesan elemen yang paling depan.

• Elemen yang ditunjuk oleh front.

Operasi Get Rear

• Pengambilan/pengaksesan elemen yang paling belakang.

• Elemen yang ditunjuk oleh rear.

Contoh Penerapan Queue

• mailbox dalam komunikasi antar proses• simulasi dan modeling (misalnya simulasi

sistem pengendali lalu lintas udara) dalam memprediksi performansi

• Waiting Line pada Sistem Operasi

QUEUE DENGAN CIRCULAR ARRAY

Circular Array

• Mampu melakukan proses penghapusan elemen tanda melakukan pergeseran.

Aturan Circular Array

1. Proses penghapusan dilakukan dengan cara nilai depan (front) ditambah 1 : depan=depan + 1.

2. Proses penambahan elemen sama dengan queue linear array yaitu nilai belakang ditambah 1 : belakang=belakang + 1.

3. Jika depan = maks dan ada elemen yang akan dihapus, maka nilai depan = 1.

4. Jika belakang = maks dan depan tidak 1 maka jika ada elemen yang akan ditambahkan, nilai belakang=1.

5. Jika hanya tinggal 1 elemen di queue (depan = belakang), dan akan dihapus maka depan diisi 0 dan belakang diisi dengan 0 (queue kosong).

Circular Array

Proses Circular Array

Proses Circular Array

Queue dalam Program

The Interface Queue

public interface Queue{ public boolean isEmpty(); public Object getFrontEelement(); public Object getRearEelement(); public void put(Object theObject); public Object remove();}

Class ArrayQueue

Inisialisasi Awal

public class ArrayQueue implements Queue{ int front=0; int rear=-1; Object [] queue;

Constructor

public ArrayQueue(int initialCapacity) { if (initialCapacity < 1) throw new IllegalArgumentException ("initialCapacity must be >= 1"); queue = new Object [initialCapacity + 1]; } public ArrayQueue() { this(10);

}

Method empty()

public boolean isEmpty() {

return rear == -1; }

Method getFront()

public Object getFrontElement() { if (isEmpty()) return null; else return queue[front]; }

Method getRear()

public Object getRearElement() { if (isEmpty()) return null; else return queue[rear]; }

Method put()

public void put(Object theElement) { if (rear == queue.length - 1) { Object [] newArray = new Object [2*queue.length]; System.arraycopy(queue, 0, newArray, 0, queue.length); queue = newArray; } queue[++rear] = theElement; }

Method remove()

public Object remove() { if (isEmpty()) return null; Object frontElement = queue[front]; for(int i = 1;i<=rear; i++)

queue[i-1] = queue[i]; --rear; return frontElement; }

Method main()public static void main(String [] args) { int x; ArrayQueue q = new ArrayQueue(3); q.put(new Integer(1)); q.put(new Integer(2)); q.put(new Integer(3)); q.put(new Integer(4)); q.remove(); q.remove(); q.put(new Integer(5)); q.put(new Integer(6)); q.put(new Integer(7)); q.put(new Integer(8)); q.put(new Integer(9)); q.put(new Integer(10)); q.put(new Integer(11)); q.put(new Integer(12)); while (!q.isEmpty()) { System.out.println("Rear element is " + q.getRearElement()); System.out.println("Front element is " + q.getFrontElement()); System.out.println("Removed the element " + q.remove()); } } }

Class LinkedQueue

Class ChainNodeclass ChainNode{ // package visible data members Object element; ChainNode next;

// package visible constructors ChainNode() {} ChainNode(Object element) {this.element = element;}

ChainNode(Object element, ChainNode next) {this.element = element; this.next = next;}}

Inisialisasi Awal

public class LinkedQueue implements Queue{ protected ChainNode front; protected ChainNode rear;

Method isEmpty()

public boolean isEmpty() {

return front == null; }

Method getFront()

public Object getFrontElement() { if (isEmpty()) return null; else return front.element; }

Method getRear()

public Object getRearElement() { if (isEmpty()) return null; else return rear.element; }

Method put()

public void put(Object theElement) { ChainNode p = new ChainNode(theElement, null); if (front == null) front = p; // empty queue else rear.next = p; // nonempty queue rear = p; }

Method remove()

public Object remove() { if (isEmpty()) return null; Object frontElement = front.element; front = front.next; if (isEmpty()) rear = null; // enable garbage collection return frontElement; }

Method main()public static void main(String [] args) { int x; LinkedQueue q = new LinkedQueue(3); q.put(new Integer(1)); q.put(new Integer(2)); q.put(new Integer(3)); q.put(new Integer(4)); while (!q.isEmpty()) { System.out.println("Rear element is " + q.getRearElement()); System.out.println("Front element is " + q.getFrontElement()); System.out.println("Removed the element " + q.remove()); } } }

Class CircularQueue

Inisialisasi Awal

class CircularQueue{

private int maxSize;private int[] queArray;private int front;private int rear;private int nItems;

Constructor

public CircularQueue(int s){

maxSize = s;queArray = new int[maxSize];front = 0;rear = -1;nItems = 0;

}

Method isEmpty()

public boolean isEmpty(){

return (nItems==0);

}

Method peekFront()

public int peekFront(){

return queArray[front];

}

Method insert()

public void insert(int j){

if(rear == maxSize-1)rear = -1;

queArray[++rear] = j; nItems++;

}

Method remove()

public int remove(){

int temp = queArray[front++]; if(front == maxSize)front = 0;nItems--; return temp;

}

Method main()public static void main(String[] args){

CircularQueue theQueue = new CircularQueue(5); // queue holds 5 itemsSystem.out.println("front : " + theQueue.front + "rear : " + theQueue.rear);theQueue.insert(10); theQueue.insert(20);theQueue.insert(30); theQueue.insert(40);theQueue.remove(); System.out.println(“remove 1x, front : " +theQueue.front +" rear : " +theQueue.rear);theQueue.insert(50); theQueue.insert(60); System.out.println("add 2 elemen, front : " +theQueue.front+"rear:”+theQueue.rear);theQueue.remove();System.out.println(“remove 1x, front : " +theQueue.front+ “rear : " +theQueue.rear);while( !theQueue.isEmpty() ) {

int n = theQueue.remove();System.out.print(n);System.out.print(" ");

}

Pustaka

• Sartaj Sahni, Presentation L5 & L10• Jokonowo, Bambang S.Si, “Pemrograman Berorientasi

Obyek”, Pusat pengembangan bahan ajar UMB, 2006.• Noviyanto, “Pemrograman Berorientasi Obyek (PBO) – Array”,

2005• Nugroho, Adi, “Algoritma dan Struktur Data Dalam Bahasa

Java”, ANDI Yogyakarta, 2008.• Michaell Waite, ”Data Structures and Algorithms in Java”,

SAMS, 2001