What is a Stack?

A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top.” The end opposite the top is known as the “base.”

The base of the stack is significant since items stored in the stack that are closer to the base represent those that have been in the stack the longest. The most recently added item is the one that is in position to be removed first. This ordering principle is sometimes called LIFO, last-in first-out. It provides an ordering based on length of time in the collection. Newer items are near the top, while older items are near the base.

stack

One of the most useful ideas related to stacks comes from the simple observation of items as they are added and then removed. Assume you start out with a clean desktop. Now place books one at a time on top of each other. You are constructing a stack. Consider what happens when you begin removing books. The order that they are removed is exactly the reverse of the order that they were placed. Stacks are fundamentally important, as they can be used to reverse the order of items. The order of insertion is the reverse of the order of removal. Figure 3 above shows the Python data object stack as it was created and then again as items are removed. Note the order of the objects.

The Stack Abstract Data Type

The stack abstract data type is defined by the following structure and operations. A stack is structured, as described above, as an ordered collection of items where items are added to and removed from the end called the “top.” Stacks are ordered LIFO. The stack operations are given below.

  • Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
  • push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
  • pop() removes the top item from the stack. It needs no parameters and returns the item. The stack is modified.
  • peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
  • isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
  • size() returns the number of items on the stack. It needs no parameters and returns an integer.
Stack + Queue == deque

A deque (pronounced deck) is a double-ended queue, which has features of both a stack and a queue. It’s useful when you want to add and delete items from either end of a
sequence. Here, we’ll work from both ends of a word to the middle to see if it’s a palindrome. The function popleft() removes the leftmost item from the deque and returns
it; pop() removes the rightmost item and returns it. Together, they work from the ends toward the middle. As long as the end characters match, it keeps popping until it reaches
the middle:

>> def palindrome(word):
…     from collections import deque
…     dq = deque(word)
…     while len(dq) > 1:
…        if dq.popleft() != dq.pop():
…            return False
…     return True
…
…
>>> palindrome(‘a’)
True
>>> palindrome(‘racecar’)
True
>>> palindrome(”)
True
>>> palindrome(‘radar’)
True
>>> palindrome(‘halibut’)
False

I used this as a simple illustration of deques.

If you really wanted a quick palindrome checker, it would be a lot simpler to just compare a string with its reverse. Python doesn’t have a reverse() function for strings, but it does have a way [::-1] to reverse a string with a slice, as illustrated here:

>> def another_palindrome(word):
…     return word == word[::-1] …
>>> another_palindrome(‘radar’)
True
>>> another_palindrome(‘halibut’)
False