Tumpukan (stack) dan Antrian (queue) C++ Disertai Contoh, Tugas & Jawaban - TeachMeSoft

Tumpukan (stack) dan Antrian (queue) C++ Disertai Contoh, Tugas & Jawaban

Tumpukan (stack) dan Antrian (queue) C++ Disertai Contoh, Tugas & Jawaban



Materi

Stack (tumpukan) adalah struktur data yang meniru bagaimana proses menyimpan dan mengambil suatu buku pada suatu tumpukan buku yang ada di lantai. Apabila diperhatikan dengan seksama maka proses menyimpa buku (disebut push) dan proses mengambil buku (disebut pop) dari suatu tumpukan selalu dilakukan pada bagian atas tumpukan (top of the stack ) sehingga terjadi urutan yang disebut LIFO (Last In First Out).

Artinya, buku yang terakhir disimpan adalah buku yang pertama harus diambil karena buku inilah  yang berada pada urutan teratas dari tumpukan.
Operasi dalam stack :
  • Push : Menyisipkan data ke dalam stack.
  • Pop : Mengeluarkan data dari stack
  • IsEmpty : Untuk mengecek apakah stack dalam keadaan kosong atau tidak.
  • IsFull : Untuk mengecek apakah stack dalam keadaan penuh atau tidak
  • Clear : Mengosongkan isi data.
Pendeklarasian stack :
//deklarasi stack dengan struct dan array
struct STACK
{
      int data[5];
      int top;
};
//deklarasi variabel tumpukan dari struct 
STACK tumpukan;


Queue (antrian) adalah suatu kumpulan data yang penambahan elemen hanya bisa dilakukan pada suatu ujung (disebut dengan sisi belakang atau rear), dan penghapusan atau pengambilan elemen dilakukan lewat ujung yang lain (disebut dengan sisi dengan atau front). Pada queue prinsip yang digunakan adalah FIFO (first in first out).

Ada pun operasi dasar yang dapat dilakukan pada sebuah queue (antrian), yaitu operasi penambahan data (ENQUEUE) dan operasi pengurangan/ pengambilan data (DEQUEUE). Gambar dibawah mengilustrasikan operasi ENQUEUE dan DEQUEUE pada queue yang didimplemenatasikan dengan array berukuran 6 dari proses berurutan sebagai berikut,
P1 : Penambahan 3 data, yaitu A-B-C-D-E
P2 : Pengurangan 2 data
P3 : Penambahan 3 data, yaitu F-G-H
Ilustrasi operasi PUSH dan POP pada Stack
Ilustrasi operasi PUSH dan POP pada Stack
Pada kehidupan sehari-hari, implementasi queue dapat dilustrasikan seperti antrian pasien pada sebuah poliklinik. Jika ada pasien baru maka pasien tersebut akan mendapatkan nomor antrian yang paling besar dan akan menjadi pasien yang terakhir dilayani setelah pasien-pasien yang datang sebelumnya.


Contoh Program


Contoh ke-1
Cobalah program yang menggunakan tumpukan (stack) berikut, dan gambarlah dalam bentuk ilustrasi POP dan PUSH datanya.
Source code
//Preprosesor
#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;

//Deklarasi stack dengan struct dan array
struct STACK
{
int data [5];
int top;
};

//deklarasi variabel tumpukan dari struct
STACK tumpukan;

//deklarasi fungsi operasi stack
void inisialisasi();
int IsEmpty();
int IsFull();

void push (int data);

void pop ();

//fungsi main program
main ()
{
system("cls");
int pilih, input, i;
inisialisasi();
do{
cout<<"1. Push data"<<endl;
cout<<"2. Pop Data"<<endl;
cout<<"3. Print Data"<<endl;
cout<<"4. Clear Data"<<endl;
cout<<endl;
cout<<"Pilih : ";cin>>pilih;
switch(pilih)
{
case 1:
{
if(IsFull()==1)
{
cout<<"Tumpukanan penuh !";
}
else
{
cout<<"Data yang akan di push : ";cin>>input;
push(input);
}
cout<<endl;
getch();
break;
}
case 2:
{
if(IsEmpty()==1)
{
cout<<"Tumpukanan Kosong !";
}
else
{
cout<<"Data yang akan di Pop = "<<tumpukan.data[tumpukan.top]<<endl;
pop();
}
cout<<endl;
getch();
break;
}
case 3:
{
if(IsEmpty()==1)
{
cout<<"Tumpukanan Kosong !"<<endl;
}
else
{
cout<<"Data : "<<endl;
for(i=0; i<=tumpukan.top; i++)
{
cout<<tumpukan.data[i]<<" ";
}
}
cout<<endl;
getch();
break;
}
case 4:
{
inisialisasi();
cout<<"Tumpukanan Kosong !"<<endl;
cout<<endl;
getch();
break;
}
            default:
{
cout<<"Tidak ada dalam pilih"<<endl;
}
}
} while (pilih>=1 && pilih <=4);
getch();
}

//fungsi inisialisasi stack = kosong
void inisialisasi()
{
tumpukan.top=-1;
}

//fungsi mengecheck apakah stack kosong
int IsEmpty()
{
if(tumpukan.top==-1)
{
return 1;

}else
{
return 0;
}
}

//fungsi mengecheck apakah stack penuh
int IsFull()
{
if (tumpukan.top==5-1)
{
return 1;

}else
{
return 0;

}

}

//fungsi untuk menyisipkan data ke stack
void push(int data)
{
tumpukan.top++;
tumpukan.data[tumpukan.top]=data;
}

//fungsi untuk mengeluarkan data dari stack
void pop()
{
tumpukan.top=tumpukan.top-1;
if(tumpukan.top<0)
{
tumpukan.top=-1;
}
}


Running program 
Running program 1


Contoh ke-2
Berikut contoh queue yang diimplementasikan dengan array
Source code
#include <iostream>
#include <conio.h>
#define MAX 8

using namespace std;

typedef struct{
int
data[MAX];
int head;
int tail;
}
Queue;
Queue
antrian;
void
Create(){
antrian.head=antrian.tail=-1;
}

int IsEmpty(){
return 0;
}

int IsFull(){
if(antrian.tail==MAX-1) return 0;
else return 0;
}

void Enqueue(int data){
if(IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
}else
{
if(IsFull()==0)
{
antrian.tail++;
antrian.data[antrian.tail]=data;
}
}
}

int Dequeue(){
int i;
int e=antrian.data[antrian.head];
for(i=antrian.head; i<=antrian.tail-1; i++)
{
antrian.data[i]=antrian.data[i+1];
}
antrian.tail--;
return e;
}

void Clear(){
antrian.head=antrian.tail=-1;
cout<<"data clear";
}

void Tampil(){
if(IsEmpty()==0)
{
cout<<"\nData di antrian";
for(int i=antrian.head; i<=antrian.tail; i++)
{
cout<<"\n"<<antrian.data[i];
}
}else {cout<<"data kosong ! \n";}
}

int main(){
int data;
Create();
cout<<"\nData = ";cin>>data;
Enqueue(data);
cout<<"\nData = ";cin>>data;
Tampil();
cout<<"\nElemen yang keluar : "<<Dequeue();
Tampil();
getch;
}
Running program 
Running program II



Tugas

  1. Buatlah algoritma dan program yang kira-kira bisa menghasilkan tampilan seperti berikut 


Jawaban


Pending




Disqus comments