STACK PADA STRUKTUR DATA

Pengertian Stack atau Tumpukan

Pengertian Stack atau Tumpukan adalah suatu stuktur data yang penting dalam pemrograman yang mempunyai sifat LIFO (Last In First Out), Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.  Stack (Tumpukan) adalah list linier yang dikenali elemen puncaknya (TOP) dan Aturan penyisipan dan penghapusan elemennya tertentu. Penyisipan selalu dilakukan “di atas“  TOP dan Penghapusan selalu dilakukan pada TOP.

STACK ATAU TUMPUKAN PADA MATAKULIAH STRUKTUR DATA

Stack karena aturan penyisipan dan penghapusan semacam itu, TOP adalah satu-satunya alamat tempat terjadi operasi. Elemen yang ditambahkan paling akhir akan menjadi elemen yang akan dihapus.Dikatakan bahwa elemen Stack akan tersusun secara LIFO (Last In First Out).

karena kita menumpuk Compo di posisi terakhir, maka Compo akan menjadi elemen teratas dalam tumpukan. 

Sebaliknya, karena kita menumpuk Televisi pada saat pertama kali, maka elemen Televisi menjadi elemen terbawah dari tumpukan. Dan jika kita mengambil elemen dari tumpukan, maka secara otomatis akan terambil elemen teratas, yaitu Compo juga.

OPERASI-OPERASI/FUNGSI STACK

• Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
• Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
• Clear : digunakan untuk mengosongkan stack
• IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
• IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

INISIALISASI STACK

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah KOSONG.!

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH!

Ilustrasi stack pada saat inisialisasi

Fungsi IsFull

Untuk memeriksa apakah stack sudah penuh?

Dengan cara memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full

Ilustrasi

 

 Contoh Rumus seserhaana Stack

#include <iostream.h>
#include<stdio.h>
#define MAX 5
#define true 1
#define false 0

char stack[MAX];
int top;

void init(void);
int full(void);
int empty(void);
char pop(void);
void clear(void);
void push(char info);
void baca(void);

void main()
{
char pilih,elm;
cout<<"demo operasi single stack"<<endl;
init();
do
{
cout<<"OPERASI SINGLE STACK :"<<endl;
cout<<"[1]PUSH"<<endl;
cout<<"[2]POP"<<endl;
cout<<"[3]clear"<<endl;
cout<<"[4]BACA"<<endl;
cout<<"[5]selesai"<<endl;
cout<<"pilihan:";cin>>pilih;
switch(pilih)
{
case '1':cout<<"PUSH-->";cin>>elm;
push(elm);
break;
case '2':elm=pop();
cout<<"pop"<<elm;
break;
case '3':clear();
break;
case '4':baca();
break;
case '5':break;
default:cout<<"salah pilih..."<<endl;
}
cout<<endl;
}
while(pilih!='5');
}

void init(void)
{
top=0;
}
void push(char info)
{
if(full()!=true)
{
top++;
stack[top]=info;
}
else
cout<<"stack overflow..."<<endl;
}
char pop(void)
{
char info;
if(empty()!=true)
{
info=stack[top];
top--;
return(info);
}
else
cout<<"stack underflow..."<<endl;
}
void clear(void)
{
top=0;
}
int full(void)
{
if(top==MAX)
return(true);
else
return(false);
}
int empty(void)
{
if(top==0)
return(true);
else
return(false);
}
void baca(void)
{ int i;
cout<<"isi stack:"<<endl;

if(top>0)
{
for(i=1;i<=top;i++)
cout<<stack[i];
}
else
cout<<"(kosong)";
cout<<endl;
}

Operasi-operasi/fungsi Stack:
1. Push : digunakan untuk menambah item pada stack pada tumpukan paling atas.
2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas.
3. Clear : digunakan untuk mengosongkan stack.
4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong.
5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh.

 

OPERASI DASAR STACK

OPERASI PADA STACK

1. CREATE (STACK)
2. ISEMPTY (STACK)
3. PUSH (ELEMEN, STACK)
4. POP (STACK)

CREATE(S)
Operator ini berfungsi untuk membuat sebuah stack kosong (menjadi hampa) dan didefinisikan bahwa
NOEL (CREATE (S)) = 0 dan
TOP (CREATE(S)) = null / tidak terdefinisi


 ISEMPTY(S)
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong (hampa) atau tidak . Operasinya akan bernilai boolean dengan definisi sebagai berikut :
ISEMPTY(S) = true, jika S adalah stack kosong atau NOEL(S) = 0
False, jika S bukan stack kosong atau NOEL(S)  0
Catatan : ISEMPTY(CREATE(S)) = true

 PUSH(E,S)
• Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack . Notasi yang digunakan adalah PUSH(E,S)
Artinya : menambahkan elemen E ke dalam stack S
• Elemen yang baru masuk ini akan menempati posisi TOP jadi TOP(PUSH(E,S)) = E
• Akibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL (S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false )

 POP(S)
• Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack, notasinya POP(S)
• Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP.
• Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang 1 dan elemen pada posisi TOP akan berubah.
• Operator ini tidak dapat digunakan pada stack kosong, artinya POP(CREATE(S)) = error condition dan
POP(PUSH(E,S)) = S

Catatan : TOP(PUSH(E,S)) = E

Queue
Adalah suatu bentuk khusus dari linear list dengan operasi penyisipan (insertion) hanya pada salah satu sisi ( Rear/ belakang) dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya (Front/ depan) dari list.

Antrean Q = [ Q1, Q2, Q3,……….., QT]
Front(Q) = bagian depan dari antrean Q
Rear(Q) = bagian belakang dari antrean Q
Noel(Q) = Jumlah elemen di dalam antrean ( berharga integer)
Jadi : Front(Q) = QT
Rear(Q) = Q1
Noel(Q) = T

Antrean beroperasi secara FIFO ( First In First Out) yang pertama masuk, yang pertama keluar.

 Operasi dasar pada Antrean :
1. CREATE(Q)
Operator untuk membentuk suatu antrean hampa
Q = [,…….,]
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak didefinisikan
REAR(CREATE(Q)) = tidak didefinisikan

2. ISEMPTY(Q)
Operator yang menentukan apakah antrean Q hampa atau tidak.
Operand dari operator ISEMPTY adalah antrean.
Hasilnya bertipe data Boolean
ISEMPTY(Q) =TRUE jika Q adalah antrean hampa (NOEL(Q) = 0)
FALSE jika Q bukan antrean kosong (NOEL(Q)  0)

3. INSERT(E,Q)
Operator yang menyisipkan elemen E ke dalam antrean Q
Catt : Elemen Q ditempatkan pada bagian belakang antrean dan antrean menjadi lebih panjang
Q = [ A, B, C, D]
REAR(INSERT(E,Q)) = E
FRONT(Q) = A
NOEL(Q) = 5
ISEMPTY(INSERT(E,Q)) = FALSE

4. REMOVE(Q)
Operator yang menghapus elemen bagian depan dari antrean Q dan antrean menjadi lebih pendek
Jika NOEL(Q) = 0 maka
REMOVE(Q) = ERROR ( UNDERFLOW)

 Penyajian dari antrean :
1. One way list
2. Array
 Menunjukkan bagaimana suatu antrean dalam array Queue dengan N elemen
1. Antrean mula-mula terdiri dari elemen AAA, BBB, CCC, DDD

1 2 3 4 5 6 7 8 9
FRONT(Q) = AAA : 1
REAR(Q) = DDD : 4


2. REMOVE(Q)

1 2 3 4 5 6 7 8 9

FRONT(Q) = BBB : 2
REAR(Q) = DDD : 4

3. INSERT(EEE,Q)
1 2 3 4 5 6 7 8 9
FRONT(Q) = BBB : 2
REAR(Q) = EEE : 5
KESIMPULAN :
Untuk setiap kali penghapusan nilai FRONT bertambah
Untuk setiap kali penambahan nilai REAR akan bertambah

 Antrean yang disimpan dalam array dengan 5 lokasi memori sebagai array Sirkular.

1. Pada Awal Hampa
FRONT = 0 REAR = 0 1 2 3 4 5

2. A dan B dimasukkan
FRONT : 1
REAR : 2 1 2 3 4 5


3. C, D , dan E dimasukkan
FRONT :1
REAR : 5
1 2 3 4 5
4. A, B, dan C dihapus
FRONT : 4
REAR :5
1 2 3 4 5
5. F dimasukkan
FRONT : 4
REAR : 1

1 2 3 4 5
6. D dihapus
FRONT : 5
REAR :1
1 2 3 4 5
7. G dan H dimasukkan
FRONT : 5
REAR : 3
1 2 3 4 5

8. E dihapus
FRONT :1
REAR : 3
1 2 3 4 5
 ALGORITMA QINSERT
