Deque (Double Ended Queue)

Deque (Double Ended Queue) adalah suatu list linear atau linear list, yang penambahan dan penghapusan elemennya dapat dilakukan pada kedua sisi ujung list tetapi tidak dapat dilakukan di tengah-tengah list. Dari sini kita dapat mengatakan bahwa deque adalah salah satu Queue Ganda atau Double Deque.

Ada banyak cara penyajian suatu deque di dalam komputer. Namun yang biasa digunakan adalah penyajian dengan cara penempatan di dalam sebuah array sirkular, atau array putar deque. Disini kita menggunakan pointer atau penunjuk, LEFT dan RIGHT, yang berturut-turut menunjuk sisi kiri dan kanan deque.

Contoh Program

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

class node

{

public:

int data;

class  node *next;

class node *prev;

};

class dqueue: public node

{

  node *head,*tail;

  int top1,top2;

  public:

   dqueue()

   {

   top1=0;

   top2=0;

   head=NULL;

   tail=NULL;

   }

  void push(int x){

node *temp;

int ch;

if(top1+top2 >=5)

{

  cout <<"dqueue overflow";

  return ;

}

if( top1+top2 == 0)

  {

    head = new node;

    head->data=x;

    head->next=NULL;

    head->prev=NULL;

    tail=head;

    top1++;

  }

else

{

cout <<" Tambahkan Element 1.Left 2.Right\n Masukkan Pilihan:";

   cin >> ch;

   if(ch==1)

   {

     top1++;

     temp=new node;

     temp->data=x;

     temp->next=head; 

     temp->prev=NULL;

     head->prev=temp;

     head=temp;

   }

   else

   {

     top2++;

     temp=new node;

     temp->data=x;

     temp->next=NULL;

     temp->prev=tail;

     tail->next=temp;

     tail=temp;

   }

}

  }

  void pop()

  {

   int ch;

cout <<"Hapus 1.Left Node 2.Right Node\n Masukkan Pilihan:";

   cin >>ch;

   if(top1 + top2 <=0)

   {

     cout <<"\nDqueue under flow";

     return;

   }

   if(ch==1)

   {

     head=head->next;

     head->prev=NULL;

     top1--;

   }

   else

   {

     top2--;

     tail=tail->prev;

     tail->next=NULL;

   }

  }

  void display()

  {

   int ch;

   node *temp;

cout <<"Tampilkan dari 1.Awal 2.Akhir\n Masukkan Pilihan";

   cin >>ch;

   if(top1+top2 <=0)

   {

     cout <<"under flow";

     return ;

   }

   if (ch==1)

   {

    temp=head;

    while(temp!=NULL)

    {

      cout << temp->data <<" ";

      temp=temp->next;

    }

   }

   else

   {

    temp=tail;

    while( temp!=NULL) 

    {

      cout <<temp->data << " ";

      temp=temp->prev;

    }

   }

    }

  };

  main()

  {

    dqueue d1;

    int ch;

    while (1){

cout <<"1.INSERT  2.DELETE  3.DISPLAY  4.EXIT\n Masukkan Pilihan:";

    cin >>ch; 

    switch(ch)

    {

case 1:     cout <<"enter Masukkan Element";

cin >> ch;

d1.push(ch); break;

    case 2: d1.pop(); break;

    case 3: d1.display(); break;

    case 4: exit(1);

    }

  }}

Outputnya :

Selamat Mencoba dan Semoga Bermanfaat ☺

Queue (Antrian)

1. Deskripsi Queue

Queue (Antian) adalah suatu kumpulan data yang mana penambahan data / elemen hanya dapat dilakukan pada sisi belakang  sedangkan penghapusan / pengeluaran elemen dilakukan pada sisi depan. jenis struktur data antrian sering digunakan untuk menstimulasikan keadaan dunia nyata . Antrian dapat dijumpai dalam kehidupan sehari - hari. Misal : Antrian registrasi mahasiswa, tiket kereta api dan lain-ain.

2. Operasi - Operasi Dasar Pada Antrian

a. CreateQueue : Membuat antrian baru Q, dengan jumlah elemen koson.

b. MakeNullQ : Mengosongkan antrian Q, jika ada elemen maka semua elemen terhapus.

c. EmptyQ : Antrian Kosong? menguji apakah antrian Q kosong.

d. FullQ : Antrian Penuh? menguji apakah antrian Q penuh.

