Stacks

A stack is an abstract data type that places restrictions on where you can add and remove elements. A good analogy is to think of a stack as a stack of books; you can remove only the top book, and you can only add a new book on the top. As with any abstract data type, a stack can be implemented with a variety of data structures, such as a linked list or an array. A stack has a variety of applications such as in reversing the order of elements, evaluating polish strings, etc.

The distinguishing characteristic of a stack is that the addition or removal of items takes place at the same end. This end is commonly referred to as the "top." The end opposite to it is known as the "bottom". The principle by which a stack is ordered is called LIFO (shorthand for last-in first-out). In our stack of books, the last book we add to the pile must be the one that comes off when we remove a book.

Sometimes, a stack is implemented to have a maximum capacity. In those cases, if the allocated space for a stack is completely used, then no more elements can be pushed, any attempt to do so will result in an stack overflow error. This is one of the most common errors encountered in the programming world, so much that it inspired the name of the Q&A website stackoverflow.com. The opposite can also happen, when a pop is attempted when the stack is empty: this results in a stack underflow error.

There are two basic operations related to the stack.

Function Name*	Provided Functionality
push(i)	Insert element i at the top of the stack.
pop()	Remove the element at the top of the stack.

Stacks are often implemented with the following functions.

Function Name*	Provided Functionality
size()	returns the current size of the stack.
peek()	returns the element at the top of the stack without changing the stack

*Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.

Stack Questions

Consider a stack of boxes numbered from zero to ten, arranged in ascending order one above the other such that the number ten is on top.

1. How do we push box 11 into this stack?

2. How do we pop a box from this stack?

3. If the room has height only enough for exactly eleven boxes, what happens when we try pushing a twelfth one?

4. What happens if we pop all of the boxes from the stack and then try to pop a box from the stack?

A1. The box 11 is placed above box 10.

A2. The topmost box (box 10) is removed.

A3. Since there is no more space, this is similar to a stack overflow error.

A4. Since we have no boxes left in the stack, this is similar to stack underflow error.

A stack and its operations are usually visualized as a stack of cards or books. Consider the empty stack below.

Push essentially stacks a given item with a specific value on top of the stack. For example if the block below was run,

1
2
3

push(6)
push(789)
push(0)

the resulting stack would look like the following:

pop works by doing the reverse and kicking out the top element of the stack. For our stack above, executing the block of operations would make it look like

1
2
3

pop()
pop()
pop()

What will an empty stack look like after the block of operations below is executed?

1 2 3

push(6) push(5) push(pop()*2)

---

The answer is D. The last line just takes out the last element, doubles it and puts it back in. $_\square$

What will an empty stack look like after the block of operations below is executed on it?

1 2 3 4 5

push(5) push(3) push(7) push(pop()+1) peek()

---

The stack will look like the following:

1 2 3 4

(5) (5,3) (5,3,7) (5,3,8)

Thus $8$ will be outputted. $_\square$

To implement a stack data structure we usually need:

• an area of memory to store the data items
• a pointer to the top of the stack
• a set of well defined operations : push,pop,peek and size

In this implementation, the top of the stack is on the right of the array.

Note: Stacks are already implemented for you in Python, as you can see below. This is a re-implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Stack:
    self.array = []
    self.size = 0

    def __init__(self, array=None):
        if array != None:
            self.array = array
            self.size = len(array)
        else:
            self.array = []
            self.size = 0

    def push(self,item):
        self.array.append(item)

    def pop(self):
        deleted = self.array[-1]
        self.array = self.array[0:-1]
        return deleted

    def peek(self):
        return self.array[-1]

    def size(self):
        return self.size

Now that we have fully described the behavior of the stack ADT, we can implement it easily, as shown above. Even though there are several ways of implementing the stack ADT, here we will use an array based implementation. Because we will use python, we do not have to re-size our lists because they are dynamically re-sizable. Our implementation will be straightforward and new items will be added and deleted to the end of the list.

Write a method that reverses the contents of a stack

Solution

If the method is not instance method of the stack ADT we can write reverse as

1 2 3 4 5

def reverse(stack): new_stack = Stack() while stack.size() != 0: new_stack.push(stack.pop()) return new_stack

Lists in Python already have the append and pop methods which let them be used as stacks.

Using a list as stack

1	>>> mystack = []

Right now the stack is empty let's fill it up with some elements.

1 2 3 4 5 6

>>> myStack.append(1) >>> myStack.append(2) >>> myStack.append(3) >>> myStack [1, 2, 3]

Now let's do the second important operation with it, that is to get an element out of it.

1 2 3 4 5

>>> myStack.pop() 3 >>> myStack.pop() 2

As expected its behaving like a stack and that's all we need from this data-type. You might be discouraged at how limited things it can do but you will thrilled at its power when you try to solve more sophisticated problems. You might be impressed how using stack can simplify things.

Let's have little more fun.

1 2 3 4 5 6 7

>>> myStack.append(7) >>> myStack.append(8) >>> myStack [1, 7, 8] >>> myStack.pop() 8

The time complexity of stacks depends on the type of the data structure you are using and the specific implementation you build. Below is a description of how linked lists and arrays are not that different when it comes to complexity:

A stack, unlike a queue, only performs an operation at one end of the list. This invariant makes the process much easier. In our book pile, adding a book was very easy since we already knew where the top was. Likewise, removing the topmost book is equally easy since we know where it is. No need to go through the rest of the pile because all of our operations happen at one point.