Stack
- Struktur data yang aksesnya terbatas pada item yang paling sering dimasukkan
- Stack dikenal juga sebagai tumpukan
- Tumpukan piring
- Tumpukan majalah
- Item yang dimasukkan paling akhir yang akan diambil pertama kali
- Pengambilan hanya diijinkan pada item teratas saja
- Item setelahnya dan paling bawah tidak dapat langsung diambil
Operasi Dasar
- Menambah data
- push
- Menghapus data
- pop
- Melihat data
- top
Protokol Dasar
package org.benynasution.sd.stack;
public interface Stack <AnyType>{
void push(AnyType data);//menambah data
void pop();//menghapus data
AnyType top();//melihat data teratas
AnyType topAndPop();//melihat data teratas
//kemudian menghapus
boolean isEmpty();//memeriksa apakah stack kosong
void makeEmpty();//mengkosongkan stack
}
StackKita
- Pembuatan struktur data stack sendiri yang diberi nama StackKita
- StackKita mengimplementasi interface Stack pada package org.benynasution.sd.stack
Class StackKita
package org.benynasution.sd.stack;
public class StackKita<AnyType> implements Stack<AnyType> {
private static final int KAPASITAS_DEFAULT = 10;
private AnyType[] arraykita;
private int teratas;
public StackKita(){
arraykita = (AnyType[]) new Object[KAPASITAS_DEFAULT];
teratas = -1;
}
public void push(AnyType data) {
if(teratas+1 == arraykita.length){
System.out.println("stack penuh, keluar dari aplikasi");
System.exit(1);
}
arraykita[++teratas] = data;
}
public void pop() {
if(isEmpty()){
System.out.println("stack kosong, keluar dari aplikasi");
System.exit(1);
}
teratas--;
}
public AnyType top() {
if(isEmpty()){
System.out.println("stack kosong, keluar dari aplikasi");
System.exit(1);
}
return arraykita[teratas];
}
public AnyType topAndPop() {
if(isEmpty()){
System.out.println("stack kosong, keluar dari aplikasi");
System.exit(1);
}
return arraykita[teratas--];
}
public boolean isEmpty() {
return teratas == -1;
}
public void makeEmpty() {
teratas = -1;
}
}
Class UjiStackKita
package org.benynasution.uji;
import org.benynasution.sd.stack.StackKita;
public class UjiStackKita {
public static void main(String args[]){
StackKita<Integer> uji = new StackKita<Integer>();
uji.push(1); //tambah 1
System.out.println(uji.top()); //1
uji.push(2); //tambah 2
System.out.println(uji.top()); //2
uji.push(3); //tambah 3
uji.push(4); //tambah 4
System.out.println(uji.top()); //4
uji.pop(); //hapus 4
System.out.println(uji.top()); //3
System.out.println(uji.topAndPop()); //3
System.out.println(uji.top()); //2
uji.pop(); //hapus 2
uji.pop(); //hapus 1
uji.pop(); //error
}
}
- Struktur data sederhana lainnya adalah Queue
- Memiliki batasan akses terhadap item yang dimasukkan terlebih dahulu untuk diproses
- Pada beberapa kasus, mampu melakukan pencarian dan/atau menghapus item yang sering dimasukkan
- Seringkali kurang tepat diaplikasikan
- Pada sistem multiprocessing, item yang lebih dahulu datang akan diproses awal
· Contohnya pada job printer
· Pertama masuk antrian yang akan diproses
· Menghindari item yang paling awal menunggu selamanya untuk diproses
- Enqueue
- Memasukkan data pada sisi belakang antrian
- Dequeue
- Menghapus data pada sisi depan antrian
- getFront
- Mengakses data pada sisi depan antrian
Protokol Dasar
package org.benynasution.sd.queue;
public interface Queue <AnyType> {
void enqueue(AnyType data);//menambah data
AnyType dequeue();//melihat data terdepan kemudian menghapus
AnyType getFront();//melihat data terdepan
boolean isEmpty();//memeriksa apakah queue kosong
boolean isFull();//memeriksa apakah queue penuh
void makeEmpty();//mengkosongkan queue
}
QueueKita
- Pembuatan struktur data queue sendiri yang diberi nama QueueKita
- QueueKita mengimplementasi interface Queue pada package org.benynasution.sd.queue
Class QueueKita
package org.benynasution.sd.queue;
public class QueueKita<AnyType> implements Queue<AnyType>{
private static final int KAPASITAS_DEFAULT = 10;
private AnyType[] arraykita;
private int terpakai;
private int terdepan;
private int terbelakang;
public QueueKita(){
arraykita = (AnyType[]) new Object[KAPASITAS_DEFAULT];
makeEmpty();
}
public void enqueue(AnyType data) {
if(isFull()){
System.out.println("queue penuh, keluar dari aplikasi");
System.exit(1);
}
this.terbelakang = penambah(this.terbelakang);
this.arraykita[this.terbelakang] = data;
this.terpakai++;
}
public AnyType dequeue() {
if(isEmpty()){
System.out.println("queue kosong, keluar dari aplikasi");
System.exit(1);
}
this.terpakai--;
AnyType tmp = this.arraykita[this.terdepan];
this.arraykita[this.terdepan] = null;
this.terdepan = penambah(this.terdepan);
return tmp;
}
public AnyType getFront() {
if(isEmpty()){
System.out.println("queue kosong, keluar dari aplikasi");
System.exit(1);
}
return this.arraykita[this.terdepan];
}
public boolean isEmpty() {
return this.terpakai == 0;
}
public boolean isFull() {
return this.terpakai == this.arraykita.length;
}
public void makeEmpty() {
this.terpakai = 0;
this.terdepan = 0;
this.terbelakang = -1;
}
private int penambah(int awal){
if(++awal == this.arraykita.length)
awal = 0;
return awal;
}
}
Linked List
• Merupakan bentuk struktur data yang tersusun secara berurutan, sambung-menyambung, dinamis dan terbatas
• Linked List juga dikenal sebagai Senarai Berantai
• Linked List dapat terhubung karena adanya variabel yang berfungsi sebagai penunjuk (pointer)
• Masing-masing data dalam Linked List disebut sebagai node (simpul) yang menempati alokasi memori secara dinamis dan berupa stuktur data yang memiliki beberapa member/field
Macam Linked List
• Single Linked List
– Single Linked List non Circular
– Single Linked List Circular
• Double Linked List
– Double Linked List non Circular
– Double Linked List Circular
Single Linked List non Circular
• Single, variabel pointer hanya satu saja dan satu arah
• Linked List, node-node yang saling berhubungan
• Non Circular, node head dan node tail tidak tersambung
• Setiap node memiliki pointer ke node berikutnya
• Node terakhir akan menunjuk ke NULL, sebagai penanda akhir dari sebuah Linked List
Pembuatan Node
• Deklarasi node
public class Node{
private Object data;
private Node next;
}
- Penjelasan
– Pembuatan ADT bernama Node yang memiliki dua member:
• Member data dengan tipe data Object, sebagai variabel penampung data
• Member next dengan tipe data Node, sebagai variabel pointer
Pembuatan Linked List
• Deklarasi Linked List non Circular
public class LLNC
private Node head;
private Node tail;
- Penjelasan
– Pembuatan class LLNC dengan dua buah member
– Member head dengan tipe data Node sebagai awal
– Member tail dengan tipe data Node sebagai akhir
Penambahan Linked List
• Penambahan node di belakang (insertTail)
public void insertTail(Object data){
public void insertTail(Object data){
if(head==null){
head.data = tail.data = data;
head.next = tail.next = null;
}else{
Node nodenew = new Node();
nodenew.data = data;
nodenew.next = null;
tail.next = nodenew;
tail = nodenew;
}
}
- Penjelasan
– Object data merupakan informasi yang akan disimpan
– Jika head bernilai null, artinya LL baru dibuat, maka data untuk head dan tail berasal dari data dan pointer bernilai null
• Penambahan node di belakang (insertTail)
public void insertTail(Object data){
public void insertTail(Object data){
if(head==null){
head.data = tail.data = data;
head.next = tail.next = null;
}else{
Node nodenew = new Node();
nodenew.data = data;
nodenew.next = null;
tail.next = nodenew;
tail = nodenew;
}
}
- Penjelasan
– Buat node baru dengan nama nodenew bertipe Node
– Isikan data pada nodenew.data dan pointer nodenew.next dengan null
– Baris tail.next = nodenew menghubungkan tail dengan nodenew
• Penambahan node di depan (insertHead)
public void insertHead(Object data){
public void insertHead(Object data){
if(head==null){
head.data = tail.data = data;
head.next = tail.next = null;
}else{
Node nodenew = new Node();
nodenew.data = data;
nodenew.next = head;
head = nodenew;
}
}
- Penjelasan
– Object data merupakan informasi yang akan disimpan
– Jika head bernilai null, artinya LL baru dibuat, maka data untuk head dan tail berasal dari data dan pointer bernilai null
• Penambahan node di depan (insertHead)
public void insertHead(Object data){
public void insertHead(Object data){
if(head==null){
head.data = tail.data = data;
head.next = tail.next = null;
}else{
Node nodenew = new Node();
nodenew.data = data;
nodenew.next = head;
head = nodenew;
}
}
- Penjelasan
– Buat node baru dengan nama nodenew bertipe Node
– Isikan data pada nodenew.data dan pointer nodenew.next dengan tail
– Ubah head dengan nodenew
Penghapusan Linked List
• Penghapusan di belakang (removeTail)
public Object removeTail(){
Node tmp = head; Node hapus = new Node();
if(head.next==null){
head = tail = null;
return tmp.data;
}else{
while(tmp.next!=tail)
tmp = tail.next;
hapus = tail;
tail = tmp; tail.next = null;
return hapus.data;
}
}
- Penjelasan
– Beri nilai tmp sama dengan head, buat node hapus
– Jika head.next NULL, head dan tail bernilai NULL
– Kembalikan nilai dari tmp.data
• Penghapusan di belakang (removeTail)
public Object removeTail(){
Node tmp = head; Node hapus = new Node();
if(head.next==null){
head = tail = null;
return tmp.data;
}else{
while(tmp.next!=tail)
tmp = tmp.next; //enumerasi
hapus = tail;
tail = tmp; tail.next = null;
return hapus.data;
}
}
- Penjelasan
– Ketika tmp.next tidak sama dengan tail, kopikan tmp.next ke tmp
– Beri node hapus nilai dari obyek tail
– Tail sekarang adalah tmp, dan pointer berikutnya adalah null
– Kembalikan nilai dari hapus.data
• Penghapusan di depan (removeHead)
public Object removeHead(){
Node tmp = head;
if(head.next==null){
head = tail = null;
return tmp.data;
}else{
head = head.next;
return tmp.data;
}
}
- Penjelasan
– Beri nilai head ke tmp
– Jika head.next NULL, head dan tail bernilai NULL
– Kembalikan data dari tmp.data
• Penghapusan di depan (removeHead)
public Object removeHead(){
Node tmp = head;
if(head.next==null){
head = tail = null;
return tmp.data;
}else{
head = head.next;
return tmp.data;
}
}
- Penjelasan
– Kopikan head ke tmp
– Head sekarang adalah head.next
– Kembalikan data dari tmp.data (head lama)
Menampilkan Linked List
• Menampilkan Linked List menggunakan iterasi
for(Node n = head; n!=null; n = n.next){
System.out.println(n.data);
}
Menyisipkan Linked List
• Penyisipan data (insertAt[indeks])
public void insertAt(int number, Object data){
Node tmp = head; int idx = 0; Node nodenew = new Node();
nodenew.data = data; nodenew.next = null;
if(head.next==null){
nodenew.next = null; tail = nodenew;
head.next = tail;
}else{
while(tmp.next!=null){
if(idx>0 && idx==number){
nodenew.next = tmp.next;
tmp.next = nodenew;
break;
}
tmp = tmp.next; idx++;
}
}
}
- Penjelasan
– Parameter insert ada dua, number dan data, number bertipe int untuk menentukan di posisi mana data akan disisipkan dan data bertipe Object
– Kopikan head ke tmp sebagai nilai awal iterasi
– Buat variabel idx dengan tipe int untuk indeks
– Buat nodenew sebagai tempat penampung data baru, nodenew.data = data dan nodenew.next bernilai NULL
– Jika head bernilai NULL, artinya hanya ada satu node, maka tambahkan dibelakangnya sebagai tail
– Jika tidak, maka lakukan iterasi
– Iterasi dimulai dari pemeriksaan apakah nilai tmp.next bernilai NULL yang artinya bahwa tmp adalah tail, jika tidak maka iterasi dilakukan
– Asumsi bahwa penyisipan bukan dari indeks 0 (head) dan bukan di tail, tetapi ditengah-tengah sehingga untuk kondisi if bernilai idx>0
– Jika idx bernilai sama dengan number yang artinya posisi ditemukan, lakukan penyisipan
– Penyisipan dilakukan dengan memberikan nilai next untuk nodenew berupa nilai next dari tmp
– Sedangkan untuk next dari tmp yang baru adalah nodenew
– Keyword break untuk keluar dari loop sekaligus mengakhiri penyisipan
– Jika idx bernilai tidak sama dengan number, maka tambahkan idx dengan 1 dan pindahkan nilai tmp dengan tmp.next
Double Linked List non Circular
• Double, variabel pointer ada dua dan dua arah, prev dan next
• Linked List, node-node yang saling berhubungan
• Non Circular, node head dan node tail tidak tersambung
• Setiap node memiliki pointer ke node berikutnya dan node sebelumnya
• Node pertama dan terakhir akan menunjuk ke NULL, sebagai penanda awal dan akhir dari sebuah Double Linked List
Pembuatan Node
• Deklarasi node
public class Node{
private Object data;
private Node next;
private Node prev;
}
- Penjelasan
– Pembuatan ADT bernama Node yang memiliki dua member:
• Member data dengan tipe data Object, sebagai variabel penampung data
• Member next dengan tipe data Node, sebagai variabel pointer berikutnya
• Member prev dengan tipe data Node, sebagai variabel pointer sebelumnya
Pembuatan Double Linked List
• Deklarasi Double Linked List non Circular
public class DLLNC
private Node head;
private Node tail;
- Penjelasan
– Pembuatan class DLLNC dengan dua buah member
– Member head dengan tipe data Node sebagai awal
– Member tail dengan tipe data Node sebagai akhir
Penambahan Double Linked List
• Penambahan di belakang (insertTail)
public void insertTail(Object data){
Node nodenew = new Node();
nodenew.data = data; nodenew.next = nodenew.prev = null;
if(head==null){
head = tail = nodenew;
head.prev = tail.prev = null;
head.next = tail.next = null;
}else{
tail.next = nodenew;
nodenew.prev = tail;
tail = nodenew;
tail.next = null
}
}
- Penjelasan
– Buat node baru bernama nodenew untuk menampung data, dimana nodenew.data = data dan pointer next dan prev bernilai NULL
– Jika head bernilai NULL yang artinya Double Linked List masih kosong, maka head dan tail bernilai nodenew
– Nilai prev untuk head dan tail sama, NULL
– Nilai next untuk head dan tail sama, NULL
– Jika head tidak bernilai NULL, maka nilai tail.next adalah nodenew, yang artinya rangkaian yang baru adalah nodenew
– Nilai prev untuk nodenew adalah tail
– Tail yang baru adalah nodenew menggantikan tail yang lama
– Nilai next untuk tail sekarang adalah NULL
- Penambahan di depan (insertHead)
public void insertHead(Object data){
Node nodenew = new Node();
nodenew.data = data; nodenew.next = nodenew.prev = null;
if(head==null){
head = tail = nodenew;
head.prev = tail.prev = null;
head.next = tail.next = null;
}else{
head.prev = nodenew;
nodenew.next = head;
head = nodenew;
head.prev = null;
}
}
- Penjelasan
– Buat node baru bernama nodenew untuk menampung data, dimana nodenew.data = data dan pointer next dan prev bernilai NULL
– Jika head bernilai NULL yang artinya Double Linked List masih kosong, maka head dan tail bernilai nodenew
– Nilai prev untuk head dan tail sama, NULL
– Nilai next untuk head dan tail sama, NULL
– Jika head tidak bernilai NULL, maka head.prev adalah nodenew, yang artinya rangkaian yang baru adalah nodenew
– Nilai next untuk nodenew adalah head
– Head yang baru adalah nodenew menggantikan head yang lama
– Nilai prev untuk head sekarang adalah NULL
Penghapusan Double Linked List
• Penghapusan dari belakang (removeTail)
public Object removeTail(){
Node hapus = new Node();
if(head.next==null){
hapus = head;
head = tail = null;
return hapus.data;
}else{
hapus = tail;
tail = tail.prev;
tail.next = null;
return hapus.data;
}
}
- Penjelasan
– Buat node baru bernama hapus untuk menampung data sementara
– Jika nilai next untuk head adalah NULL yang artinya hanya ada satu data, maka hapus bernilai sama dengan head
– Beri nilai NULL untuk head dan tail
– Kembalikan data dari hapus.data
– Jika nilai next untuk head bukan NULL yang artinya ada lebih dari satu data, maka hapus bernilai sama dengan tail
– Tail sekarang adalah tail.prev, yaitu node sebelum tail
– Nilai next untuk tail baru adalah NULL
– Kembalikan data dari hapus.data
- Penghapusan dari depan (removeHead)
public Object removeHead(){
Node hapus = new Node();
if(head.next==null){
hapus = head;
head = tail = null;
return hapus.data;
}else{
hapus = head;
head = head.next;
head.prev = null;
return hapus.data;
}
}
• Penjelasan
– Buat node baru bernama hapus untuk menampung data sementara
– Jika nilai next untuk head adalah NULLyang artinya hanya ada satu data, maka hapus bernilai sama dengan head
– Beri nilai NULL untuk head dan tail
– Kembalikan data dari hapus.data
– Jika nilai next untuk head bukan NULL yang artinya ada lebih dari satu data, maka hapus bernilai sama dengan head
– Head sekarang adalah head.next, yaitu node sesudah head
– Nilai prev untuk head baru adalah NULL
– Kembalikan data dari hapus.data
Menampilkan Double Linked List
• Menampilkan Double Linked List menggunakan iterasi
for(Node n = head; n!=null; n = n.next){
System.out.println(n.data);
}
Menyisipkan Double Linked List
• Penyisipan data (insertAt[indeks])
public void insertAt(int number, Object data){
Node tmp = head; int idx = 0; Node nodenew = new Node();
nodenew.data = data; nodenew.next = nodenew.prev = null;
if(head.next==null){
nodenew.next = null;
tail = nodenew; tail.prev = head;
head.next = tail;
}else{
while(tmp.next!=null){
if(idx>0 && idx==number){
nodenew.next = tmp.next;
nodenew.prev = tmp;
tmp.next.prev = nodenew;
tmp.next = nodenew;
break;
}
tmp = tmp.next; idx++;
}
}
}
Menyisipkan Linked List
• Penjelasan
– Parameter insert ada dua, number dan data, number bertipe int untuk menentukan di posisi mana data akan disisipkan dan data bertipe Object
– Kopikan head ke tmp sebagai nilai awal iterasi
– Buat variabel idx dengan tipe int untuk indeks
– Buat nodenew sebagai tempat penampung data baru, nodenew.data = data, nodenew.next dan nodenew.prev bernilai NULL
– Jika head bernilai NULL, artinya hanya ada satu node, maka tambahkan dibelakangnya sebagai tail
– Sambungkan nilai prev untuk tail ke head dan nilai next untuk head ke tail
– Jika tidak, maka lakukan iterasi
– Iterasi dimulai dari pemeriksaan apakah nilai tmp.next bernilai NULL yang artinya bahwa tmp adalah tail, jika tidak maka iterasi dilakukan
– Asumsi bahwa penyisipan bukan dari indeks 0 (head) dan bukan di tail, tetapi ditengah-tengah sehingga untuk kondisi if bernilai idx>0
– Jika idx bernilai sama dengan number yang artinya posisi ditemukan, lakukan penyisipan
– Penyisipan dilakukan dengan memberikan nilai next untuk nodenew berupa nilai next dari tmp, kemudian nilai prev nodenew adalah tmp
– Sedangkan untuk next dari tmp yang baru adalah nodenew
– Keyword break untuk keluar dari loop sekaligus mengakhiri penyisipan
– Jika idx bernilai tidak sama dengan number, maka tambahkan idx dengan 1 dan pindahkan nilai tmp dengan tmp.next
Solusi Menggunakan Linked List
do{
insertTail(removeHead());
insertTail(removeHead());
removeHead();
}while(head.next!=null);
