SFTPK: Stack & Queue
This post is one in a series of topics formally trained programmers know—the rest of the series can be found in the series index. In this post, we will look at two related and simple data structures: the Stack and the Queue. The stack is a structure that can be implemented with either an Array or Linked List.
An important term for understanding a stack is that it is LIFO (last-in-first-out); namely, the last item you add (or push) is the first item you retrieve (or peek or pop). Let's have a look at what a stack looks like:
Here, we added 1, 2, 3, 4, and then 5, and when we read from the stack, we retrieve them in reverse order.
Implementations
Next is the queue, which is very similar to the stack—but whereas the stack is LIFO, a queue is FIFO (first-in-first-out). So if we put 1, 2, 3, 4, and 5 into the queue, we retrieve them in the same order: 1, 2, 3, 4, 5.
Implementations
C# has a queue implementation, and in JavaScript, an array can act as a queue when you use unshift to add to the beginning (the head) and pop to remove from the end (the tail).