Stacks and Queues Almighty

Let's talk Stacks and Queues.

But first, because Stacks and Queues are kinds of data structures:
What is a data structure?
Are they language specific?

Data Structures are just the containers our computers store data in.

When implemented we're talking languages, but when we're talking about the logical concept and behavior of these structures we're talking Computer Science.*

Here's the definition from Wikipedia's Data Structure page, which is worth a look:

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.[^1]

It's just a collection.
Usually characterized by the ways you:

1. add to
2. remove from
3. and access the data within

And why do we care how our data is stored?

You might not be God, like Bruce here. Or Google.
But even if you don't have 7.7 billion people's information to manage,
it's best to optimize your storage to suit your needs.

Computers are our friends.
Friends who we can ask to keep track of information for us and do things with that information upon request. And we love computers for it. They can make our lives easier. Thank you, Computer.

But they can only love help us, if we give them structures they can manage efficiently.

There are many data structures: Arrays, Linked Lists, Doubly Linked Lists, Records, Trees, Graphs, Trees, Binary Trees, B-Trees, Stacks, Queues, and so on.[^2]

Stacks

Remember a data structure is just a way of storing data. Stacks are linear structures (meaning it's elements are sequential/the ordering matters). With stacks, it's useful to think of a stack of books or a stack of pancakes. You always care about the top of the stack (the end of the collection).

When using a stack, or choosing to use a stack, you're primarily concerned with being able to push and pop from the stack.

We can also keep track of the size of our stack if we want. And we can peek at our stack, which just takes a look at the top element in our structure.

Push = add.
Pop = remove.
Peek = access.

And we're always adding or removing from the top (which means the end 🙄) of the stack. The common abbreviation of this rule is: FILO First In Last Out, or LIFO Last In First Out. They mean the same thing.

Here's a push, pop, and size implementation (in pseudoclassical JS).
_{^{(no peek here, but you'd just want to grab the last element)}}

First, setting up the stack:

const Stack = function() {
  this.storage = {};
  this.size = 0;
};

Push:

Stack.prototype.push = function(value) {
  this.storage[this.size] = value;
  this.size++;
};

Pop:

Stack.prototype.pop = function() {
  const keys = Object.keys(this.storage);
  const popped = this.storage[keys.length - 1];
  delete this.storage[keys.length - 1];
  this.size--;
  return popped;
};

What's my age size again?

Stack.prototype.size = function() {
  return this.size < 0 ? 0 : this.size;
};

Basic applications for the stack structure:

• undo/redo commands
• word processing
• the call stack (it's own kind of stack structure)
• pancakes
• poltergeisting

Implementation is usually done with an Array or Linked List.

What identifies the data structure as a stack in either case is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations.[^3]

If implementation is done with an Array,
General C.S.* Array structures (not the ones you might see in JavaScript for example) have a set, pre-determined size. This can result in stack overflow!

^Oh ^no, ^oh ^god ^bruce

Stack overflow is what happens when a program tries to use more memory than is available in the call stack.^[4]

Time complexity wise^[5] — stack insertion, removal, access, and size return are constant, because we're only ever concerned with the top of the stack.

Queues

Queues are very similar to stacks.
[x] Data Structures
[x] Linear
[x] Implemented with your choice of underlying structure
[ ] Only concerned with the end of the collection
[ ] FILO/LIFO
[ ] Like pancakes
[ ] Applications
[x] O(1) time complexity

Ok, we've got some differences here.

Queues work by a FIFO First In First Out, or LILO Last In Last Out system. Queues IRL are at the movie theater ticket line, in the grocery store checkout, at the DMV, in the waiting room to the underworld.

When you remove from the queue, you remove from the beginning of the collection, just like you would from a line of people. When you add, you add to the end of the collection, like you would to the back of a line.

The names for adding and removing change up on us a bit.

Enqueue = add.
Dequeue = remove.

Here's another basic, beginner implementation (also pseudoclassical)^[6]
This time with queues.

Set up:

const Queue = function() {
  this.storage = {};
  this.size = 0;
};

Enqueue:

Queue.prototype.enqueue = function(value) {
  this.size++;
  this.storage[this.size] = value;
};

Dequeue:
_{^{it's midnight on July 21, 2007 and you're first up to buy the Deathly Hallows.}}

Queue.prototype.dequeue = function() {
  this.size--;
  const keys = Object.keys(this.storage);
  const dequeued = this.storage[keys[0]];
  delete this.storage[keys[0]];
  return dequeued;
};

Size:

Queue.prototype.size = function() {
  return this.count < 0 ? 0 : this.count;
};

Basic applications:

• print queues
• cpu memory
• online shopping
• booking angel olsen tickets online
• searching graphs
• call centers
• rollercoaster tycoon

👏In Conclusion👏

Same:
[x] Data Structures
[x] Linear
[x] Implemented with your choice of underlying structure
[x] O(1) time complexity

Not the same:
[ ] Only concerned with the end of the collection
[ ] First/Last rules
[ ] Like pancakes
[ ] Applications

[1]Wikipedia's Data Structure Page
[2]Big List of Data Structures
[3]Wiki-Stack
[4]Meta Overflow
[5]Big O
[6]Pseudo-what?
*Computer Science, my dude.