Double Stack

Struktur Data Pertemuan 5

"Double Stack"

Double Stack atau Stack Ganda adalah stack yang terdiri dari dua single stack. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus melalui salah satu arah.
Pada double stack, dasar stack 1 berada pada index terkecil. Dan dasar stack 2 berada pada index terbesar.

Ilustrasi pada Double Stack :

Proses pada Double Stack :

• AWAL (inisialisasi)
• PUSH1 (Push untuk Stack 1)
• POP1 (Pop untuk Stack 1)
• PUSH 2 (Push untuk Stack 2)
• POP 2 (Pop untuk Stack 2)

Prinsip pada Double Stack yaitu LIFO (Last In First Out) baik untuk Stack1 dan Stack2

Kondisi Antrian :

Algoritma dalam Double Stack

Algoritma PUSH1 (mengisi Stack1)
Periksa apakah Stack1 BISA DIISI
if (Top2 – Top1 > 1)
{
Top1 = Top1 + 1;
}
S[Top1] = x;
else
cout<<“Stack Penuh”;

Algoritma POP1 (mengambil isi Stack1)
Periksa apakah Stack1 ADA ISINYA
if (Top1 > -1)
{
x = S[Top1];
}
Top1 = Top1 – 1;
else
cout<<“Stack Kosong”;

Algoritma PUSH2 (mengisi Stack2)
Periksa apakah Stack2 BISA DIISI
if (Top2 – Top1 > 1)
{
Top2 = Top2 – 1;
}
S[Top2] = x;
else
cout<<“Stack Penuh”;

Algoritma POP2 (mengambil isi Stack2)
Periksa apakah Stack2 ADA ISINYA
if (Top2 < n)
{
x = S[Top2];
}
Top2 = Top2 + 1;
else
cout<<“Stack Kosong”;

Soal

1. Susunlah program untuk menginput data dari keyboard terus menerus hingga stack1 penuh 
2. Susunlah program untuk menginput data dari keyboard terus menerus hingga stack2 penuh 
3. Susunlah program untuk menghapus stack1 hingga kosong 
4. Susunlah program untuk menghapus stack2 hingga kosong 

Program :

#include<iostream>
#include<conio.h>
#include<stdlib.h>
#define n 10
using namespace std;
char P[]={'>',' ',' ',' ',' ',' '};
int S[n],mov[2],X,Y,pil=0;
int *top1,*top2,*dasar1,*dasar2,*helpI;
//utama
void awal(){
 top1=&S[-1];
   top2=&S[n];
   dasar1=&S[-1];
   dasar2=&S[n];
   helpI=&S[-1];
}
void push1(int x){
 top1=top1+1;
   *top1=x;
}
void push2(int y){
 top2=top2-1;
   *top2=y;
}
void pop1(){
 X=*top1;
   *top1=0;
   top1=top1-1;
}
void pop2(){
 Y=*top2;
   *top2=0;
   top2=top2+1;
}
int BisaDiisi(int k){
 if(top2-top1>k)
    return 1;
   else
    return 0;
}
int BisaDiambil1(){
 if(top1>dasar1)
    return 1;
   else
    return 0;
}
int BisaDiambil2(){
 if(top2<dasar2)
    return 1;
   else
    return 0;
}
void tampil(){
 cout<<"\n================ data menjadi ==================="<<endl;
   while(helpI!=(dasar2-1)){
    helpI++;
      cout<<*helpI<<" ";
   }
   cout<<"\n======================================================"<<endl;
   helpI=&S[-1];
}
//tambahan
void tampilMenu(){
    system("cls");
    cout<<"========================================================"<<endl;
    cout<<"1. Push 1"<<endl;
    cout<<"2. Push 2"<<endl;
    cout<<"3. Pop 1"<<endl;
    cout<<"4. Pop 2"<<endl;
    cout<<"========================================================="<<endl;
      cout<<"pilihan anda : ";cin>>pil;

}


main(){
 awal();
   do{
  tampilMenu();
      cout<<endl;
  //cout<<"nilai pil = "<<pil<<endl;
    switch(pil){
     case 1: if(BisaDiisi(1)){
           cout<<"masukkan bilangan = ";
                  cin>>X;
           push1(X);
         }
                else{
                cout<<"maaf tidak ada tempat untuk push";
                }break;
      case 2: if(BisaDiisi(1)){
           cout<<"masukkan bilangan = ";
                  cin>>Y;
           push2(Y);
          }
               else{
                 cout<<"maaf tidak ada tempat untuk push";
               }break;
      case 3: if(BisaDiambil1()){
          pop1();
                   cout<<"data yang diambil = "<<X<<endl;
          }
                else{
                cout<<"maaf stack 1 tidak ada isinya"<<endl;
                }break;
      case 4: if(BisaDiambil2()){
           pop2();
                  cout<<"angka yang diambil = "<<Y<<endl;
          }
               else{
                 cout<<"maaf stack 2 tidak ada isinya"<<endl;
               }break;
   }
    tampil();
      cout<<"\nenter untuk mengulang dan esc untuk keluar !";
      do{
       mov[0]=getch();
         if(mov[0]==27)
          exit(0);
      }while(mov[0]!=13);
   }while(mov[0]==13);
 getch();

}