Queue Data Structure

A Queue is a linear data struture that is open at both ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). In can be thought of as a queue of poeple waiting to get tickets, the first person in line will be the first one called to purchase their ticket.

Basic Operations

enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.
peek() − Gets the element at the front of the queue without removing it.
isEmpty() − Checks if the queue is empty.

Implementations

List (Array) Implementation

class Queue:
	def __init__(self):
		self.queue = []

	def enqueue(self, data):
		self.queue.append(data)

	def dequeue(self):
		return self.queue.pop(0)

	def peek(self):
		if self.isEmpty():
			raise ValueError("Queue is empty")
		return self.queue[0]

	def isEmpty(self):
		return len(self.queue) == 0

type DataType interface{}

type Queue []DataType

func (q *Queue) IsEmpty() bool {
	return len(*q) == 0
}

func (q *Queue) Size() int {
	return len(*q)
}

func (q *Queue) Enqueue(d DataType) {
	*q = append((*q), d)
}

func (q *Queue) Peek() DataType {
	return (*q)[0]
}

func (q *Queue) Dequeue() DataType {
	if q.IsEmpty() {
		return nil
	}
	data := (*q)[0]
	*q = (*q)[1:]
	return data
}

class Queue {
	constructor() {
		this.queue = [];
	}

	enqueue(data) {
		this.queue.push(data);
	}

	dequeue() {
		return this.queue.shift();
	}

	peek() {
        return this.queue[this.queue.length-1];
    }
    
    isEmpty() {
        return this.queue.length === 0;
    }
}

class Queue {
private:
	vector<int> queue;
public:
	void enqueue(int data) {
		queue.push_back(data);
	}

	int dequeue() {
		int temp = queue[0];
		queue.erase(queue.begin());
		return temp;
	}

	int peek() {
		return queue[0];
	}

	bool isEmpty() {
		return queue.empty();
	}
};

class Queue {
    private ArrayList<Integer> queue;

    Queue(int size) {
        queue = new ArrayList<Integer>(size);
    }

    public void enqueue(int data) {
        queue.add(data);
    }

    public int dequeue() {
        int temp = queue.get(0);
        queue.remove(0);
        return temp;
    }

    public int peek() {
        return queue.get(0);
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

Linked List Implementation

type DataType interface{}

type node struct {
	data DataType
	next *node
}

type Queue struct {
	head *node
	tail *node
	length int
}

func (q *Queue) IsEmpty() bool {
	return q.length == 0
}

func (q *Queue) Size() int {
	return q.length
}

func (q *Queue) Enqueue(d DataType) {
	q.length++
	if q.head == nil {
		q.head = &node{d, nil}
		q.tail = q.head
	} else {
		temp := &node{d, nil}
		q.tail.next = temp
		q.tail = temp
	}
}

func (q *Queue) Peek() DataType {
	return q.head.data
}

func (q *Queue) Dequeue() DataType {
	if q.IsEmpty() {
		return nil
	} else {
		q.length--
		temp := q.head.data
		q.head = q.head.next
		return temp
	}
}

Time Complexity

In the list based implemention shown above the enqueue operation would have an average time complexity of O(1) unless the list needed to be resized in which case the time complexity would become O(n). The dequeue operation however would always be O(n) since all the elements in the list would need to be shifted each time.

Posted on Jun 27, 2022 by bmcculley Posted in:

Data Structures