October 2

October 2

On Queues and Stacks

Recall the previous lecture where we discussed queue and stack implementations using arrays.

As a reminder, queues are “First In, First Out” (FIFO), meaning data elements are added (pushed) to the back of the array and removed (shifted) from the beginning of the array. In the real world, you can find queues anywhere like in lines of traffic. The first car is the first to get out while new cars pile up on the back.

In contrast, stacks are “Last In, First Out” (LIFO), meaning data elements are added (pushed) to the back of the array and removed (popped) from the back as well. In the real world, you can find stacks in just about any image editing program. For example, when you use a tool in photoshop, you push a command onto a stack. When you hit “undo”, you remove the most recent command from that stack.

In order to perform these commands, you need to use the following methods:

  • myArray.push(x) – adds element ‘x’ to the back
  • myArray.pop() – removes an element from the back, returns that element
  • myArray.shift(x) – adds element ‘x’ to the beginning
  • myArray.unshift() – removes an element from the beginning, returns that element

Note that if you want to store the value of a removed element you use a variable:
var removedElem = myArray.pop();

On the dangers of popping and unshifting

It is very dangerous to call pop or unshift when there is nothing in the array. Just like when handling an array out of bounds error, you need to make sure you are using push, pop, shift, and unshift calls in the proper order with the correct number of calls so that you don’t break everything.

On Objects and their Methods/Attributes

You may have noticed that, in order to push, pop, shift and unshift using arrays, you have to use a dot operator to call array_name.push(x),  array_name.pop(), and etc. These are method calls, meaning these push and pop functions belong specifically to array_name. All arrays have this property, but by using the dot operator to call a method, you are basically saying “Hey array_name, do this operation.”

This is different from push() and pop() which are used to push and pop matrices off the stack. They are not called with a dot operator and are just built-in functions for p5.js.

You may have also noticed that we use the dot operator for a few other things, such as:

  • some_string.length
  • some_array.length
  • some_number.toString()

Dot operators belong to objects, so any string, array, or number is actually an object that comes with a set of special attributes and methods. You’ve already seen that an object’s methods are functions that belong to that object. In contrast, an object’s attributes are basically variables that belong to that object. So when we say some_string.length, we are saying “Give me the value of some_string‘s length”. You can think of the dot as meaning “apostrophe s” (some_string.length means roughly some_string‘s length).

Thanks to Michelle for these notes.