Skip to content

Queue

Jump to bottom
Battistella Stefano edited this page Apr 24, 2014 · 4 revisions

In computer science, a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed.

Wikipedia

var queueA = new Queue(); //an empty queue
var queueB = new Queue(0, 1, 2, 3); //queueB contains (from the head) 0, 1, 2, 3

Methods

getIterator()

This method returns an iterator for scanning the queue. The iterator is useful in order to get a full decoupling in your classes. This avoid, to the class that uses the iterator, to know what type of data structure stores the data.

var queue = new Queue();
var it = queue.getIterator();
for(it.first(); !it.isDone(); it.next()) {
  var item = it.getItem();
  //do something
}

The iterator starts from the head of the queue.

Complexity: O(1)

enqueue(item)

This method enqueue the item at the tail of the queue. The item could be whatever you want.

var queue = new Queue();
queue.enqueue(4); //queue contains (from the head) 4
queue.enqueue(2); //queue contains (from the head) 4, 2

Complexity: O(1)

multiEnqueue(items)

This method enqueue the items at the head of the queue. The items could be whatever you want.

var queue = new Queue();
queue.multiEnqueue([4, 2]); //queue contains (from the head) 4, 2
queue.multiEnqueue([5, 6]); //queue contains (from the head) 4, 2, 5, 6

Complexity: O(n)

dequeue()

This method remove the item at the head of the queue. The item is returned.

var queue = new Queue(4, 2); //queue contains (from the head) 4, 2
queue.dequeue(); //4 and queue contains 2

Complexity: O(n)

In this case the method require to restore indexes of the array that mantains the items of the queue.

multiDequeue(times)

This method removes the first times items at the head of the queue. The items are returned as an array.

var queue = new Queue(6, 8, 4, 2); //queue contains (from the head) 6, 8, 4, 2
queue.multiDequeue(2); //[6, 8] and queue contains (from the head) 4, 2

Complexity: O(n)

peek()

This method takes the item at the head of the queue without removing it.

var queue = new Queue(6, 8, 4, 2); //queue contains (from the head) 6, 8, 4, 2
queue.peek(); //6 and queue contains (from the head) 6, 8, 4, 2

Complexity: O(1)

remove(index, length)

This method removes the first length items starting from the position index of the queue. The items aren't returned. The length parameter could be omitted. In that case, will be removed only the item at the position index.

var queue = new Queue(6, 8, 4, 2, 7); //queue contains (from the head) 6, 8, 4, 2, 7
queue.remove(1, 2); //queue contains (from the head) 6, 2, 7
queue.remove(1); //queue contains (from the head) 6, 7

Complexity: O(n)

clear()

This method empty the queue.

var queue = new Queue(6, 8, 4, 2);
queue.clear(); //the queue is empty

Complexity: O(1)

contains(item, callback)

This method checks if the queue contains an item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method checks if the item is simply contained in the queue.

