Stacks

Stacks are a data structure: a logical collection of data which has various ways that programmers can access it. You are probably used to data structures such as arrays, which are typically fixed length indexed structures like the one below:

Data structures such as arrays are random access, meaning that we can access any part of them at any time. For example, we can directly access any part of it. A stack is a very restricted data structure. It has literally a stack of items, with a top and a bottom, but the only item we can directly access is the item on top.

Items are pushed onto the top of the stack, so if we executed:

Push 11

Then 11 would go on top of the stack:

To remove the top item, we Pop the stack. Notice that Pop doesn’t take an argument, because it simply pops the top item off. If we pop this stack, pop returns 11 and removes it from the stack. Although restrictive in terms of how we access them, stacks have a number of advantages. First, they are dynamic data types, meaning that they grow and contract as needed. Second, they don’t have a data type – this is probably very different from most programming languages that you’ve dealt with, as they generally insist on being told what type (character, integer, float, etc.) is going to be stored. Stacks don’t even have to store items of the same type. Take a play with the example below:

Stacks are often used to process incoming strings of characters. In these cases, Push doesn’t take an argument, and instead simply pushes the first item from the string onto the stack. Similarly, Pop pops the stack and sends the character to the output.

Take a look at the following example in which reverses the order of an expression:

Great, so now we know how stacks work, but what can we do with them? The next section gives a nice simple algorithm that uses a stack to convert from an arbitrarily complex infix expression to the corresponding prefix one.