The array-based implementation of queues is not an efficient implementation, as we select one side of a queue to add an element and other side to remove. The task can be accomplished by using two pointers-front and rear. An element is added to the front and removed from the rear of the queue. This leads to a drifting issue, as shown in Figure 4.7:

Figure 4.7: Drifting issue with queue implementation using array

In Figure 4.7, it can be seen that there could be a situation when the queue is full, yet there is free space available in the array:

Figure 4.8: Approach 1 to address drifting issue in queue

The problem can be resolved by keeping the rear at the first position, and moving the rest of the array towards the rear by one unit, as shown in Figure 4.8. However, this makes the removal operation O(n), which is computationally inefficient. Another way to tackle this problem is by using a circular implementation of queue, as shown in Figure 4.9. Circular implementation allows reusing of empty cells once the array length ends. This implementation makes addition and removal operations O(1), which is quite efficient computationally. However, this introduces another challenge related to determining whether the queue is full or empty, as in both situations, empty and full queue, the rear will hold a position less then the front pointer. The current problem can be addressed by keeping track of the number of elements in the queue, or creating an array with n+1 to store n elements:

Figure 4.9: Circular array implementation of queue

Let's implement a queue using reference classes in R. The ADT implementation of a queue in R is shown as follows:

aqueue<-setRefClass(Class = "aqueue", 
  fields = list( 
    Alist="array", 
    queuesize="integer", 
    maxSize="integer", 
    rear = "integer", 
    top = "integer" 
  ), 
  methods = list( 
    initialize=function(qSize, ...){ 
      queuesize<<-0L 
      rear<<-1L 
      top<<-0L 
      maxSize<<-as.integer(qSize) 
      Alist<<-array(dim = maxSize) 
    } 
    # Queue is empty 
    isEmpty = function() {}, 
    # Add element to the queue 
    enqueue = function(val){}, 
    # remove element from queue 
    dequeue = function() {}, 
 
    # size of queue 
    size = function() {} 
  ) 
)

The new reference class can be generated using setRefClass(), and the method can be created using a method list within setRefClass. The new queue can be created using the new() function:

> q<-aqueue$new()
> q
Reference class object of class "aqueue"
Field "Alist":
[1] NA NA NA NA NA NA NA NA NA NA NA NA NA ... NA NA NA NA NA
Field "queuesize":
[1] 0
Field "arraySize":
[1] 100
Field "maxSize":
[1] 100
Field "rear":
[1] 0
Field "top":
[1] 0

The other implementation from ADT can be added to the queue class by adding methods. That the queue is empty can be checked using the queuesize variable, as follows:

isEmpty = function() { 
  return(queuesize==0L) 
}

For adding and deleting an element in a queue, the methods enqueue() and dequeue() can be used respectively in the method list of setRefClass:

enqueue = function(val){ 
  if(queuesize<maxSize){ 
    if(top==maxSize) top<<-0L 
    top<<-top + 1L 
    Alist[top]<<-val 
    queuesize<<-queuesize+1L 
  } else 
  { 
    cat("Queue Full!") 
  } 
}, 
 
dequeue = function() { 
  if(queuesize>0L){ 
    Alist[rear]<<-NA 
    ifelse(rear==maxSize, rear<<-1L, rear<<-rear+1L) 
    queuesize<<-queuesize-1L 
  } else 
  { 
    cat("Empty Queue!")  
  } 
}

The preceding function is a circular implementation; thus, the top and rear position is reset to the start of the array once the top and rear pointer hits the maxSize index.

Linked queues are a much simpler implementation, as nodes are dynamically created and destroyed. In linked list queues, an element is inserted at the rear and removed from the front, as shown in Figure 4.10:

Figure 4.10: Example of link list queue

The class implementation of the queue ADT in R using reference classes for a linked list-based queue is shown as follows:

ListQueue <- setRefClass(Class = "ListQueue", 
  fields = list( 
    Lsize="integer", 
    front="environment",  
    rear = "environment", 
    Lqueue="environment"), 
 
  methods = list( 
    initialize=function(...) { 
      Lsize<<-0L 
    }, 
 
    # Check if list is empty 
    isEmpty=function(){},  
 
    # create empty environment 
    create_emptyenv = function() {}, 
 
    # Create node  
    Node = function(val, node=NULL) {}, 
 
    # Function to add value to link list 
    enqueue=function(val){}, 
 
    # Function to remove node from link list 
    dequeue=function(){} 
 
     # Function to get link list size 
    size=function(){}  
  ) 
)

The function isEmpty checks whether the linked list is empty using the Lsize variable, as shown in the following code snippet. For an empty linked list, Lsize has zero value:

isEmpty=function(){ 
  if(Lsize==0) { 
    cat("Empty Stack!") 
    return(TRUE) 
  } else 
  { 
    return(FALSE) 
  } 
}

The link list node in R is represented using environment; thus, the create_emptyenv function creates an empty environment:

create_emptyenv = function() { 
  emptyenv() 
}

The node representation is similar to the linked list node, and consists of element and nextnode.

Node = function(val, node=NULL) { 
  llist <-new.env(parent=create_emptyenv()) 
  llist$element <- val 
  llist$nextnode <- node 
  llist 
}

As the elements in a queue are added to the rear of the queue, the rear pointer is used to capture the environment location for the last node as follows:

enqueue=function(val){ 
  ListIsEmpty<-isEmpty() 
  if(ListIsEmpty){ 
  Lqueue<<-Node(val) 
  Lsize<<-Lsize+1L 
  rear<<-Lqueue 
  } else 
  { 
    newNode<-Node(val) 
    assign("nextnode", newNode, envir = rear) 
    rear<<-newNode 
    Lsize<<-Lsize+1L 
  } 
}

The assign statement is used to attach the reference of a new node using the rear pointer reference. As elements are deleted from the front node, the front pointer is not necessary, and the first element can be accessed and removed directly, as shown in the following code snippet:

dequeue=function(){ 
  stackIsEmpty<-isEmpty() 
  if(stackIsEmpty){ 
    cat("Empty Queue") 
  } else 
  { 
    Lqueue<<-Lqueue$nextnode 
    Lsize<<-Lsize-1L 
  } 
}

The size of the linked list is contained in the Lsize variable of the class function.

The linked list implementation of queues require O(1) (worst-case) computation effort, where enqueuing is performed by appending to the rear, and dequeuing is implemented at the head of the linked list. However, new allocation is required with every operation, which may make it slow.

The enqueuing operation in array-based queues is implemented by using a circular buffer, which works as inserting element at the next free position. The implementation can be a dynamic array implementation, where a new array is created with a bigger size when the max memory is reached in the current array. The enqueuing and dequeuing operations are performed using front and rear references, thus requiring O(1) computational effort. In terms of memory allocation, queues behave similar to stack implementations-a linked implementation needs an extra nextnode field to store the address of the next node, thus increasing the memory overhead.