Stack & Queue

Stack and Queue

I.Stack

Stack merupakan basic dari data structure yang merepresentasikan tumpukan /stack aslinya ,dimana yang terakhir dimasukan,keluar pertama kali.Sebagai ilustrasinya,dapat dibayangkan dengan tumpukan buku dimana kita hanya dapat mengambil buku teratas untuk memindahkan ke sesuatu tempat.Implementasi dari stack juga disebut dengan LIFO(Last In First Out). Konsep stack digunakan pada DFS(Depth First Search) yang merupakan algoritma untuk mencari suatu data pada trees. Terdapat 3 operan dasar di stack yaitu,push (memasukan suatu data),pop (delete data teratas) ,peek (melihat data teratas).

Operan dasar di Stack. Sumber :https://cdn.journaldev.com/wp-content/uploads/2018/05/swift-stacks-diagram.png

Implementasi nya dalam C sebagai berikut:

#include <stdio.h>

#include<stdlib.h>

typedef struct LinkedList{

int data;

struct LinkedList *next;

}stackLinkedList;

stackLinkedList *top = NULL;

void push(int data){

stackLinkedList *temp = (stackLinkedList *) malloc(sizeof(stackLinkedList));

temp->data = data;

temp->next = top;

top = temp;

}

void printLists(){

stackLinkedList *temp = top;

printf("Data :\n");

while(temp!= NULL){

printf("%d\n",temp->data);

temp = temp->next;

}

printf("\n\n");

}

void pop(){

stackLinkedList *temp = top;

if(top == NULL){

printf("No data\n");

}

else{

top = temp->next;

free(temp);

}

}

void peek(){

if(top == NULL){

printf("No data\n\n");

}

else

printf("Peek : %d -> Top\n\n",top->data);

}

int main (){

int num;

int x;

int choice;

do{

printf("1.Push item\n");

printf("2.Pop item\n");

printf("3.Peek item\n");

printf("4.Show item\n");

printf("5.Exit\n");

printf(">>Input : ");

do{

scanf("%d",&choice);

}while(choice > 5 || choice < 1);

switch(choice){

case 1:

printf(">>Input Data : ");

scanf("%d",&x);

push(x);

break;

case 2:

pop();

break;

case 3:

peek();

break;

case 4:

printLists();

break;

case 5:

return 0;

}

}while(1);

}

Untuk lebih jelasnya,dapat melihat di:

- https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

- https://www.youtube.com/watch?v=SE-RkUlheoc -Stack Operations - PUSH & POP

- https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

Prefix,Infix,Postfix

Terdapat 3 notasi operasi untuk suatu aritmatika yaitu,prefix,infix,dan postfix.Sebelummemahami tentang notasi operasi untuk suatu aritmatika, perlu dipahami terlebih dahulu terjadinya notasi dalam struktur data.Notasi terbentuk dari operan dan operator.Operan merupakan data /nilai dalam suatu proses.Sedangkan Operator merupakan fungsi yang digunakan.Contohnya: A + B. Operan adalah A,B sedangkan Operator adalah +.

1. Infix
Merupakan notasi yang sering dijumpai oleh orang orang.Urutan infix yaitu (Operand,Operator,Operand). Seperti contohnya (1+5)*(6/2)^3.

2.Prefix
Merupakan notasi yang terbentuk dari (Operator,Operand Operand) sehingga bentuk infix dapat diubah menjadi sebagai berikut : * + 1 5 ^ / 6 2 3.
Cara untuk mengubah infix ke prefix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
=  (+ 1 5) * (/ 6 2) ^ 3
= (+ 1 5) * (^ / 6 2 3)
= * + 1 5 ^ / 6 2 3.

3.Postfix
Merupakan notasi yang terbentuk dari (Operand,Operand,Operator) sehingga bentuk infix dapat diubah menjadi sebagai berikut : 1 5 + 6 2 / 3 ^ *.
Cara untuk mengubah infix ke postfix sebagai berikut :
(1 + 5) * ( 6 / 2) ^ 3
= (1 5 +) * (6  2 /) ^3
= (1 5 + ) * (6 2 / 3 ^)
= 1 5 + 6 2 / 3 ^ *

II.Queue
Merupakan linear data struktur seperti stack.Namun queue merepresentasikan antrian dimana yang pertama kali masuk,pertama kali keluar.Queue juga dikenal dengan FIFO(First In First Out).Ilustrasi yang baik untuk mempelajari queue adalah saat mengantri untuk memesan makanan.Pastinya pelanggan pertama akan mendapatkan makanan terlebih dahulu.Konsep queue digunakan pada BFS(Breadth First Search) yang merupakan algoritma untuk mencari suatu data tree.Perbedaan dengan DFS(Depth First Search) adalah DFS menggunakan konsep stack,sedangkan BFS menggunakan konsep queue.Terdapat 3 operan dasar pada queue yaitu Enqueue (memasukan data pada queue) , Dequeue (Menghapus data awal data pada queue) ,dan peek (Melihat data ter-awal).

Contoh dasar queue.Sumber : https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/02/Queue.png

Implementasi queue pada C sebagai berikut :

#include<stdio.h>
#include<stdlib.h>
typedef struct queueLinkedList{
int data;
struct queueLinkedList *next;
}queueLinkedList;

typedef struct Linkedlist{
struct queueLinkedList *rear;
struct queueLinkedList *front;
}Linkedlist;
Linkedlist list;
void enqueue(int data){
queueLinkedList * temp = (queueLinkedList *)malloc(sizeof(queueLinkedList));
temp->data = data;
if(list.front == NULL){
temp->next = NULL;
list.front = temp;
list.rear = temp;
}
else{
list.rear->next = temp;
temp->next = NULL;
list.rear = temp;
}
}
void dequeue(){
queueLinkedList *temp = list.front;
list.front = temp->next;
free(temp);
}
void peek(){
printf("%d --> Front\n\n",list.front->data);
}
void printLists(){
queueLinkedList *temp = list.front;
printf("Data :\n");
while(temp!= NULL){
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n\n");
}
int main (){
int num;
int x;
int choice;
do{
printf("1.Enqueue item\n");
printf("2.Dequeue item\n");
printf("3.Peek item\n");
printf("4.Show item\n");
printf("5.Exit\n");
printf(">>Input : ");
do{
scanf("%d",&choice);
}while(choice > 5 || choice < 1);
switch(choice){
case 1:
printf(">>Input Data : ");
scanf("%d",&x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
peek();
break;
case 4:
printLists();
break;
case 5:
return 0;
}

}while(1);
}
Untuk Lebih jelasnya dapat dilihat di :
-https://www.studytonight.com/data-structures/queue-data-structure
-https://www.geeksforgeeks.org/queue-data-structure/
-https://www.youtube.com/watch?v=XuCbpw6Bj1U - Data Structures: Introduction to Queues