uhbis

Once more unto the uhbis, dear friends!

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

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.