�ݺ�ߣ

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah
BAGIAN IIIBAGIAN III

StackStack

StackStack
•Sistem penyimpanan data dengan
mekanisme Last In First Out (LIFO).
•Satck merupakan tipe data abstrak
yang banyak digunakan dalam Compiler,
String processing dan berbagai algoritma
untuk graph.

StackStack
TOP
D merupakan elemen yang terakhir masuk
dan
akan menjadi elemen yang pertama keluar
A
B
C
D
PUSH PULL

StackStack
Operasi dalam Stack
1. Create( )
Menciptakan Stack baru dalam keadaan kosong.
2. Push(e)
Memasukkan data baru dari variabel e kedalam Stack.
3. Pull(*e)
Mengambil data dari Stack untuk disimpan di variabel e.
4. Empty( )
Memeriksa apakah Stack dalam keadaan kosong.
5. Full( )
Memeriksa apakah Stack dalam keadaan penuh.
6. Clear( )
Menghapus semua data yang ada dalam Stack.

StackStack
Implementasi Stack dengan Array
#define pj_max 7
typedef char elemen_type;
elemen_type Stack[pj_max];
int Top;
void create()
{
Top = 0;
}

StackStack
int full()
{
if (Top == pj_max-1)
return 1; else return 0;
}
int empty()
{
if (Top == 0)
return 1; else return 0;
}

StackStack
void Push(elemen_type e)
{
if (!full){Top++; Stack[Top] = e;};
}
void Pull(elemen_type *e)
{
if (!empty){*e = Stack[Top]; Top--;};
}
void clear()
{
Top = 0;
}

StackStack
0
0
0
0
0
0
TOP[0]
[1]
[2]
[3]
[4]
[5]
[6]
Create( );

StackStack
0
0
0
90
70
30
TOP
0
0
0
90
70
30
TOP
0
0
35
90
70
30
TOP
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
Sebelum Push TOP++ Stack[TOP] = e
Proses Push(35);

StackStack
0
0
35
90
70
30
TOP
0
0
35
90
70
30
TOP
0
0
35
90
70
30
TOP
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
[0]
[1]
[2]
[3]
[4]
[5]
[6]
Sebelum Pull *e = Stack[TOP] TOP--
Proses Pull(*e);

StackStack
Implementasi Stack dengan Linked list
• Operasi Push()
menggunakan Insert Depan
• Operasi Pull()
menggunakan Delete dibagian Head
• Pointer Head berfungsi sebagai TOP

StackStack
Dibandingkan dengan implementasi Stack dengan array,
implementasi Stack dengan linked list mempunyai:
Keuntungan:
1. Kapasitas Stack hanya dibatasi oleh kapasitas memori komputer.
2. Penggunaan memori tergantung dari banyaknya data.
Kerugian:
1. Operasi Clear memerlukan lebih banyak langkah.

StackStack
Masih ingat soal dibawah ini ?
Buat suatu program yang dapat memeriksa
apakah pasangan simbol kurung {} [] dan (),
sudah benar.
Contoh:
1. {[()][()]} benar
2. [{()]} salah
3. [{()()}] benar
4. {[())()]} salah

StackStack
int Setangkup(char StrKurung[])int Setangkup(char StrKurung[])
{{
int L,I,S; char X;int L,I,S; char X;
L = strlen(StrKurung); I=0; S=true;L = strlen(StrKurung); I=0; S=true;
CreateStack();CreateStack();
dodo
{{
switch (StrKurung[I])switch (StrKurung[I])
{{
case '(' : Push(StrKurung[I]); break;case '(' : Push(StrKurung[I]); break;
case '[' : Push(StrKurung[I]); break;case '[' : Push(StrKurung[I]); break;
case '{' : Push(StrKurung[I]); break;case '{' : Push(StrKurung[I]); break;
case ')' : Pop(&X); if (X != '(') S = false; break;case ')' : Pop(&X); if (X != '(') S = false; break;
case ']' : Pop(&X); if (X != '[') S = false; break;case ']' : Pop(&X); if (X != '[') S = false; break;
case '}' : Pop(&X); if (X != '{') S = false; break;case '}' : Pop(&X); if (X != '{') S = false; break;
}}
I++;I++;
} while (S && I<L);} while (S && I<L);
if (!EmptyStack()) S=false;if (!EmptyStack()) S=false;
return S;return S;
}}

