- Get link
- Other Apps
Sebelum kita mempelajari tentang stack,
kita harus tau dulu apa itu stack. Stack adalah tumpukan. Stack menggunakan
prinsip LIFO (Last in First Out) yaitu data yang disimpan (push) terakhir akan
diambil (pop) lebih dulu.
Berikut
ini contoh pembalik kalimat yang menggunakan konsep stack
Kata “STRUKTUR DATA” jika dibalik akan
menjadi “ATAD RUTKURTS”. Kata tersebut dikategorikan bukan palindrom. Palindrom
adalah sebuah kata, frasa, angka maupun susunan lainnya yang dapat dibaca
dengan sama baik dari depan maupun belakang. Kita dapat membuat program
pengecekan palindrom, salah satunya menggunakan C++. Berikut ini source code
nya.
#include <iostream>
#include <string>
using namespace std;
class tumpukan{
public:
tumpukan(){
//buat link list kosong
head=NULL;
tail=NULL;
size=0;
}
//menambahkan data pada stack/membuat node baru
void push(char a){
//buat node baru
node* tmp = new node;
//masukkan data ke node
tmp->data = a;
//tentukan node setelahnya
tmp->next = NULL;
//jika LL kosong
if(size==0){
//head dan tail adalah node yg baru dibuat
head = tmp;
tail = tmp;
//node sebelumnya belum ada
tail->prev = NULL;
}
//jika LL tidak kosong
else{
//node setelah tail adalah node baru
tail->next = tmp;
//node sebelum node baru adalah tail
tmp->prev = tail;
//pindahkan tail ke node baru
tail = tmp;
}
//jumlah node bertambah
size++;
}
//mengambil data dan menghapus node yang terakhir
char pop(){
//ambil data di tail
data = tail->data;
if(head==tail){
delete head;
}
else{
//akses tail
node* tmp = tail;
//pindah tail
tail = tail->prev;
//hapus link
tail->next = NULL;
tmp->prev = NULL;
//hapus mantan tail (tmp)
delete tmp;
}
size--;
return data;
}
private:
struct node{
char data;
node* next;
node* prev;
};
node* head;
node* tail;
int size;
char data;
};
class antrian{
public:
antrian(){
//buat link list kosong
head=NULL;
tail=NULL;
size=0;
}
//menambahkan data pada stack/membuat node baru
void push(char a){
//buat node baru
node* tmp = new node;
//masukkan data ke node
tmp->data = a;
//tentukan node setelahnya
tmp->next = NULL;
//jika LL kosong
if(size==0){
//head dan head adalah node yg baru dibuat
head = tmp;
tail = tmp;
//node selanjutnya belum ada
head->prev = NULL;
}
//jika LL tidak kosong
else{
//node setelah head adalah node baru
tail->next = tmp;
//node sebelum node baru adalah head
tmp->prev = tail;
//pindahkan head ke node baru
tail = tmp;
}
//jumlah node bertambah
size++;
}
//mengambil data dan menghapus node yang pertama
char pop(){
//ambil data di head
data = head->data;
if(head==tail){
delete head;
}
else{
//akses head
node* tmp = head;
//pindah head
head = head->next;
//hapus link
head->prev = NULL;
tmp->next = NULL;
//hapus mantan head (tmp)
delete tmp;
}
size--;
return data;
}
private:
struct node{
char data;
node* next;
node* prev;
};
node* head;
node* tail;
int size;
char data;
};
int main() {
//membuat stack
tumpukan s;
//membuat queue
antrian q;
//membuat variabel bool palindrome
bool palindrome = true;
cout<<"Pengecekan Palindrome"<<endl<<endl;
//membuat variabel penampungan kata
string kata;
//meminta user memasukkan kata
char a,b,c;
do{
cout<<"Masukkan kata : ";cin>>kata;cout<<endl;
//loop untuk memasukkan semua isi dari string kata ke stack dan queue
for(int i=0;i<kata.length();i++){
s.push(kata[i]);
q.push(kata[i]);
}
//loop untuk membandingkan hasil popping dari stack dan queue
for(int l = 0;l<kata.length();l++){
//jika keluaran popping berbeda
a = q.pop(); b = s.pop();
if(a != b){
cout<<a<<" != "<<b<<endl;
palindrome = false;
}
else{
cout<<a<<" == "<<b<<endl;
}
}
//jika semua hasil perbandingan popping stack dan queue sama
if(palindrome == true){
cout<<"Kata tersebut adalah kata palindrome";
}
else{
cout<<"Kata tersebut tidak palindrome";
}
cout<<"\n\nCek kata lainnya ? (Y/N)";cin>>c;cout<<endl;
}while(c == 'Y' || c == 'y');
cout<<endl;
system("pause");
return 0;
}
#include <iostream>
#include <string>
using namespace std;
class tumpukan{
public:
tumpukan(){
//buat link list kosong
head=NULL;
tail=NULL;
size=0;
}
//menambahkan data pada stack/membuat node baru
void push(char a){
//buat node baru
node* tmp = new node;
//masukkan data ke node
tmp->data = a;
//tentukan node setelahnya
tmp->next = NULL;
//jika LL kosong
if(size==0){
//head dan tail adalah node yg baru dibuat
head = tmp;
tail = tmp;
//node sebelumnya belum ada
tail->prev = NULL;
}
//jika LL tidak kosong
else{
//node setelah tail adalah node baru
tail->next = tmp;
//node sebelum node baru adalah tail
tmp->prev = tail;
//pindahkan tail ke node baru
tail = tmp;
}
//jumlah node bertambah
size++;
}
//mengambil data dan menghapus node yang terakhir
char pop(){
//ambil data di tail
data = tail->data;
if(head==tail){
delete head;
}
else{
//akses tail
node* tmp = tail;
//pindah tail
tail = tail->prev;
//hapus link
tail->next = NULL;
tmp->prev = NULL;
//hapus mantan tail (tmp)
delete tmp;
}
size--;
return data;
}
private:
struct node{
char data;
node* next;
node* prev;
};
node* head;
node* tail;
int size;
char data;
};
class antrian{
public:
antrian(){
//buat link list kosong
head=NULL;
tail=NULL;
size=0;
}
//menambahkan data pada stack/membuat node baru
void push(char a){
//buat node baru
node* tmp = new node;
//masukkan data ke node
tmp->data = a;
//tentukan node setelahnya
tmp->next = NULL;
//jika LL kosong
if(size==0){
//head dan head adalah node yg baru dibuat
head = tmp;
tail = tmp;
//node selanjutnya belum ada
head->prev = NULL;
}
//jika LL tidak kosong
else{
//node setelah head adalah node baru
tail->next = tmp;
//node sebelum node baru adalah head
tmp->prev = tail;
//pindahkan head ke node baru
tail = tmp;
}
//jumlah node bertambah
size++;
}
//mengambil data dan menghapus node yang pertama
char pop(){
//ambil data di head
data = head->data;
if(head==tail){
delete head;
}
else{
//akses head
node* tmp = head;
//pindah head
head = head->next;
//hapus link
head->prev = NULL;
tmp->next = NULL;
//hapus mantan head (tmp)
delete tmp;
}
size--;
return data;
}
private:
struct node{
char data;
node* next;
node* prev;
};
node* head;
node* tail;
int size;
char data;
};
int main() {
//membuat stack
tumpukan s;
//membuat queue
antrian q;
//membuat variabel bool palindrome
bool palindrome = true;
cout<<"Pengecekan Palindrome"<<endl<<endl;
//membuat variabel penampungan kata
string kata;
//meminta user memasukkan kata
char a,b,c;
do{
cout<<"Masukkan kata : ";cin>>kata;cout<<endl;
//loop untuk memasukkan semua isi dari string kata ke stack dan queue
for(int i=0;i<kata.length();i++){
s.push(kata[i]);
q.push(kata[i]);
}
//loop untuk membandingkan hasil popping dari stack dan queue
for(int l = 0;l<kata.length();l++){
//jika keluaran popping berbeda
a = q.pop(); b = s.pop();
if(a != b){
cout<<a<<" != "<<b<<endl;
palindrome = false;
}
else{
cout<<a<<" == "<<b<<endl;
}
}
//jika semua hasil perbandingan popping stack dan queue sama
if(palindrome == true){
cout<<"Kata tersebut adalah kata palindrome";
}
else{
cout<<"Kata tersebut tidak palindrome";
}
cout<<"\n\nCek kata lainnya ? (Y/N)";cin>>c;cout<<endl;
}while(c == 'Y' || c == 'y');
cout<<endl;
system("pause");
return 0;
}
Salah satu penerapan stack yaitu kita bisa mengubah bilangan desimal ke biner, oktal, dan heksadesimal. Berikut ini source codenya:
#include<stdio.h>
#include<conio.h>
int MAXSTACK;
typedef int itemtype;
typedef struct
{
itemtype item[300];
int count;
}stack;
void initializestack(stack *s)
{
s->count = 0;
}
int empty(stack *s)
{
return (s->count == 0);
}
int full(stack *s)
{
return (s->count == MAXSTACK);
}
void push(itemtype x, stack *s)
{
if(full(s))
printf("stack penuh !\n");
else
{
s->item[s->count]=x;
++(s->count);
}
}
int pop(stack *s)
{
if(empty(s))
printf("stack kosong\n");
else
{
--(s->count);
return (s->item[s->count]);
}
return 0;
}
//deklarasi
int i, n, m, o,p,pilih;
int input;
stack tumpukan;
void biner();
void oktal();
void heksa();
main()
{
printf("-------konversi desimal ke biner oktal dan heksadesimal------\n");
printf("------------------ PRIMA ADI P / M0509056 -------------------\n");
initializestack(&tumpukan);
printf("\nmasukkan bilangan desimal = ");
scanf("%d", &input);
printf("\n---MENU---\n");
printf("1 untuk konversi ke biner\n");
printf("2 untuk konversi ke oktal\n");
printf("3 untuk konversi ke heksa\n");
printf("4 untuk keluar");
while(pilih<4){
printf("\n\npilih : ");
scanf("%d",&pilih);
switch(pilih)
{
case 1:
printf("bilangan binernya\n");
biner();break;
case 2:
printf("bilangan oktalnya\n");
oktal();break;
case 3:
printf("bilangan heksadesimalnya\n");
heksa();break;
case 4:
printf("--silahkan tekan enter sekalilagi");
}}
getch();
return 0;
}
//ke oktal
void oktal(){
for(o=1,n=input;n>0;n=n/8,o++)
{
MAXSTACK=o;
m=n%8;
push(m,&tumpukan);
}
for(i=MAXSTACK;i>0;i--)
{
printf("%d", pop(&tumpukan));
}
}
//ke biner
void biner(){
for(o=1,n=input;n>0;n=n/2,o++)
{
MAXSTACK=o;
m=n%2;
push(m,&tumpukan);
}
for(i=MAXSTACK;i>0;i--)
{
printf("%d", pop(&tumpukan));
}
}
//ke heksa desimal
void heksa()
{
for(o=1,n=input;n>0;n=n/16,o++)
{
MAXSTACK=o;
m=n%16;
push(m,&tumpukan);
}
for(i=MAXSTACK;i>0;i--)
{
p=pop(&tumpukan);
if(p<=9)
printf("%d",p);
else if(p==10)printf("A");
else if(p==11)printf("B");
else if(p==12)printf("C");
else if(p==13)printf("D");
else if(p==14)printf("E");
else if(p==15)printf("F");
}
}
Didalam stack, dikenal istilah infix, prefix, dan postfix. Perbedaan ketiganya adalah:
-
Prefix
adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa
menuliskan tanda kurung. Contoh : +AB, –
+ABC, * + AB – CD.
- Infix
adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand
dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi. Contoh :
A+B, A+B-C, (A+B)*(C-D).
- Postfix
adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa
menuliskan tanda kurung. Contoh : AB + , AB + C – , AB + CD -*.
Untuk mengubah
infix menjadi postfix menggunakan stack dengan aturan:
-
Notasi
infix dibaca satu per satu
-
Jika berupa
operand maka langsung dicetak dan tidak disimpan
-
Stack hanya
digunakan untuk menyimpan operator
-
Operator
mempunyai tingkatan level dengan urutan (dari level tertinggi ke terendah) :
‘^’, ‘*’ dan ‘/’, ‘+’ dan ‘-’
Jika
operator, maka mengikuti aturan sbb:
-
Jika notasi
‘(‘ PUSH ke stack
-
Jika notasi
‘)’ POP dan cetak s/d tanda ‘)’ tetapi tidak dicetak
-
Jika
operator, cek bila stack Kosong atau level operator > level operator TOS
maka PUSH
-
Lainnya POP
dan cetak lalu PUSH, ulangi perbandingan
-
Jika notasi
infix sudah berakhir, POP stack sampai Kosong
Contoh:
Penjelasan:
- ‘(‘ disimpan pada stack karena
merupakan push
- A langsung dicetak karena merupakan
operand
- ‘+’ masuk ke stack dan tetap mencetak A
karena belum ada tanda POP
- B langsung dicetak karena merupakan
operand
- ‘)’ merupakan tanda POP, sehingga
mencetak operasi sebelumnya
- ‘*’ masuk ke stack tetapi tidak dicetak
karena termasuk operator
- C (operand terakhir) langsung dicetak dan
menghasilkan AB+C*
Kita juga bisa melakukan operasi notasi postfix menggunakan stack dengan cara:
1. Baca notasi postfix satu per satu
2. Jika notasi adalah operan maka PUSH ke
stack
3. Jika notasi adalah operator maka
- POP ke OpRight
- POP ke OpLeft
- Hasil = OpLeft operator OpRight
- PUSH Hasil
4. Jika notasi postfix berakhir, POP stack
sebagai hasil operasi
Contoh:
Penjelasan:
- 2 disimpan pada stack karena merupakan
operand
- 3 disimpan pada stack karena merupakan
operand
- ‘+’ merupakan operator, maka 2 ke OpLeft,
dan 3 ke OpRight. Sehingga pada stack disimpan 5 (Hasil operasi akan muncul
jika dimasukkan operator)
- Operand 5 disimpan pada stack
- Karena dimasukkan operator ‘*’, maka
otomatis sistem mengalikan angka sebelumnya yang telah disimpan pada stack.
Maka pada stack tertulis 25 (Hasil operasi akan muncul jika dimasukkan operator)
- Karena notasi postfix berakhir, maka POP
stack dijadikan sebagai hasil operasi
Nice artikel....
ReplyDelete