queue.go

package main

const (
	FIFO = iota
	LIFO
)

type queueNode struct {
	next  *queueNode
	prev  *queueNode
	value string
}

type Queue struct {
	head *queueNode
	tail *queueNode

	size      int
	queueMode int
}

func NewQueue(queueMode int) *Queue {
	return &Queue{
		queueMode: queueMode,
	}
}

func (q *Queue) Enqueue(value string) {
	defer func() {
		q.size++
	}()
	if q.head == nil {
		q.head = &queueNode{value: value}
		return
	}

	if q.head.next == nil {
		newNode := &queueNode{value: value}
		newNode.prev = q.head
		q.head.next = newNode
		q.tail = newNode
		return
	}

	newNode := &queueNode{value: value}
	newNode.prev = q.tail
	q.tail.next = newNode
	q.tail = newNode
}

func (q *Queue) Dequeue() (string, bool) {
	defer func() {
		if q.size > 0 {
			q.size--
		}
	}()

	if q.queueMode == LIFO {
		if q.tail != nil {
			target := q.tail.value

			if q.tail.prev == q.head {
				q.head.next = nil
				q.tail = nil
			} else {
				q.tail = q.tail.prev
				q.tail.next = nil
			}

			return target, true
		}

		if q.head != nil {
			target := q.head.value
			q.head = nil
			return target, true
		}

		return "", false
	}

	if q.head != nil {
		target := q.head.value
		q.head = q.head.next
		if q.head != nil {
			// remove prev ref
			q.head.prev = nil

			// remove tail ref
			if q.head == q.tail {
				q.tail = nil
			}
		}

		return target, true
	}

	return "", false
}