QINSERT(QUEUE, N, FRONT, DATA)
1. {Apakah antrean penuh}
Jika FRONT = 1 dan REAR = N atau Jika FRONT = REAR+1, maka Write : OVERFLOW, return.
2. Jika FRONT = NULL maka FRONT := 1, REAR := 1
Dalam hal ini
Jika FRONT = N maka REAR := 1
Dalam hal lain
REAR := REAR + 1
3. QUEUE(REAR) := DATA ( masukkan elemen baru)
4. Return

 ALGORITMA QDELETE
QDELETE(QUEUE, N, FRONT, REAR, DATA)
1. {Apakah antrean kosong}
Jika FRONT = NULL, maka Write : UNDERFLOW, return.
2. DATA := QUEUE(FRONT)
3. (FRONT mendapat nilai baru)
Jika FRONT =REAR maka FRONT := NULL
REAR := NULL
Dalam hal ini
Jika FRONT := N maka FRONT := 1
Dalam hal lain
FRONT := FRONT + 1
4. Return

LINK LIST

PENDAHULUAN
 Dalam suatu linier list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
 Misalkan ada 1500 item yang merupakan elemen dari suatu linier list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linier list tersebut. Tetapi elemen ke–57akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.

 Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.

 

 Penerapan Stack dalam kehidupan sehari

contoh penerapan stack dalam kehidupan sehari-hari:
Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.
Misalnya jika VCD langsung diambil, compo akan jatuh. Prinsip stack ini bisa diterapkan dalam pemrograman. Di C++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked list.
Abstract Data Types adalah konsep matematis yang mendefinisikan suatu tipe data, terdiri dari sejumlah nilai dan operasi. ADT terdiri dari struktur data abstrak dan operasi, dimana struktur data abstrak hanya dapat diakses dengan mendefinisikan operasi. Sekumpulan data dan operasi terhadap data tersebut yang definisi-nya tidak bergantung pada implementasi tertentu. Kumpulan dari berbagai macam operasi tersebut disebut interface (Antar Muka). Dan operasi tersebut dapat dilihat dari luar karena memiliki Interface.
Secara garis besar, ADT ada beberapa bagian yaitu:
• List
• Stack
• Queue

Dan dalam kehidupan sehari-hari ADT dapat dicontohkan sebagai berikut:

LIST
List merupakan sebuah kumpulan benda di mana setiap benda memiliki posisi.
Misalnya:
• Urutan angka pada keyboard komputer
• Urutan lagu pada playlist Mp3 player
• Dll

STACK
Stack adalah merupakan sebuah kumpulan benda dimana hanya benda yang baru dimasukkan yang dapat diakses atau dilihat. Stack juga merupakan perintah pengumpulan data secara linier yang disebut “last in, first out” (LIFO).
Misalnya:
• Setumpuk koran, dimana koran yang paling terakhir ditambahkan dan ditaruh di atas tumpukan yang dapat dilihat.
• Tumpukan kotak rokok, koin, buku, dll

QUEUE atau ANTRIAN
Queue atau antrian adalah sebuah kumpulan benda di mana hanya benda yang terakhir dimasukkan yang dapat diakses. Queue atau Antrian merupakan perintah pengumpulan data yang disebut “first-in, first-out”. Aplikasi ini meliputi jadwal pekerjaan dalam sebuah operasi
Misalnya:
a. Antrian printer job pada sebuah jaringan
b. Antrian nasabah pada sebuah bank
c. Antrian loket bioskop, dll

contoh penerapan stack dalam kehidupan sehari

Contoh Penerapan Antrian dalam Aplikasi Sehari-hari
Jika diartikan secara harafiah, queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehiduypan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah
enqueue.
Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :
a. EnQueue Memasukkan data ke dalam antrian
b. DeQueue Mengeluarkan data terdepan dari antrian
c. Clear Menghapus seluruh antrian
d. IsEmpty Memeriksa apakah antrian kosong
e. IsFull Memeriksa apakah antrian penuh

 

Referensi:

http://kurniawandanie.blogspot.co.id/2014/01/pengertian-stack-atau-tumpukan.html

http://apps.cs.ipb.ac.id:3000/775/apa-saja-operasi-operasi-yang-digunakan-pada-stack

http://tutetutetute.blogspot.co.id/2010/02/operasi-dasar-stack.html

http://dulmid99.blogspot.co.id/2013/06/contoh-penerapan-stack-dalam-aplikasi.html