var queue = new Queue(6, 8, 4, 2);
queue.contains(4); //true
queue.contains(1); //false

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var queue = new Queue(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 5;
};
queue.contains(null, callback); //true

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var queue = new Queue(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
queue.contains(null, callback); //true

Complexity: O(n)

execute(callback)

This method execute the callback function for each item stored in the queue. The callback must accept the item the iteration is working on. The callback must also return a value to assign to the item.

var queue = new Queue(6, 8, 4, 2);
var callback = function(item) { //this function returns the square for each item
  return item * item;
};
queue.execute(callback); //queue contains (from the head) 36, 64, 16, 4

In this example we deal with more complex items.

var queue = new Queue(0, 1);
var callback = function(item) { //this function encapsulate each item into an object
  return {x: item, y: item + 2};
};
queue.execute(callback); //queue contains (from the head) {x: 0, y: 2}, {x: 1, y: 3}

Complexity: O(n)

getItem(index)

This method returns the item at position index starting from the head of the queue. So index 0 will be for the item at the head of the queue, 1 is for the second and so on.

var queue = new Queue(6, 8, 4, 2);
queue.getItem(0); //6
queue.getItem(1); //8

Complexity: O(1)

getLength()

This method returns the length of the queue so the number of items stored.

var queue = new Queue();
queue.getLength() //0 - the queue is empty
queue.multiEnqueue([6, 8, 4, 2]);
queue.getLength(); //4

Complexity: O(1)

isEmpty()

This method checks if the queue is empty or not.

var queue = new Queue();
queue.isEmpty() //true
queue.multiEnqueue([6, 8, 4, 2]);
queue.isEmpty(); //false

Complexity: O(1)

filter(callback)

This method returns all the items that satisfies the condition represented by the callback. The callback must accept the item the iteration is working on. The method starts from the head of the queue.

var queue = new Queue(6, 8, 4, 2);
var callback = function(item) { //this function checks if the item is lower than 4 or greater than 6
  return item < 4 || item > 6;
};
queue.filter(callback); //[2, 8];

In this example we deal with more complex items.

var itemA = {parent: null, item: 0};
var itemB = {parent: itemA, item: 1};
var itemC = {parent: itemB, item: 2};
var itemD = {parent: null, item: 3};
var queue = new Queue(itemA, itemB, itemC, itemD);
var callback = function(item) { //this function checks if itemA is in the same hierarchy of the item
  while(item.parent || item === itemA)
    item = item.parent;
  return item === itemA;
};
queue.filter(callback); //[itemC, itemB, itemA]

Complexity: O(n)

indexOf(item, callback)

This method returns the first position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the first position where the item is stored. If nothing has been found, the method returns -1, otherwise the position relates to the head of the queue.

var queue = new Queue(6, 8, 4, 2);
queue.indexOf(4); //2
queue.indexOf(5); //-1

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var queue = new Queue(6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 5;
};
queue.indexOf(null, callback); //2

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var queue = new Queue(itemA, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
queue.indexOf(null, callback); //1

Complexity: O(n)

lastIndexOf(item, callback)

This method returns the last position of the item that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns the last position where the item is stored. If nothing has been found, the method returns -1, otherwise the position is relates to the head of the queue.

var queue = new Queue(6, 2, 4, 8, 6, 8, 4, 2);
queue.lastIndexOf(4); //6
queue.lastIndexOf(5); //-1

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var queue = new Queue(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 5;
};
queue.lastIndexOf(null, callback); //4

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var queue = new Queue(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
queue.lastIndexOf(null, callback); //2

Complexity: O(n)

allIndexedOf(item, callback)

This method returns all the positions of the items that satisfy the condition represented by the callback function. The callback could be omitted. In this case the method returns all the positions where the item is stored. The positions relate to the head of the queue.

var queue = new Queue(6, 2, 4, 8, 6, 8, 4, 2);
queue.allIndexesOf(4); //[2, 6]
queue.allIndexesOf(5); //[]

If you desire a more complex research of an item you need to pass also the callback parameter. The callback must accept the item the iteration is working on. In that case the item parameter could be omitted because it won't be used to evaluate the condition.

var queue = new Queue(6, 2, 4, 8, 6, 8, 4, 2);
var callback = function(item) { //this function checks if there is a number lower than 5.
  return item < 5;
};
queue.allIndexesOf(null, callback); //[1, 2, 6, 7]

In this example we deal with more complex items.

var itemA = {parent: null; key: 0};
var itemB = {parent: itemA; key: 1};
var queue = new Queue(itemA, itemB, itemB);
var callback = function(item) { //this function checks if there is an item whose parent is itemA 
  return item.parent === itemA;
};
queue.allIndexesOf(null, callback); //[1, 2]

Complexity: O(n)

clone()

This method returns a clone of the queue. The items are cloned only if there's a method clone() to invoke, otherwise they will be shared with the old queue. This problem there is not if items are not object.

var queue = new Queue(6, 8, 4, 2);
var clone = queue.clone(); //clone contains (from the head) 6, 8, 4, 2

Complexity: O(n)

cloneDistinct()

This method returns a clone of the queue containing only one copy of the same item. The items are cloned only if there's a method cloneDistinct() to invoke or at least a method clone(), otherwise they will be shared with the old queue. This problem there is not if items are not object.

var queue = new Queue(2, 8, 4, 6, 8, 4, 2, 6);
var clone = queue.cloneDistinct(); //clone contains (from the head) 2, 8, 4, 6

Complexity: O(n·m)

m: the number of distinct elements stored in the queue. The time required depends strongly from the number of items duplicated. If the number of items duplicated is very high, then m tend to be near 1 (when the queue contains only one distinct item) so complexity will be O(n). If the number of items duplicated is very low, then m tend to be near n (when the queue doesn't contain any duplicated items) so complexity will be O(n2).

Clone this wiki locally