To Queue or not to Queue?

#programming #kotlin #java #queue

That should not be a question

Waiting In Line To See Star Wars: 1977–2000

No one likes to stand in line¹. Most people hate to waste their time queuing up. We spend an average of 6 months of our adult lives waiting our turn — almost 3 days a year. There are books about queues. Documentaries². Even academic experts in queues. But then, when we are coding, we often forget to use queues and end up messing around with lists instead.

All things work better when you use the right tool.

FIFO or LIFO1!!!

A queue in a supermarket is FIFO. The way we usually stack boxes is LIFO. FIFO stands for “First In, First Out”³. LIFO is the acronym for “Last In, First Out”. That’s it.

I used draw.io to draw this diagram. Awesome tool!

When implementing FIFO queues we usually use add, peek (returns, but does not remove, the head of the queue) and poll (returns and removes the head of the queue) methods, while we refer to them, respectively, as push, peek and pop in **LIFO **stacks.

The STACK, the QUEUE and the DEQUE

In a stack we can only add and remove elements from one end (LIFO), in a queue we add elements to one end and remove them from the other (FIFO) and, joining those two worlds we have the deque (aka “Double Ended Queue”) where we can add and remove elements from both ends. None of them allows random access to the elements.

	val stack = Stack<String>()

	stack.push("first")
	stack.push("second")
	stack.push("last")

	println(stack) // [first, second, last]

	println(stack.peek()) // last
	println(stack) // [first, second, last]

	println(stack.pop()) // last
	println(stack) // [first, second]

view raw queues-stack.kt hosted with ❤ by GitHub

	val queue: Queue<String> = LinkedList()

	queue.add("first")
	queue.add("second")
	queue.add("last")

	println(queue) // [first, second, last]

	println(queue.peek()) // first
	println(queue) // [first, second, last]

	println(queue.poll()) // first
	println(queue) // [second, last]

view raw queues-queue.kt hosted with ❤ by GitHub

	val queue: Deque<String> = LinkedList()

	queue.addFirst("first")
	queue.add("second")
	queue.addLast("last")

	println(queue) // [first, second, last]

	println(queue.peekFirst()) // first
	println(queue.peekLast()) // last
	println(queue) // [first, second, last]

	println(queue.pollFirst()) // first
	println(queue) // [second, last]
	println(queue.pollLast()) // last
	println(queue) // [second]

view raw queues-deque.kt hosted with ❤ by GitHub

In JAVA you should use deque to model a stack because the Stack class is considered obsolete (it extends the Vector class and inherits all its methods, making it possible to break the LIFO principle).

So, don’t reinvent the wheel⁴.

This article was originally published on Medium

[1] Ok, there are some weird exceptions:facepalm:
[2] There is always an alternative https://www.youtube.com/watch?v=ZyNz8UHHrxE (in Spanish):wink:
[3] Some people know it as FCFS (“First Come, First Served”)
[4] And remember to give LolaMarket a chance. Awesome service!

External links 👀