Maps, Stacks and Queues

In this lesson, we look at some of the more simple data structures that don't come in layers. We will be looking at Maps, Stacks and Queues.

Introduction

Last lesson, we glossed over what a data structure is, and covered The Array as our classic example of a data structure. But simply picking out indexes might not be the best, or most structured way of playing around with our data. In this lesson, we look at some of the more simple data structures that don't come in layers. We will be looking at Maps, Stacks and Queues.

Learning outcomes

Look through these now and then use them to test yourself after doing the assignment:

• What are Maps, Stacks and Queues?

• What are their differences, and how may each be used?

• What features would you expect each of these to have?

Maps

Sometimes known as an Associative Array, Dictionary or a Map depending on the language. Maps are used like an array, but instead of using an index number like:

arr = [4, 9, 45]
arr[0] #This would return 4

You use a key to identify where you want to look:

people = { 'Billy Smiggins' => 'male', 'Jane Doe' => 'female' }
people['Jane Doe'] #This would return female

This data structure allow us to store values with keys that have some meaning, or otherwise map values to objects other than integers. In the cases of Ruby and Javascript, this site's languages of choice, Ruby calls these Hashes and Javascript calls them Maps

Stacks

You may recall that The Stack was mentioned in when we were learning about recursion, a concept that functions and parameters are stacked on top of each other in memory, then taken from the top down when they are needed. [Stacks](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) as a data structure follow the same methodology of stacking their input on top of remaining data, and taking data off the top of the stack.

Stacks should allow users to use two methods to manipulate data. #push, which puts it's input on the top, or the head of the stack; and #pop, which removes the element from the head of the stack and returns it. Some implementations may have #peek, which allow users to see the head of the stack without removing it. Here is an example of what Stack use may look like

simple_stack.push(3) #[3]
simple_stack.push(1) #[3,1]
simple_stack.push(9) #[3,1,9]

simple_stack.pop # Returns 9, Stack: [3,1]
simple_stack.pop # Returns 1, Stack: [3]
simple_stack.pop # Returns 3, Stack: []

To conceptualize this idea; think of a stack of plates. Removing a plate from the middle would be a silly idea. Instead, you'd take the plates from the top.

An alternative name for a stack is a LIFO (Last-In-First-Out) queue.

Both Ruby and Javascript have Stack functionality built into their Array object. Be sure to read on what their pop and push methods do!

Queues

You will be familiar with the concept of queuing for something. Say you're buying groceries, and there's a line of people waiting to purchase their goods; and you join the back of this line. You have just joined a Queue.

By definition, a [Queue](https://en.wikipedia.org/wiki/Queue_(abstract_data_type)), like a Stack, should allow uses to use two methods: #enqueue, which places it's input at the back of the queue, and #dequeue which removes an element from the front of the queue and returns it.

To go back to our grocery analogy; you joining the queue would be #enqueue, and the individual finally buying and bagging their food would be #dequeue'd. Here is an example of what a Queue may look like:

grocery_queue.enqueue('Billy Smiggins') #["Billy Smiggins"]
grocery_queue.enqueue('Jane') #["Billy Smiggins", "Jane"]
grocery_queue.enqueue('QChai') #["Billy Smiggins", "Jane", "QChai"]

grocery_queue.dequeue # Returns "Billy Smiggins", Queue: ["Jane", "QChai"]
grocery_queue.dequeue # Returns "Jane",           Queue: ["QChai"]
grocery_queue.dequeue # Returns "QChai",          Queue: ["QChai"]

An alternative name for a queue is a FIFO (First-In-First-Out) queue.

Some languages have builtin queues ready for use; but Ruby and Javascript do not explicitly have queues or either of the mentioned functions. However, both languages Ruby and Javascript have the #shift method which, when used with #push; allows the easy implementation of queues.

Assignment

1. Use pop, push and shift in your language of choice and get a feel for how these work! If you're not using Ruby or Javascript for this course, you might need to google around to find Queue implementation.

2. View the docs of your chosen language and find how maps work in your language. It could be under a different name, like 'Hash' or 'Dictionary'.