STACK (Tumpukan)

Stack adalah suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Contoh dalam kehidupan sehari-hari adalah tumpukan piring di sebuah restoran yang tumpukannya dapat ditambah pada bagian paling atas dan jika mengambilnya pun dari bagian paling atas pula.

 Macam-macam tumpukan

Ada 2 operasi paling dasar dari stack yang dapat dilakukan, yaitu :

1.   Operasi push yaitu operasi menambahkan elemen pada urutan terakhir (paling atas).

2.  Operasi pop yaitu operasi mengambil sebuah elemen data pada urutan terakhir dan menghapus elemen tersebut dari stack.

Sebagai contoh, misalkah ada data sebagai berikut : 1 3 5 6, maka data tersebut dapat tersimpan dalam bentuk sebagai berikut : 

asumsi penyimpanan stack

               

 

 

Contoh lain adalah ada sekumpulan perintah stack yaitu push(5), push(7), pop, push(3), pop. Jika dijalankan, maka yang akan terjadi adalah :

Selain operasi dasar stack (push dan stack), ada lagi operasi lain yang dapat terjadi dalam stack yaitu :

1.   Proses deklarasi yaitu proses pendeklarasian stack.

2.   Proses isempty yaitu proses pemeriksaan apakah stack dalam keadaan kosong.

3.   Proses isfull yaitu proses pemeriksaan apakah stack telah penuh. 

4.  Proses inisialisasi yaitu proses pembuatan stack kosong, biasanya dengan pemberian nilai untuk top. 

 

Representasi stack dalam pemrograman, dapat dilakukan dengan 2 cara yaitu :

1. Representasi stack dengan array

2. Representasi stack dengan single linked list 

Representasi stack dengan menggunakan single linked list :

                                        

Operasi-operasi stack secara lengkap adalah sebagai berikut :

•         Pendeklarasian stack

Proses pendeklarasian stack adalah proses pembuatan struktur stack dalam memori. Karena stack dapat direpresentasikan dalam 2 cara, maka pendeklarasian stack pun ada 2 yaitu :

a.       Pendeklarasian stack yang menggunakan array.

Suatu stack memiliki beberapa bagian yaitu

*        top yang menunjuk posisi data terakhir (top)

*        elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.

*        maks_elemen yaitu variable yang menunjuk maksimal banyaknya elemen dalam stack.

Dalam bahasa C, pendeklarasiannya adalah :

  

• Inisialisasi stack adalah proses pembuatan suatu stack kosong. Adapun langkah-langkah proses tersebut berdasarkan jenis penyimpanannya adalah : 

a.       Inisialisasi stack yang menggunakan array. 

Proses inisialisasi untuk stack yang menggunakan array adalah dengan mengisi nilai field top dengan 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan 0 (contoh bahasa C), maka top diisi dengan nilai -1.

 

 

•  Operasi IsEmpty

Operasi ini digunakan untuk memeriksa apakah stack dalam keadaan kosong. Operasi ini penting dilakukan dalam proses pop. Ketika suatu stack dalam keadaan kosong, maka proses pop tidak bisa dilakukan. Adapun langkah-langkah operasi ini adalah :

    A.      Operasi IsEmpty pada stack yang menggunakan array.

Operasi ini dilakukan hanya dengan memeriksa field top. Jika top bernilai 0 (untuk elemen yang dimulai dengan index 1) atau top bernilai -1 (untuk elemen yang dimulai dengan index 0), maka berarti stack dalam keadaan empty (kosong) yang akan me-return-kan true (1) dan jika tidak berarti stack mempunyai isi dan me-return-kan nilai false (0)

B. Operasi IsFull pada stack yang menggunakan single linked list. Karena dalam linked list bersifat dinamis, maka pengecekan isFull adalah dengan memeriksa apakah memori masih dapat digunakan untuk alokasi sebuah elemen stack. Jika alokasi dapat dilakukan, maka berarti memori masih belum penuh dan proses push dapat dilakukan. Tetapi jika alokasi memori gagal dilakukan, maka berarti memori penuh dan tidak bisa menambah lagi elemen stack.  

 Operasi Push

