Jumat, 08 April 2016

Struktur Data Dasar - Stack dan Queue

Kali ini, gue bakal bahas salah satu struktur data dasar yang cukup sering dipakai (walaupun sebenernya udah ada librarynya di C++). Untuk struktur data stack biasa dipakai untuk konversi Infix/Postfix atau di DFS versi iteratif, sedangkan queue biasa dipakai untuk BFS.

Gue mulai dari stack dulu. Pada dasarnya, struktur data stack prinsipnya seperti tumpukan (stack = tumpukan). Data yang lebih dulu dimasukkan, bakalan lebih akhir dikeluarkan, dan sebaliknya (last in first out -- LIFO).

Misal gue punya data 1 3 4 2 5, gue masukin satu persatu ke stack yang gue punya, terus abis semuanya udah masuk, gue keluarin lagi satu persatu, jadinya keluarannya : 5 2 4 3 1.

Dalam stack, biasanya operasi yang dilakukan itu top(), untuk ngecek data apa yang ada di paling atas; push(), untuk masukin data ke (atas) stack; pop(), untuk ngeluarin data yang ada di paling atas; sama isEmpty(), untuk ngecek stacknya kosong atau gak.

Potongan kodenya (dalam C++) :

int s[101],head = 0;
void push(int x){
 head++;
 s[head] = x;
}
bool isEmpty(){
 if(head==0) return true;
 return false;
}
void pop(){
 head--;
}
int top(){
 return s[head];
}
Untuk queue, sebenernya mirip, tapi dia prinsip kerjanya kayak antrian. Yang pertama masuk ya yang pertama kali diproses. Yang pertama masuk bakal jadi yang pertama keluar (first in first out -- FIFO).

Operasinya mirip-mirip sama stack. Langsung aja deh potongan kodenya :

#define max_size 1010  //adjustable, sebutuhnya aja
int q[max_size], front = 0, rear = 0;
bool isEmpty(){
 if (front < 0 || front >= rear) {
  return true;
 }
 return false;
}
bool isFull(){
 if (rear == max_size - 1) { //C++ is using zero based indexing
  return true;
 }
 return false;
}
void enqueue(int x){           //enqueue itu kayak push kerjanya
 if(!isFull()){     //to prevent overflow
  q[rear] = x;
  rear++;
 }
}
void dequeue(){                //dequeue kayak pop kerjanya
  front++;
}
int peek_front(){
 return q[front];
}

Kayaknya segini dulu aja, kalau ada yang bingung/mau ditanya bisa tanya lewat kolom komentar, atau bagi yang kenal saya di real-life bisa langsung kontak :D

Semoga membantu

Tidak ada komentar:

Posting Komentar

-Mohon untuk tidak spam di komentar-