StackStack
EVALUASI INFIX
Mendapatkan nilai dari suatu ekspresi numerik
yang ditulis dalam notasi Infix.
Contoh:
a.a. 2 + 3,2 + 3, hasilnya adalah 5hasilnya adalah 5
b.b. 2 + 3 * 5,2 + 3 * 5, hasilnya adalah 17hasilnya adalah 17
c.c. (2 + 3) * 5,(2 + 3) * 5, hasilnya adalah 25hasilnya adalah 25
d.d. (2 + 3) * (15 – 10),(2 + 3) * (15 – 10), hasilnya adalah 25hasilnya adalah 25

Notasi Infix, Postfix dan PrefixNotasi Infix, Postfix dan Prefix
Notasi InfixNotasi Infix Notasi PostfixNotasi Postfix Notasi PrefixNotasi Prefix
A + BA + B A B +A B + + A B+ A B
A + B * CA + B * C A B C * +A B C * + + A * B C+ A * B C
(A+B)*(C-D)(A+B)*(C-D) AB+CD-*AB+CD-* *+AB-CD*+AB-CD
(A + B) * C(A + B) * C A B + C *A B + C * * + A B C* + A B C

Notasi Infix, Postfix dan PrefixNotasi Infix, Postfix dan Prefix
Latihan:
Lakukan konversi dari notasi Infix dibawah ini
ke notasi Prefix dan notasi Postfix.
1. A + B x C + D / E
2. A * (R + (C – D)) * (E – F) + T
3. (B * B – 4 * A * C) / (2 * A)

Operand dan OperatorOperand dan Operator
A + B * C
Operator
O p e r a n d

Konversi Infix ke PostfixKonversi Infix ke Postfix
Create Stack
Kosongkan string Postfix
Tambahkan simbol ‘)’ ke ujung string Infix
Push( ‘(’ )
While (Not Empty Stack)
{
Baca simbol dari string Infix
Switch (simbol)
{
case operand: Tambahkan simbol ke ujung string Postfix
case operator: While (prcd(Stack[Top], simbol) == true)
{
Pop(X)
Tambahkan X ke ujung string Postfix
}
Push(simbol)
case ‘(‘ : Push(simbol)
case ‘)’ : While (Stack[Top] != ‘(‘ )
{
Pop(X)
Tambahkan X ke ujung string Postfix
}
Pop(X) // Buang simbol ‘(‘
} // akhir dari Switch
} // akhir dari While
Selesai.

PrecedencePrecedence
Operator Nilai
Prcd(’^’ , ’x’) True
Prcd(’x’ , ’+’) True
Prcd(’x’ , ’x’) True
Prcd(’+’ , ’+’) True
Prcd(’+’ , ’-’) True
Prcd(’-’ , ’-’) True
Prcd(’x’ , ’^’) False
Prcd(’+’ , ’x’) False
Prcd(’-’ , ’+’) False
Prcd(’-’ , ’x’) False
dst.

PrecedencePrecedence
Keterangan:
‘^’ = Tanda pangkat
Bila operator tidak terdefinisi, maka
nilainya False, contoh:
Prcd(’(’ , ’+’)= False.

Konversi Infix ke postfixKonversi Infix ke postfix
ContohContoh::
String Infix:String Infix: 6 + 2 * 2 + 72 / 86 + 2 * 2 + 72 / 8
String Infix:String Infix: (6 + 2) * (2 + 72 )/ 8(6 + 2) * (2 + 72 )/ 8

Evaluasi PostfixEvaluasi Postfix
1. Scan string Postfix dari kiri ke kanan.
2. Bila ketemu operand, Push(operand).
3. Bila ketemu operator,
3.1. Pop dua kali yaitu Pop(X) dan Pop(Y).
3.2. Z = Y operator X.
3.3. Push(Z).
4. Ulangi 2 s/d 3.3 hingga seluruh simbol
didalam string terbaca.

Evaluasi InfixEvaluasi Infix
Tidak bisa langsung.Tidak bisa langsung.
Harus melalui:Harus melalui:
• Konversi Infix ke PostfixKonversi Infix ke Postfix
• Evaluasi PostfixEvaluasi Postfix
• SelesaiSelesai

�ݺ�ߣ

Struktur data 03 (stack)

More Related Content

Struktur data 03 (stack)