Operasi push adalah operasi dasar dari stack. Operasi ini berguna untuk menambah suatu elemen data baru pada stack dan disimpan pada posisi top yang akan mengakibatkan posisi top akan berubah. Langkah operasi ini adalah :

a.    Operasi push pada stack yang menggunakan array.

Langkah operasi push dalam array adalah dengan :

*        Periksa apakah stack penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.

*        Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru.

 

b.     Operasi push pada stack yang menggunakan single linked list Operasi push pada stack yang menggunakan single linked list adalah sama dengan proses tambahawal pada operasi linked list. Langkah-langkahnya adalah :

*        Periksa apakah memori penuh (isfull). Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan. 

*        Proses push-nya sendiri adalah dengan cara mengalokasikan suatu elemen linked list (disebut variable baru), kemudian periksa jika stack dalam keadaan kosong maka pointer yang menunjuk ke awal stack diisi dengan pointer baru, dan jika dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru. Tetapi jika pointer penunjuk stack sudah menunjuk ke suatu data, maka sambungkan field pointer bawah (penunjuk ke data sebelumnya) dari pointer baru ke pointer penunjuk posisi akhir stack (top) dan kemudian pindahkah pointer penunjuk posisi akhir stack ke pointer baru. 

  

  

Operasi Pop

Operasi pop adalah salah satu operasi paling dasar dari stack. Operasi ini berguna untuk mengambil elemen terakhir (top) dan kemudian menghapus elemen tersebut sehingga posisi top akan berpindah. Operasi ini biasanya dibuat dalam bentuk function yang me-return-kan nilai sesuai data yang ada di top.

Ini adalah contoh program Stack yang pernah dilakukan dalam Praktikum Struktur data:

#include <iostream.h>
#include <conio.h>
#include <string.h>
struct
{
          char data [15][100], max [15];
          int i,j;
}
stack;
void isi () // push untuk memasukan data
{
          stack.i++;
          cout<<”masukan data: “;
          cin>>stack.max;
          strcpy (stack.data[stack.i],stack.max);
}
void buang () // pop untuk mengambil data
{
          if (stack.i>0)
          {
                cout<<”data yang terambil: “<<stack.data[stack.i]<<endl;
                     stack.i–; stack.j–;
          }
          else
                cout<<”tak ada data yang terambil”<<endl;
}
void muncul (int n)//print untuk menampilkan data
{
          if (stack.j>0)
          {
                for (int e=n; e>=1; e–)
                {
                     cout<<stack.data[e]<<endl;
                }
          }
          else
          cout<<”tak ada data tersimpan”<<endl;
}
void hapus () // clear untuk menghapus data
{
          stack.j=0; stack.i=0;
}
void main ()
{
          int n,plh;
          awal:
          clrscr();
          cout<<”contoh program stack (tumpukan)\n\n”;
          cout<<”maksimal tumpukan data: “; cin>>n;
          stack.data[n];
          stack.i=0;
          stack.j=0;
          pilihan:
          clrscr();
          cout<<”\n1. push \n2. pop \n3. print \n4. clear \n5. quit \n”;
          cout<<”\npilih :”; cin>>plh;
          cout<<”\n”;
          if (plh==1)
                {
                     if (stack.j<n)
                     {
                          stack.j++; isi();
                     }
                     else
                     {
                          cout<<”tumpukan penuh”<<endl; getch();
                     }
                     goto pilihan;
          }
          else if (plh==2)
          {
                     buang(); getch(); goto pilihan;
          }
          else if (plh==3)
          {
                     muncul (stack.i); getch(); goto pilihan;
          }
          else if (plh==4)
          {
                     hapus();  getch(); goto pilihan;
          }
          else if (plh==5)
          {
                     getch(); goto awal;
          }
          else
          {
                     cout<<”input yang anda masukan salah !!!”;
                     getch(); goto awal;
          }
}