LandasanTeori
PENGERTIAN :
•
Stack (tumpukan) adalah
struktur data dimana proses pengambilan dan penambahan element dilakukan pada
satu ujung yang sama.
•
Stack mengikuti konsep LIFO.
•
LIFO (Last In First Out) :
elemen yang terakhir kali masuk akan menjadi elemen yang pertama kali keluar.
•
Stack dapat dibuat dengan
menggunakan array maupun linked list.
Stack (Tumpukan)
“Benda yang terakhir
masuk ke dalam stack akan menjadi yang pertama keluar
dari stack
Ilustrasi Stack
•
Karena Compo ditumpuk di posisi terakhir,
maka Compo akan menjadi elemen teratas dalam tumpukan. Sebaliknya, karena Televisi ditumpuk pada saat pertama
kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika dilakukan pengambilan elemen dari
tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo.
PUSH, POP dan
TOP
•
Operasi dasar pada stack adalah
: pop dan push.
–
Push : proses menambah item pada
stack.
–
Pop : proses mengambil item pada
stack.
•
Pop dan push sama-sama
dilakukan pada item yang terakhir kali ditambahkan pada stack.
Sedangkan pointer TOP
akan menunjuk pada element yang paling atas (yang paling akhir ditamba
Proses Operasi Stack
•
Contoh lain adalah ada sekumpulan perintah stack yaitu push(5), push(7),
pop, push(3), pop, pop. Jika dijalankan, maka yang akan terjadi adalah :
Latihan
•
Misal L adalah list linier.
Gambarkan proses Stack untuk tiap operasi berikut dan tuliskan hasil akhirnya
jika top menunjuk pada data f :
L = {a,b,c,d,e,f}
pop();
pop();
push(z);
push(y);
pop();
push(w);
Pointer Top
•
Digunakan untuk menunjuk
element paling akhir yang dimasukkan kedalam stack.
•
Jika top tidak menunjuk pada
element manapun hal ini menunjukkan bahwa stack dalam kondisi kosong (empty).
•
top akan menyimpan index
element paling akhir masuk.
Operasi pada Stack
(1) Deklarasi
•
Proses yang harus dilakukan
pertama kali adalah deklarasi/menyiapkan tempat.
•
Langkah yang harus dilakukan
adalah :
– Deklarasi class
– Deklarasi struktur
data (menggunakan array atau linked list)
– Deklarasi pointer
top
Deklarasi
Stack dengan Array
1. Pembuatan class
contoh
:
2. Pembuatan variabel
top :
int
top;
3. Pembuatan variabel
untuk menampung panjang array :
int
array_size;
(mendeklarasikan variabel bernama array_size
dengan tipe integer)
4. Pembuatan variabel
Array :
int tumpukan[];
(mendeklarasikan variabel array
bernama tumpukan dengan tipe integer)
Program
Deklarasi (Array)
(2)
Inisialisasi
•
Merupakan proses pemberian
nilai awal.
•
Pada Array :
1. Pembentukan obyek
array beserta ukurannya.
tumpukan = new int[10];
(pembentukan
obyek array yang memiliki 10 element, dan alamat obyek akan disimpan pada
variabel bernama tumpukan)
1. Pemberian nilai awal
pada variabel top=-1.
int top=-1;
Program
Inisialisasi (Array)
(3) Cek
Kosong
•
Operasi yang digunakan untuk
mengecek kondisi stack dalam keadaan kosong.
•
Caranya : melihat nilai top.
Jika nilainya sama seperti ketika inisialisasi berarti stack dalam kondisi
kosong (top =-1 atau top=null).
•
Operasi ini harus dapat
mengembalikan nilai true jika stack kosong dan false jika sebaliknya.
Program
“isEmpty” (Array)
(4) Cek
Penuh
•
Operasi yang hanya dapat
diterapkan pada stack yang menggunakan array.
•
Operasi ini digunakan untuk
mengecek kondisi stack dalam keadaan penuh.
•
Caranya : melihat nilai top.
Jika nilai top sudah menunjuk n-1 (dimana n adalah ukuran array) maka dapat
diindikasikan stack sudah dalam kondisi penuh.
•
Operasi ini harus dapat
mengembalikan nilai true jika stack penuh dan false jika sebaliknya.
Program
“isFull” (Array)
(5)
Operasi POP
•
Pop adalah proses pengambilan
data pada stack.
•
Ketika pop terjadi, element
pada stack akan berkurang, yaitu element yang paling akhir dikurangi.
•
Sehingga posisi pointer top
juga akan bergeser :
– top di-decrement
•
Langkah-langkah :
– Pengecekan stack
dalam kondisi kosong dengan memanggil method isEmpty(). Jika nilai yang
dikembalikan true maka pop tidak bisa dilakukan (penangkapan error oleh
exception handling). Jika nilai yang dikembalikan false maka akan dilakukan
langkah berikutnya (langkah 2 dan 3).
– Data dari element
paling belakang akan menjadi return value (nilai yang dikembalikan).
– Pergeseran posisi
top.
Program
Pop (Array)
•
Untuk menggunakan
StackException() harus disertakan import package dari java.util.*
(6)
Operasi Push
•
Push adalah proses penambahan
element pada stack.
•
Ketika push terjadi, element
pada stack akan bertambah 1.
•
Posisi pointer top akan
bergeser menunjuk pada element baru yang ditambahkan.
– top akan
di-increment.
•
Langkah-langkah :
– Penambahan element
baru pada bagian belakang stack.
– Pergeseran posisi
top.
•
Khusus untuk array, terlebih
dahulu harus dicek kondisi stack penuh dengan memanggil method isFull(). Jika
nilai yang dikembalikan true maka bisa ditampilkan pesan kesalahan atau
dilakukan resizing array.
Program
Push (Array)
Program
Rezising()
(7)
Operasi peek
•
Peek adalah proses pengaksesan
element yang ditunjuk oleh top(yaitu element yang terakhir kali ditambahkan).
•
Operasi ini berbeda dengan pop
karena tidak disertai dengan penghapusan data yang ada hanya pengaksesan
(pengembalian data saja).
Program
Peek (Array)
LISTING PROGRAM
1.
Masukan kedalam tumpukan angka berikut 30,10,50,40,20
import
java.util.EmptyStackException;
/**
*
*
@author nn
*/
public class Stack {
/**
* @param args the command line arguments
*/
static int tumpukan[];
static int array_size;
static int top;
static void inisialisasi(int arrSize){
array_size=arrSize;
tumpukan=new int [array_size];
top =-1;
}
static boolean IsEmpty(){
return (top==-1);
}
static boolean isFull(){
return (top==array_size-1);
}
static int popStack(){
if (IsEmpty())
throw new EmptyStackException();
return tumpukan[top--];
}
static
int []resizing(int[]element){
int[] newArr=new int[2*element.length];
array_size=newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size);
return newArr;
}
static void pushStack(int data){
if(isFull()){
System.out.println("Stack
Penuh");
tumpukan=resizing(tumpukan);
}
tumpukan[++top]=data;
}
static void peekAllStack(){
int baru=top;
for (int i = baru; i >=0; i--) {
System.out.println( tumpukan[i]);
}
}
public static void main(String[] args) {
// TODO code application logic here
inisialisasi(5);
pushStack(30);
pushStack(10);
pushStack(50);
pushStack(40);
pushStack(20);
peekAllStack();
}
}
Codingan
2.
Buatlah methode untuk mengakses seluruh data yang ada pada tumpukan dari
tumpukan paling atas sampai paling bawah tanpa menghapus isinya
package javaapplication11;
import java.util.Stack;
/**
*
*
@author nn
*/
public class JavaApplication11 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack s = new Stack();
s.push(30);
s.push("10");
s.push("50");
s.push("40");
s.push("20");
//menampilkan semuaisistack
System.out.println("Isistack : " + s);
}
}
Codingan
3.
Buatlah
tiga buah tumpukan TPA,TPB,TPC kemudian masukan data ke tumpukan TPA dengan
data seperti soal no 1
import java.util.EmptyStackException;
/**
*
*
@author nn
*/
public class Stack3 {
/**
* @param args the command line arguments
*/
static int TPA[], TPB[], TPC[];
static int array_size_TPA, array_size_TPB, array_size_TPC;
static int top_TPA, top_TPB, top_TPC;
static void inisialisasi(int arrSize) {
array_size_TPA = array_size_TPB = array_size_TPC = arrSize;
TPA = new int[array_size_TPA];
TPB = new int[array_size_TPB];
TPC = new int[array_size_TPC];
top_TPA=top_TPB=top_TPC=-1;
}
static boolean IsEmpty_TPA() {
return (top_TPA == -1);
}
static boolean IsEmpty_TPB() {
return (top_TPB == -1);
}
static boolean IsEmpty_TPC() {
return (top_TPC == -1);
}
static boolean isFull_TPA() {
return (top_TPA == array_size_TPA - 1);
}
static boolean isFull_TPB() {
return (top_TPB == array_size_TPB - 1);
}
static boolean isFull_TPC() {
return (top_TPC == array_size_TPC - 1);
}
static int popStack_TPA() {
if (IsEmpty_TPA()) {
throw new EmptyStackException();
}
return TPA [top_TPA--];
}
static int popStack_TPB() {
if (IsEmpty_TPB()) {
throw new EmptyStackException();
}
return TPB [top_TPB--];
}
static int popStack_TPC() {
if (IsEmpty_TPC()) {
throw new EmptyStackException();
}
return TPC [top_TPC--];
}
static int[] resizing_TPA(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPA = newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size_TPA);
return newArr;
}
static int[] resizing_TPB(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPB = newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size_TPB);
return newArr;
}
static int[] resizing_TPC(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPC = newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size_TPC);
return newArr;
}
static void pushStack_TPA(int data) {
if (isFull_TPA()) {
System.out.println("Stack Penuh");
TPA = resizing_TPA(TPA);
}
TPA[++top_TPA] = data;
}
static void pushStack_TPB(int data) {
if (isFull_TPB()) {
System.out.println("Stack Penuh");
TPA = resizing_TPB(TPB);
}
TPB[++top_TPB] = data;
}
static void pushStack_TPC(int data) {
if (isFull_TPC()) {
System.out.println("Stack Penuh");
TPA = resizing_TPB(TPC);
}
TPC[++top_TPC] = data;
}
static void peekAllStack_TPA() {
int baru = top_TPA;
for (int i = baru; i >= 0; i--) {
System.out.println(TPA[i]);
}
}
static void peekAllStack_TPB() {
int baru = top_TPB;
for (int i = baru; i >= 0; i--) {
System.out.println(TPB[i]);
}
}
static void peekAllStack_TPC() {
int baru = top_TPC;
for (int i = baru; i >= 0; i--) {
System.out.println(TPC[i]);
}
}
public static void main(String[] args) {
// TODO code application logic here
inisialisasi(5);
pushStack_TPA(30);
pushStack_TPA(10);
pushStack_TPA(50);
pushStack_TPA(40);
pushStack_TPA(20);
peekAllStack_TPA();
}
}
Codingan
4.
Pindahkan isi tumpukan TPA ke TPB, kemudian tampilkan hasilnya apa yang
dapat anda simpulkan
import java.util.EmptyStackException;
/**
*
*
@author nn
*/
public class Stack4 {
/**
* @param args the command line arguments
*/
static int TPA[], TPB[], TPC[];
static int array_size_TPA, array_size_TPB, array_size_TPC;
static int top_TPA, top_TPB, top_TPC;
static void inisialisasi(int arrSize) {
array_size_TPA = array_size_TPB = array_size_TPC = arrSize;
TPA = new int[array_size_TPA];
TPB = new int[array_size_TPB];
TPC = new int[array_size_TPC];
top_TPA = top_TPB = top_TPC = -1;
}
static boolean IsEmpty_TPA() {
return (top_TPA == -1);
}
static boolean IsEmpty_TPB() {
return (top_TPB == -1);
}
static boolean IsEmpty_TPC() {
return (top_TPC == -1);
}
static boolean isFull_TPA() {
return (top_TPA == array_size_TPA - 1);
}
static boolean isFull_TPB() {
return (top_TPB == array_size_TPB - 1);
}
static boolean isFull_TPC() {
return (top_TPC == array_size_TPC - 1);
}
static int popStack_TPA() {
if (IsEmpty_TPA()) {
throw new EmptyStackException();
}
return TPA[top_TPA--];
}
static int popStack_TPB() {
if (IsEmpty_TPB()) {
throw new EmptyStackException();
}
return TPB[top_TPB--];
}
static int popStack_TPC() {
if (IsEmpty_TPC()) {
throw new EmptyStackException();
}
return TPC[top_TPC--];
}
static int[] resizing_TPA(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPA = newArr.length;
System.arraycopy(TPA, 0, TPB, 0, array_size_TPA);
return newArr;
}
static int[] resizing_TPB(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPB = newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size_TPB);
return newArr;
}
static int[] resizing_TPC(int[] element) {
int[] newArr = new int[2 * element.length];
array_size_TPC = newArr.length;
System.arraycopy(element, 0, newArr, 0, array_size_TPC);
return newArr;
}
static void pushStack_TPA(int data) {
if (isFull_TPA()) {
System.out.println("Stack Penuh");
TPA = resizing_TPA(TPA);
}
TPA[++top_TPA] = data;
}
static void pushStack_TPB(int data) {
if (isFull_TPB()) {
System.out.println("Stack
Penuh");
TPA = resizing_TPB(TPB);
}
TPB[++top_TPB] = data;
}
static void pushStack_TPC(int data) {
if (isFull_TPC()) {
System.out.println("Stack Penuh");
TPC = resizing_TPC(TPC);
}
TPC[++top_TPC] = data;
}
static void peekAllStack_TPA() {
int baru = top_TPA;
for (int i = baru; i >= 0; i--) {
System.out.println(TPA[i]);
}
}
static void peekAllStack_TPB() {
int baru = top_TPB;
for (int i = baru; i >= 0; i--) {
System.out.println(TPB[i]);
}
}
static void peekAllStack_TPC() {
int baru = top_TPC, lama;
for (int i = baru; i >= 0; i--) {
System.out.println(TPC[i]);
}
}
static void copyStack(int[] asal, int[] tujuan) {;
for (int r = top_TPA; r>=0; r--) {
pushStack_TPB(asal[r]);
}
}
public static void main(String[] args) {
// TODO code application logic here
inisialisasi(5);
pushStack_TPA(30);
pushStack_TPA(10);
pushStack_TPA(50);
pushStack_TPA(40);
pushStack_TPA(20);
System.out.println("=============STACK
A====================");
peekAllStack_TPA();
System.out.println("=============STACK
B=====================");
copyStack(TPA, TPB);
peekAllStack_TPB();
}
}
Codingan
n
Sharing is Sexy !
About the Author
0 komentar: