QUEUE dengan Link List

Link Queue dengan Link List

Antrian adalah struktur data linier yang mengikuti FIFO yaitu metode First-In-First-Out.

Kedua ujung antrian disebut Depan dan Belakang, di mana Penyisipan selalu terjadi di Belakang dan elemen diakses atau dihapus dari Depan.

Saat mengimplementasikan antrian menggunakan array:

1.  Kita tidak dapat menambah ukuran array, jika kita memiliki lebih banyak elemen untuk disisipkan daripada kapasitas array.

2.  Jika kita membuat array yang sangat besar, kita akan membuang banyak ruang memori.

Oleh karena itu jika kita mengimplementasikan Queue menggunakan Linked list kita dapat menyelesaikan masalah ini, seperti pada Linked list, Node dibuat secara dinamis sesuai kebutuhan.

Jadi dengan menggunakan link list kita dapat membuat Antrian dengan ukuran variabel dan tergantung pada kebutuhan kita, kita dapat menambah atau mengurangi ukuran antrian.

Jadi, dengan peggunaan pointer head dengan Link List, kita akan menggunakan dua pointer, front dan rear untuk melacak kedua ujung list, sehingga kita dapat melakukan semua operasi di O (1).

#include <iostream>

using namespace std;

// Structure of Node.

struct Node

{
int data;
Node *link;
};
Node *front = NULL;
Node *rear = NULL;
//Function to check
if queue is empty or not
bool isempty()
{
 if(front == NULL && rear == NULL)
 return true;
 else
 return false;
}
//function to enter
elements in queue
void enqueue ( int
value )
{
 Node *ptr = new Node();
 ptr->data= value;
 ptr->link = NULL;
 //If inserting the first element/node
 if( front == NULL )
 {
  front = ptr;
  rear = ptr;
 }
 else
 {
  rear ->link = ptr;
  rear = ptr;
 }
}
 
//function to
delete/remove element from queue
void dequeue ( )
{
 if( isempty() )
 cout<<"Queue is empty\n";
 else
 //only one element/node in queue.
 if( front == rear)
 {
  free(front);
  front = rear = NULL;
 }
 else
 {
  Node *ptr = front;
  front = front->link;
  free(ptr);
 }
}
 
//function to show
the element at front
void showfront( )
{
 if( isempty())
 cout<<"Queue is empty\n";
 else
 cout<<"element at front is:"<<front->data;
}
 
//function to display
queue
void displayQueue()
{
 if (isempty())
 cout<<"Queue is empty\n";
 else
 {
  Node *ptr = front;
  while( ptr !=NULL)
  {
   cout<<ptr->data<<"
";
   ptr= ptr->link;
  }
 }
}
//Main Function
int main()
 int choice, flag=1, value;
 while( flag == 1)
 {
  cout<<"\n1.enqueue 2.dequeue
3.showfront 4.displayQueue 5.exit\n";
 cin>>choice;
 switch (choice)
  {
  case 1: cout<<"Enter Value:\n";
          cin>>value;
          enqueue(value);
          break;
  case 2: dequeue();       
    break;
  case 3: showfront();
          break;
  case 4: displayQueue();
          break;
  case 5: flag = 0;
          break;
  }
 }
 return 0;
}