Data Structures / Chapter 1: Lists And Stacks / Representing Collections

Let's now take a look at a stack, which is a slightly different kind of collection. We can add elements to and remove elements from a stack just as we can with lists, but there are some limitations. To better understand stacks, let's try visualizing them.

Imagine that we have a spring-loaded coin holder where we can store and retrieve coins. We can add coins by inserting them into the top of the holder. We can retrieve coins by pulling them from the top of the holder.

For example, imagine that the coin holder contains 3 coins:

5

25

1

Let's add a dime (10):

10

5

25

1

The dime is at the top. Later, we remove the top coin from the holder. The holder now goes back to the previous state:

5

25

1

The coin holder is an example of a stack. As with the coin holder, we can only operate at the top of the stack:

• The push operation adds a new element to the top of the stack.
• The pop operation removes the element at the top of the stack.

Logicwalk stack notation

Stacks can be represented in different ways. In Logicwalk (LW), stacks are a special kind of list. The first element of the list is a stack element, and the second element is a child list that contains the rest of the stack. Let's see some examples.

An empty stack is just a set of opening and closing brackets:

[ ]

This is exactly the same as an empty list.

To push an element into the stack, first write the element and a comma in front of the empty list:

8, [ ]

Then surround the entire text in brackets:

[ 8, [ ] ]

As with lists, whitespace characters are optional.

Let's try pushing 7 to the stack. Again, we write 7 and a comma in front of the stack, then surround it with [ ]:

[ 7, [ 8, [ ] ] ]

Finally, let's push 5:

[ 5, [ 7, [ 8, [ ] ] ] ]

Now the stack has 3 values, 5, 7, and 8. Think of this as a stack that is laying on its side.

Let's next pop from the stack. The pop operation always removes the "top" element in the stack, so we don't need to specify the element position. After 1 pop operation, the stack is:

[ 7, [ 8, [ ] ] ]

Notice that the last element we pushed into the stack (5) is the first element that gets popped out. This order is called LIFO (last in, first out).

If we want to pop 8, we need to pop 7 first:

[ 8, [ ] ]

Pop again to remove 8 from the stack:

[ ]

Now the stack is empty.

Stack is a list

We mentioned that a stack is a special type of list. Let's examine the 3-element stack again:

[ 5, [ 7, [ 8, [ ] ] ] ]

Let's verify that this is a list. There appears to be many lists inside the stack. The outermost list, or stack, has 2 elements:

• 5
• [ 7, [ 8, [ ] ] ]

Notice that the second element is also list that has the following 2 elements:

• 7
• [ 8, [ ] ]

Once again, the second element is a list with 2 elements:

• 8
• [ ]

The second element is again a list, but it is emtpy.

In summary, the LW stack is a list where:

1. The first element is the top element of the stack, and the second element is another list that contains the rest of the elements.
2. The first element of the child list is the next element of the stack, and the second element is another list that contains the rest of the elements.
3. The second element of the last child list is empty.

Working with stacks can be cumbersome compared to working with lists because we can only pop or push. For example, if we want to insert an element to the bottom of the stack, we need to first pop all the stack elements, push the new element, then push all the popped elements.

Stacks also appear more complex due to the nesting syntax:

List	Stack
[ 1, 2, 3, 4, 5 ]	[ 1, [ 2, [ 3, [ 4, [ 5, [ ] ] ] ] ] ]
[ "Amy", "Susan", "Jane" ]	[ "Amy", [ "Susan", [ "Jane", [ ] ] ] ]
[ False, True ]	[ False, [ True, [ ] ] ]

But despite these issues, we will use stacks rather than flat lists whenever we need a collection. In the next lesson, let's discuss why stacks are preferable.

Previous Lesson Next Lesson