Rumahit.ID - Stack disebut juga tumpukan dimana data hanya dapat dimasukkan dan diambil dari satu sisi. Karena itu, stack bersifat LIFO (Last In First Out).
Tumpukan bisa diartikan sebagai suatu kumpulan data yang seolah-olah ada data yang diletakkan diatas data yang lain. Satu hal yang perlu diingat bahwa kita bisa menambah (menyisipkan) data, dan mengambil (menghapus) data melalui ujung yang sama, yang disebut ujung atas tumpukan (top of stack). Tumpukan dapat diilustrasikan sebagai berikut:

Secara sederhana tumpukan bisa diilustrasikan seperti gambar dibawah ini. Dari gambar dibawah ini kotak B ada di atas kotak A dan ada di bawah kotak C. Gambar dibawah ini hanya menunjukan bahwa dalam tumpukan hanya bisa menambah atau mengambil sebuah kotak lewat satu ujung yaitu ujung bagian atas. Dapat dilihat bahwa tumpukan merupakan suatu senarai (list) yang mempunyai watak “masuk terakhir keluar pertama"(last in first out-LIFO).

Tumpukan Dengan 6 Elemen

Implementasi alternatif stack adalah:

1. List dengan pointer untuk variable-length stack (ukuran stack bervariasi)

2. Array untuk fixed-length stack (ukuran stack sudah dibatasi, tidak dapat tumbuh)

Stack banyak digunakan dalam bidang ilmu komputer, misalnya dalam pengembangan kompilator, pengelolaan backtracking untuk parser dan sebagainya.

Stack terdiri dari elemen S[1..top], dimana S[1] adalah elemen pada dasar stack dan S[top] adalah elemen pada puncak stack. Jika top=0 berarti stack kosong. Jika top = N, dimana N adalah jumlah elemen terbanyak yang dapat ditampung, berarti stack sudah penuh. Jika stack sudah penuh tidak bias dilakukan penyisipan elemen baru. Pada stack yang diimplementasikan dengan list, ukurannya bisa tidak terbatas (unbounded stack) kecuali batasan ruang memori yang tersedia. Pada unbounded stack pemeriksaan yang diperlukan adalah pemeriksaan apakah masih ada ruang memori yang tersedia untuk elemen yang baru. Stack yang diimplementasikan dengan array disebut fixed length stack karena ukurannya tidak bisa berubah, sedangkan stack yang diimplementasikan dengan list disebut variable-length stack, karena ukurannya bisa berubah-ubah sesuai dengan penambahan dan penghapusan elemen-elemennya.

Operasi yang dapat dilakukan stack adalah:

• Menambah (push)

• Mengambil (pop)

• mengecek apakah stack penuh (isFull)

• mengecek apakah stack kosong (isEmpty)

• membersihkan stack (clear).

• Mencetak isi stack (print)

Operasi - Operasi Pada Stack

Membuat stack dan operasi-operasi yang dapat dilakukannya.

1. Mendefinisikan stack dengan menggunakan struct

typedef struct stack // Mendefinisikan stack dengan menggunakan struct
{
int top;
char data [15][20]; // menampung 15 data dengan jumlah string max 20 huruf
};

2. Mendefinisikan max_stack untuk maksimum isi stack

#define max_stack 15

3. Membuat variable array sebagai implementasi stack

stack tumpuk;

4. Mendeklarasikan operasi-operasi/fungsi yang dapat dilakukan stack.

a. Push (menginputkan data pada stack)

void push(char d[20])
{
tumpuk.top++;
strcpy(tumpuk.data[tumpuk.top],d);
printf("data berhasil dimasukkan");
}

b. Pop (mengambil data pada stack)

void pop()
{
printf ("data %s terambil",tumpuk.data[tumpuk.top]);
tumpuk.top--;
}

c. IsFull (mengecek apakah stack penuh)

int isFull()
{
if (tumpuk.top==max_stack-1)
return 1;
else return 0;
}

d. isEmpty (mengecek apakah stack kosong)

int isEmpty()
{
if (tumpuk.top==-1)
return 1;
else return 0;
}

e. clear (membersihkan seluruh isi stack)

void clear()
{
tumpuk.top=-1;
printf("semua data terhapus.");
}

f. print (mencetak seluruh isi stack)

void print()
{
for (int i=tumpuk.top;i>=0;i--)
printf ("%s\n",tumpuk.data[i]);
}

Operasi push dengan Single Stack

Operasi push merupakan proses penyisipan/pemasukan data ke dalam suatu tumpukan. Dimana tumpukan tersebut akan dicek, apakah sudah penuh atau belum. Jika sudah penuh, maka data tidak akan dimasukkan ke dalam tumpukan, tetapi jika masih kosong maka data akan disisipkan di tumpukkan paling atas.

