Stack and Queue

Apa sih Stack dan Queue itu?

Stack
Stack dapat diartikan sebagai tumpukan. Stack merupakan sebuah koleksi objek yang menggunakan LIFO (Last In Last Out). Apa sih maksud LIFO itu? Pada saat kita menambahkan/memasukkan elemen/data, maka data tersebut (yang terakhir ditambahkan) akan menjadi data yang pertama kali keluar dari tumpukan tersebut. Secara sederhana, data yang terakhir kali masuk adalah data yang pertama kali/terlebih dahulu keluar. Stack merupakan struktur data linier di mana elemen dapat dimasukkan dan dihapus hanya dari satu sisi daftar yang biasa disebut sebagai TOP. Penyisipan elemen ke dalam sebuah stack disebut PUSH. Penghapusan elemen dari stack disebut POP. Dalam stack, kita selalu melacak elemen terakhir yang ada dalam daftar dengan suatu pointer yang disebut TOP.

Representasi diagram stack dapat kita lihat dari gambar di bawah ini :



Berikut ini adalah istilah-istilah yang ada dalam program stack :

1. Push : berfungsi untuk menambah elemen pada suatu stack
2. Pop : berfungsi untuk mengambil/menghapus elemen pada suatu stack
3. Clear : berfungsi untuk mengosongkan stack
4. IsEmpty : berfungsi untuk mengecek apakah stack sudah kosong atau belum
5. IsFull : berfungsi untuk mengecek apakah stack sudah penuh

Berikut adalah contoh coding push dalam bahasa C

struct Data

{

    int value;

    struct Data *next,*prev;

}*head,*curr,*tail;

void push(int a)

{

    curr = (struct Data*)malloc(sizeof(struct Data));

    curr->value = a;

    

    if(head==NULL){

        head = tail = curr;

    }

    else{

        tail->next = curr;

        curr->prev = tail;

        tail = curr;

    }

    head->prev = tail->next = NULL;

}

void cetak()
{
    curr = head;
    while(curr!=NULL){
        printf("%d\n",curr->value);
        curr = curr->next;
    }
}

int main()
{
    push(10);
    push(20);
    push(30);
    push(40);
   
    cetak();
   
    return 0;
}

Queue
Queue dapat diartikan sebagai antrian. Queue merupakan sekumpulan data dimana penambahan elemennya hanya bisa dilakukan pada suatu ujung yang disebut sebagai sisi belakang (Rear) dan penghapusan/pengambilan elemennya dilakukan melewati ujung yang lain/pada sisi depan (Front). Prinsip yang digunakan pada queue adalah FIFO (First In First Out). Apa si FIFO itu? Elemen yang pertama kali dimasukkan ke dalam daftar adalah elemen yang pertama kali akan di hapus dari daftar/keluar dari daftar. Proses penghapusan elemen dalam queue disebut sebagai operasi dequeue. Dalam keseharian kita, kita menjumpai prinsip FIFO dalam hal antrian pada saat ingin membayar belanjaan di kasir. Siapa yang duluan datang, maka dia yang akan duluan dilayani dan dia yang akan duluan keluar dari supermarket/toko yang di datanginya dibandingkan dengan orang yang baru saja datang untuk mengantri membayar barangnya. Pada queue terdapat satu buah pintu masuk di ujung dan satu buah pintu keluar di ujung yang lain. Oleh sebab itu, queue membutuhkan variabel Head dan Tail.

Representasi diagram queue dapat kita lihat dari gambar di bawah ini :


Berikut ini adalah operasi yang dapat kita gunakan pada queue :

1. push() : menambahkan suatu item/elemen pada bagian belakang queue
2. pop() : menghapus suatu item/elemen pada bagian depan queue
3. front() : mengungkapkan/mengembalikan item paling depan dari queue

Berikut adalah beberapa aplikasi yang menggunakan queue :

1. Deques
2. Priority Queues
3. Breadth First Search

Berikut adalah contoh coding queue dalam bahasa C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

int peek() {
   return intArray[front];
}

bool isEmpty() {
   return itemCount == 0;
}

bool isFull() {
   return itemCount == MAX;
}

int size() {
   return itemCount;
} 

void insert(int data) {

   if(!isFull()) {

      if(rear == MAX-1) {
         rear = -1;           
      }     

      intArray[++rear] = data;
      itemCount++;
   }
}

int removeData() {
   int data = intArray[front++];

   if(front == MAX) {
      front = 0;
   }

   itemCount--;
   return data; 
}

int main() {
   /* insert 5 items */
   insert(3);
   insert(5);
   insert(9);
   insert(1);
   insert(12);

   // front : 0
   // rear  : 4
   // ------------------
   // index : 0 1 2 3 4
   // ------------------
   // queue : 3 5 9 1 12
   insert(15);

   // front : 0
   // rear  : 5
   // ---------------------
   // index : 0 1 2 3 4  5
   // ---------------------
   // queue : 3 5 9 1 12 15

   if(isFull()) {
      printf("Queue is full!\n"); 
   }

   // remove one item
   int num = removeData();

   printf("Element removed: %d\n",num);
   // front : 1
   // rear  : 5
   // -------------------
   // index : 1 2 3 4  5
   // -------------------
   // queue : 5 9 1 12 15

   // insert more items
   insert(16);

   // front : 1
   // rear  : -1
   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15

   // As queue is full, elements will not be inserted.
   insert(17);
   insert(18);

   // ----------------------
   // index : 0  1 2 3 4  5
   // ----------------------
   // queue : 16 5 9 1 12 15
   printf("Element at front: %d\n",peek());

   printf("----------------------\n");
   printf("index : 5 4 3 2  1  0\n");
   printf("----------------------\n");
   printf("Queue:  ");

   while(!isEmpty()) {
      int n = removeData();         
      printf("%d ",n);
   } 
 
   return 0;
}




Referensi :

1. https://id.wikipedia.org/wiki/Stack_(struktur_data)
2. https://medium.com/easyread/memahami-konsep-stack-secara-sederhana-bd4409ec560c
3. https://samuraibali.blogspot.com/2016/11/pengertian-stackproses-dan-contoh.html
4. http://rizkialdadilly.blogspot.com/2016/01/pengertian-queue.html
5. https://www.tutorialspoint.com/data_structures_algorithms/queue_program_in_c.htm
6. https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/
7. Binus Maya Stack&Queue Slides