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

Imam Ibnu Badri Algoritma dan Pemrograman 06.40

DAFTAR ISI

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

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;
    }
}

Demo

Running program

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;
}