e. TambahkanQ/ insert (x,Q) : memasukkan elemen baru x ke dalam antrian Q.

f. AmbilQ/Remove (Q,x) : mengeluarkan elemen depan pada antrian Q.

Ilustrasi operasi Tambah/InsertQ dan Hapus/RemoveQ terhadap antrian

Contoh Program
#include<iostream.h>
#include<conio.h>

main()
{
char cek=0,data[20],x,hapus;
char pil;
do{
clrscr();
cout<<"1.tambah antrian"<<endl;
cout<<"2.hapus antrian"<<endl;
cout<<"3.lihat antrian"<<endl;
cout<<"4.keluar"<<endl;
cout<<endl;
cout<<"silakan masukan pilihan anda=";
pil=getche();
cout<<endl;
if(pil!='1'&& pil !='2' && pil !='3' && pil!='4')
cout<<"anda salah mengetikan inputan";
else
{
if(pil=='1') //PUSH
{
if(cek==20)
cout<<"antrian penuh";
{
cout<<"masukan nilai=";
cin>>x;
data[cek]=x;
cek++;
}
}
else
{
if(pil=='2')  //POP
{
if(cek==0)
cout<<"antrian kosong";
else
{
hapus=data[0];
for(int v=0;v<cek;v++)
data[v]=data[v+1];
data[cek-1]=NULL;
cek--;
  cout<<"data dengan nilai"<<hapus<<"terhapus";
}
  getch();
}
else
{
if(pil=='3') //CEK DATA
{
if(cek==0)
cout<<"antrian kosong";

else
{
cout<<endl;
for(int z=0;z<cek;z++)
{
cout<<" | ";

cout<<""<<data[z];
cout<<" | ";
}
}
getch();
}
}
}
}
}while(pil!='4');
}

Output :

Selamat Mencoba dan Semoga Bermanfaat ☺

program infix to prefix

1. Deskripsi Infix

Notasi aritmatik biasa ditulis dalam notasi infix, misal A+B-C yang mudah dimengerti oleh manusia , hanya saja dalam notasi infix perl diperhatikan prioritas pengerjaan karena berhubungan dengan hirarki operator  pada komputer. perioritas pengerjaannya adalah:

a. Tanda kurung ( )

b. Eksponensial atau pangkat ^

c. Perkalian, Pembagian *,/

d. Penjumlahan, Pengurangan +,-

contoh : (A+B)-(C*D)

Prioritas pengerjaan soal di atas adalah sebagai berikut :

a. Dalam kurung yang paling kiri (A+B)

b. Dalam kurung yang kedua (C*D)

c. Perkalian hasil pengurangan dengan hasil penhumlahan

Notasi infix biasa diubah ke notasi prefix dan juga postfix

2. Deskripsi Prefix dan Cara Pengerjaannya

Prefix adalah keadaan di mana simbol operator diletakkan sebelum dua operand. berikut contoh perubahan notasi infix ke prefix:

(A+B)-(C*D)

untuk pengerjaan infix , perlu diperhatikan urutan sebagai berikut:

a. pengerjaan dalam kurung ke-1 : (A+B), prefixnya +AB

b. pengerjaan dalam kurung ke-2 : (C*D), prefixnya *CD

c. terakhir adalah operator -, +AB-*CD, prefixnya -+AB*CD

Contoh Program
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 20

char stack[MAX];
int top = -1;
char pop();
void push(char item);
int prcd(char symbol)
{
    switch(symbol)
    {
    case '+':
    case '-':
        return 2;
    case '*':
    case '/':
        return 4;
    case '^':
    case '$':
        return 6;
    case '(':
    case ')':
    case '#':
        return 1;
    }
}

int isoperator(char symbol)
{
    switch(symbol)
    {
    case '+':
    case '-':
    case '*':
    case '/':
    case '^':
    case '$':
    case '(':
    case ')':
        return 1;
    default:
        return 0;
    }
}

void convertip(char infix[],char prefix[])
{
    int i,symbol,j=0;
    char test[MAX];

    infix=strrev(infix);
    stack[++top]='#';

    for(i=0;i<strlen(infix);i++)
    {
        symbol=infix[i];
        if(isoperator(symbol)==0)
        {
            prefix[j]=symbol;
            j++;
        }
        else
        {
            if(symbol==')')
            {
                push(symbol);
            }
            else if(symbol=='(')
            {
                while(stack[top]!=')')
                {
                    prefix[j]=pop();
                    j++;
                }
                pop();//pop out (.
            }
            else
            {
                if(prcd(symbol)>prcd(stack[top]))
                {
                    push(symbol);
                }
                else
                {
                    while(prcd(symbol)<=prcd(stack[top]))
                    {
                        prefix[j]=pop();
                        j++;
                    }
                    push(symbol);
                }
            }
        }
    }

    while(stack[top]!='#')
    {
        prefix[j]=pop();
        j++;
    }
    prefix[j]='\0';//null terminate string.
    prefix=strrev(prefix);
}

