MODUL MEMAHAMI QUEUE MENGGUNAKAN LINKED LIST DI BAHASA C/C++

ANTRIAN QUEUE
mari belajar queue suatu struktur data antrian yang memiliki dua versi yaitu diterapkan dengan array atau dengan linked list yang saya contohkan di bawah ini dengan linked list. Sebelum mengenal jauh dengan queue alangkah baiknya kita memahmi dulu apa sih queue itu ??

Queue
Adalah suatu bentuk khusus dari linear list dengan operasi penyisipan (insertion) hanya pada salah satu sisi ( Rear/ belakang) dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya (Front/ depan) dari list.

Antrean Q = [ Q1, Q2, Q3,……….., QT]
Front(Q) = bagian depan dari antrean Q
Rear(Q) = bagian belakang dari antrean Q
Noel(Q) = Jumlah elemen di dalam antrean ( berharga integer)
Jadi : Front(Q) = QT
Rear(Q) = Q1
Noel(Q) = T

Antrean beroperasi secara FIFO ( First In First Out) yang pertama masuk, yang pertama keluar.

 Operasi dasar pada Antrean :

1. CREATE(Q)
Operator untuk membentuk suatu antrean hampa
Q = [,…….,]
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak didefinisikan
REAR(CREATE(Q)) = tidak didefinisikan

2. ISEMPTY(Q)
Operator yang menentukan apakah antrean Q hampa atau tidak.
Operand dari operator ISEMPTY adalah antrean.
Hasilnya bertipe data Boolean
ISEMPTY(Q) =TRUE jika Q adalah antrean hampa (NOEL(Q) = 0)
FALSE jika Q bukan antrean kosong (NOEL(Q)  0)

3. INSERT(E,Q)
Operator yang menyisipkan elemen E ke dalam antrean Q
Catt : Elemen Q ditempatkan pada bagian belakang antrean dan antrean menjadi lebih panjang
Q = [ A, B, C, D]
REAR(INSERT(E,Q)) = E
FRONT(Q) = A
NOEL(Q) = 5
ISEMPTY(INSERT(E,Q)) = FALSE
4. REMOVE(Q)
Operator yang menghapus elemen bagian depan dari antrean Q dan antrean menjadi lebih pendek
Jika NOEL(Q) = 0 maka
REMOVE(Q) = ERROR ( UNDERFLOW)

 Penyajian dari antrean :
1. One way list
2. Array
 Menunjukkan bagaimana suatu antrean dalam array Queue dengan N elemen
1. Antrean mula-mula terdiri dari elemen AAA, BBB, CCC, DDD


1 2 3 4 5 6 7 8 9
FRONT(Q) = AAA : 1
REAR(Q) = DDD : 4

2. REMOVE(Q)


1 2 3 4 5 6 7 8 9

FRONT(Q) = BBB : 2
REAR(Q) = DDD : 4

3. INSERT(EEE,Q)

1 2 3 4 5 6 7 8 9

FRONT(Q) = BBB : 2
REAR(Q) = EEE : 5

KESIMPULAN :
Untuk setiap kali penghapusan nilai FRONT bertambah
Untuk setiap kali penambahan nilai REAR akan bertambah

berikut kode queue dengan linked menggunakan bahasa c

/* queue dengan single linked list*/

#include
#include

typedef struct simpul node;

struct simpul{
	char data;
	node *next;
};

typedef struct{
	node *front;
	node *rear;
}queue;

void inisial(queue *);
void enqueue(char x, queue *);
char dequeue(queue *);


main()
{
	queue antrian;
	char input;
	int i;
	
	puts("\t program QUEUE dengan SINGLE LINKED LIST ");
	puts("\t       created by: ACHMAD SAYFUDIN");
	puts("\t =======================================");
	inisial(&antrian);
	for(i=0;i<5;i++){	
		fflush(stdin);
		printf("data : ");
		scanf("%c", &input);
		enqueue(input,&antrian);
	}
	for(i=0;i<5;i++){
			printf("%c ",dequeue(&antrian));
	}

}

void inisial(queue *q)
{
	q->front = NULL;
	q->rear = NULL;
}

void enqueue(char x, queue *q)
{
	node *p;
	p = (node *)malloc(sizeof(node));

	if(p==NULL){
		puts("alokasi gagal");
	}
	else{//membuat node baru pertama
		p->data = x;
		p->next = NULL;
	}

	if(q->front==NULL){//jika tak ada linked sama sekali 
		q->front = p;
		q->rear = p;
	}
	else{//jika linked list sudah ada 
		q->rear->next = p;
		q->rear = p;
	}
}

char dequeue(queue *q){
	node *hapus;
	char temp;

	temp = q->front->data;//diambil datanya dulu
	hapus = q->front;// arahkan hapus ke front

	q->front = hapus->next;//hubungkan q->front dengan hapus->next jika data banyak
	
	//jika queue data tunggal
	if(q->front == NULL)
	{
		q->rear = NULL;
	}

	free(hapus);
	hapus = NULL;

	return temp;
}