Operasi pop adalah operasi untuk menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan.

Double Stack Dengan Array

Double stack merupakan suatu teknik khusus yang dikembangkan untuk menghemat memori dalam pembuatan dua stack dengan array. Intinya adalah penggunaan hanya sebuah array untuk menampung dua stack.

Gambaran Perbandingan Single Stack dan Doube Stack Dengan Array

Tampak jelas pada gambar di atas bahwa sebuah array daspat dibagi untukk dua stack, stack 1 bergerak ke kanan dan stack 2 bergerak ke kiri. Jika Top 1 (elemen teratas dari stack 1) bertemu dengan top2 (elemen teratas dari stack 2), maka double stack telah penuh.

Pemanfaatan STACK

Salah satu pemanfaatan stack adalah untuk menulis ungkapan dengan menggunakan notasi tertentu. Seperti kita ketahui, dalam penulisan ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu. Perhatikan ungkapan berikut ini :

( C + D ) * ( E – F )

Dari contoh di atas ( C + D ) akan dikerjakan lebih dahulu, kemudian ( E – F ) dan hasilnya akan dikalikan

Cara penulisan ungkapan sering disebut dengan notasi INFIX, yang artinya bahwa operator ditulis diantara 2 operand.

Seorang ahli matematika bernama Jan lukasiewiccz kemudian mengembangkan suatu cara penulisan ungkapan numeris yang kemudian dikenal dengan nama notasi PREFIX, yang artinya adalah bahwa operator ditulis sebelum kedua operand yang akan disajikan.

Notasi lain, yang merupakan kebalikan dari notasi PREFIX adalah notasi POSTFIX,

Operator ditulis sesudah operand.

Contoh Notasi INFIX, PREFIX dan POSTFIX

Program Konversi Bentuk INFIX ke bentuk POSTFIX

/*Program:InfixPostfix.cpp */ 
#include <stdio.h>
#include <conio.h> 
#include <ctype.h> 
char A[25], S[20];
int I, Top;
int Operand(char Top); // fungsi memeriksa operand 
int Operator(char Op); // fungsi memeriksa operator
int Nilai(char X); // fungsi mencari nilai numerik sebuah karakter 
void main()
{ char OprStack, OprBaru;
    Top = -1;
    clrscr();
    printf("Arithmetic Statement : "); scanf("%s",A); 
    for (I=0; A[I] != '\0'; I++ )
      { if (Operand(A[I])) 
          printf("%c", A[I]); 
      else { if(Operator(A[I]))
      { if(Top==-1 || S[Top] == '(' ) S[++Top] = A[I];
      else { OprStack = S[Top]; OprBaru = A[I]; 
      if (Nilai(OprBaru) > Nilai (OprStack)) 
         S[++Top] = OprBaru;
      else
      { while(Nilai(OprStack) >= Nilai (OprBaru) && Top > -1 && S[Top] != '(' )
        { printf("%c ", OprStack);
        OprStack = S[--Top]; } 
        S[++Top] = OprBaru; }
        }
      }
      else { if(Operand(A[I])=='(') 
         S[++Top]=A[I]; 
      else { while (Top>-1 && S[Top] != '(' )
         { printf("%c ", S[Top--] ); } 
         Top-- ;
         }
      } }
      }
while (Top > -1) 
        printf("%c ", S[Top--]);
}

int Operand(char Op) // Fungsi Memeriksa Operand
{ if(isalpha(Op))
    return(-1); //True 
    else return(0); //False
}
int Operator(char Opr) // Fungsi memeriksa Operator
{ if(Opr=='^' || Opr=='*' || Opr=='/' || Opr=='+' || Opr=='-') 
    return(-1);
else return(0);
}

int Nilai (char X) // Fungsi memeriksa Operator
{ if (X=='^') 
    return(3);
else if(X=='*' || X=='/') 
    return(2); 
else if(X=='+' || X=='-') 
    return(1); 
else return(0);
}

Daftar Pustaka :

Andri Kristanto, Algoritma & Pemrograman dengan C++ Edisi 2, Graha Ilmu, Yogyakarta, 2009.
Moh. Sjukani, Struktur Data [ Algoritma & Struktur Data 2 ] dengan C, C++, Mitra Wacana Media, Jakarta, 2008.
Teddy Marcus Zakaria dan Agus Prijono, Konsep dan Implementasi Struktur Data, Informatika, Bandung, 2006
MODUL PERKULIAHAN Algoritma Pemrograman dan Struktur Data Universitas Gunadarma
.

Baru