int main()
{
char infix[20],prefix[20];

{
puts("==============================");
puts("  PROGRAM INFIX TO PREFIX  ");
puts("==============================\n");
puts("NPM    : 18.420.071");
puts("Nama   : WIWIN TRI ASTUTI");
puts("Semester  : 3c(TI)\n");
}
printf("Masukkan notasi Infix?\n");
    gets(infix);
convertip(infix,prefix);
printf("Notasi prefixnya adalah:\n");
puts(prefix);
    getch();

    return 0;
}

void push(char item)
{
    top++;
    stack[top]=item;
}

char pop()
{
    char a;
    a=stack[top];
    top--;
    return a;
}

Outputnya :

Selamat Mencoba dan Semoga Bermanfaat☺

Program Push dan Pop nilai dalam stack

1. Deskripsi Stack

Stack adalah sebuah kumpulan data dimana data yang diletakkan di atas data yang lain. Stack merupakan struktur data    yang menggunakan LIFO (Last In First Out) yang memiliki arti "terakhir masuk sebagai yang pertama keluar".

2. Penyajian Stack

Beberapa cara untuk menyajikan sebuah stack tergantung pada permasalahan yang akan diselesaikan. kita dapat menggunakan array untuk menyajikan sebuah stack, dengan anggapan bahwa banyaknya elemen maksimum dari stack    tersebut tidak akan melebihi batas maksimum banyaknya elemen dalam array. Dan juga kita dapat menggunakan tipe data    struktur (struct) yang terdiri dari dua field. Field pertama bertipe array untuk menyimpan elemen stack , medan kedua    bertipe integer untuk mencatat posisi ujung stack.

3. operasi pada stack

operasi-oerasi dasar pada stack adalah sebagai berikut:

   a. Push : digunakan untuk menambahkan item pada stack yang paling atas

   b. Pop : diambil untuk mengambi item pada tumpukan paling atas

   c. Clear : digunakan untuk mengosongkan stack

   d. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

   e. IsFull : fungsi yang digunakan apakah stack yang digunakan sudah penuh

contoh program
#include<iostream.h>
#include<conio.h>
#define max 10

struct Tumpukan{
int atas;
int data[max];
}T;

void awal(){
T.atas=-1;
}

int IsEmpty(){
if(T.atas==-1)
return 1;
else
return 0;
}

int IsFull(){
if(T.atas==max-1)
return 1;
else
return 0;
}

void Push(int data){
if(IsEmpty()==1)
 {T.atas++;
T.data[T.atas]=data;
cout<<"Data"<<T.data[T.atas]<<"masuk ke stack";}
 else if(IsFull()==0)
 {T.atas++;
T.data[T.atas]=data;
cout<<"Data"<<T.data[T.atas]<<"masuk ke stack";}

 else
cout<<"Tumpukan penuh";
 }

 void Pop(){
if(IsEmpty()==0){
cout<<"Data teratas sudah terambil";
T.atas--;
}
else
cout<<"Data Kosong";
}

 void Print(){
 if(IsEmpty()==0)
{for(int i=T.atas;i>=0;i--)
{cout<<"\nTumpukan ke "<<i<<"="<<T.data[i];}
  }
else
cout<<"Tumpukan kosong";
}

void Clear(){
T.atas==-1;
cout<<"Tumpukan kosong!";
}

void main(){
int pil,data;
awal();
do
{
clrscr();
cout<<"1. Push\n2. Pop\n3. Print\n4. Clear\n5. Exit\n Masukkan pilihan:";
cin>>pil;
switch(pil)
{case 1:cout<<"Masukkan data = ";cin>>data;
Push(data);
break;
case 2:Pop();
break;
case 3:Print();
break;
case 4:Clear();
break;
case 5:cout<<"Terimakasih, tekan enter untuk keluar";
}
getch(); }
while(pil=5);}

output

Selamat Mencoba dan Semoga Bermanfaat☺