stack - struktur data

POLITEKNIK PIKSI GANESHABANDUNG2011

PENGERTIAN STACK

Secara sederhana diartikan dengan : sebagai tumpukan dari benda sekumpulan data yang seolah-olah

diletakkan di atas data yang lain koleksi dari objek-objek homogen

Dengan konsep utamanya adalah LIFO

Last In First Out

BOS (Bottom of Stack)

K

C A T S

PUSH

POPTOS (TOP of Stack)

TOS (TOP of Stack)

ILUSTRASI

OPERASI PADA STACK

2 operasi dasar yang bisa dilaksanakan

pada sebuah stack, yaitu: Operasi Push (menyisipkan data)

memasukkan data ke dalam stack Operasi Pop (menghapus data)

menghapus elemen yang terletak pada posisi paling atas dari sebuah stack

OPERASI PADA STACK

Operasi Push

void Push (NOD **T, char item){

NOD *n;n=NodBaru (item);n->next=*T;*T=n;

}

OPERASI PADA STACK

Operasi Pop

char Pop (NOD **T){

NOD *n; char item;if (!StackKosong(*T)) {

P=*T;*T=(*T)->next;item=P->data;free(P);

}return item;

}

Operasi Lainnya

Misal dalam Pascal di deklarasikan :

Const Max = 4; Type TipeData = byte; Stack = array [1..Max] of TipeData Var Top : TipeData;

Maka,

Buat Stack (Create)

membuat stack baru yang masih kosong

Procedure Create; Begin Top := 0; End;

Konsepnya adalah bahwa Top menunjukkan tingginya tumpukkan stack. Jika tinggi Top adalah 0, berarti tumpukan kosong. Prosedur ini digunakan juga dalam penghapusan isi stack (Clear).

1

0

3

4

2

Stack Kosong (empty)

mengecek apakah stack dalam keadaan kosong atau tidak

Function Empty : Boolean; Begin Empty := False; If Top := 0 then Empty := True; End;

Stack Penuh (Full)

mengecek apakah stack dalam keadaan penuh atau tidak

Function Full : Boolean; Begin Full := False; If Top = Max then Full := True; End;

Implementasi Stack Menggunakan Array (C)

/*Stack menggunakan array*/

#include <stdio.h>

#include <conio.h>

#define max 50

#define True 1

#define False 0

int top=0, stack[max];

void buatstack();

int stackkosong ();

int stackpenuh ();

void push (int IB);

void pop ();

void cetakstack ();

void main ()

{

buatstack ();

push (10);

push (76);

push (12);

push (21);

cetakstack ();

getche;

printf (“\n\n”);

pop ();

pop ();

pop ();

cetakstack ();

getche();

}

void buatstack ()

{ stack[top] = 0; }

int stackkosong ()

{ if (top==0)

return (True);

else

return (False); }

int stackpenuh ()

{ if (top==max)

return (True);

else

return (False); }

void push (int IB)

{ if (stackpenuh() )

printf (“stack overflow \n”);

else

{ top++;

stack[top] = IB;

stack[0] = top; } }

void pop ()

{ int IP;

if (stackkosong() )

printf (“stack underflow \n”);

else

{ IP = stack[top];

top --;

stack[0] = top; } }

void cetakstack();

{ int i = 1;

while ( i <=top )

{printf (“%d\n”, stack [i]);

i++; } }

Catatan

Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita melakukan operasi POP terhadap stack kosong.

Pada pascal, Eon adalah elemen yang akan dimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari dalam stack.

Implementasi Stack Menggunakan Record (C)

/*Stack menggunakan record*/

#include <stdio.h>

#include <alloc.h>

#include <conio.h>

#define max 50

#define True 1

#define False 0

Typedef struct typestack { int top;

int elemen [max];

};

void buatstack();

void cetakstack ();

void push (int IB);

void pop ();

int stack kosong ();

int stack penuh ();

void main ()

{

buatstack ();

push (10);

push (76);

push (12);

push (1);

cetakstack ();

printf (“\n\n”);

pop ();

pop ();

pop ();

cetakstack ();

getche();

}

void buatstack ()

{ stack.top = -1; }

int stackkosong ()

{ if (stack.top==-1)

return (True);

else

return (False); }

int stackpenuh ()

{if (stack.top==max)

return (True);

else

return (False); }

void push (int IB)

{ if (stackpenuh() )

printf (“stack overflow \n”);

else

{ stack.top++;

stack.elemen [stack.top] = IB; } ;

void pop ()

{ int IP;

if (stackkosong() )

printf (“stack underflow \n”);

else

{ IP = stack.elemen [stack.top];

stack.top--; } ; }

void cetakstack();

{ int i = 0;

while ( i <= stack.top )

{ printf (“%d\n”, stack.elemen[i]);

i++; } }