Data Structures and Algorithms 101 part one: Stacks

Sakis Kasampallis | Sep 23, 2012 min read

Rationale (boring)

I decided to write down some notes about common (and maybe less common) Data Structures and Algorithms. This is the first part, covering stacks.

Definition

Think of a stack as a pile of books.

A stack looks like a pile of books
If I want to study "Modern Operating Systems", I first need to take away all the books that are on top of it (both "ARM microcontrollers" and "The UNIX programming environment"). Conversely, whenever I finish studying a book the easiest place to put it is on top of the most top book (thus above "ARM microcontrollers").

In stack terminology, adding a new item means pushing it to the top of the stack, while removing an item means popping it from the top of the stack.

Fundamental stack operations

Stacks provide direct access only to their top element, which happens to also be the last (most recent) element that was pushed in the stack. For that reason, we call stacks Last In First Out (LIFO) data structures.

Usage and performance

Why are stacks useful? There are numerous practical applications of stacks on Wikipedia. A simple example is adding two numbers using a calculator. Implementation details of such an application are outside the context of this article.

The good thing about stacks is that pushing and popping an item is very fast. Specifically, pushing and popping are constant time - O(1) operations. On the other hand, stacks are not optimized for searching or adding/removing an item from an arbitrary position. Searching and adding/removing from arbitrary stack positions are linear time - O(n) operations.

Implementation

Stacks are usually implemented using arrays, but since I am using python I will use the built-in list data structure for holding and accessing the items of the stack.

If [::-1] looks strange to you, it's a nice way of using extended slices for reversing a sequence. In this representation, the top element of the stack is the left-most element of the printed list. The peek (aka top) function returns the top element of the stack without removing it.

Sample problem

Implement a function that sorts a stack in ascending order. You are only allowed to use an extra stack and the fundamental operations push, pop, peek, and size. 

The algorithm presented here sorts the stack in quadratic - O(n^2) time. The idea is to pop an element from the unsorted stack and push it to the "right" position of the sorted stack. Exhaustive error checking (for example ensuring that unsorted is a stack, etc.) is omitted for simplicity.

Since we only have access to the top item, when the top item of the unsorted stack cannot be pushed to sorted stack (because it violates the sorting order), we move all the items of the sorted stack to the unsorted stack until the "right" position is found.

 References