4. Stacks

Written by Kelvin Lau & Jonathan Sande

Stacks are everywhere. Here are some common examples of things you would stack:

• pancakes
• books
• paper
• cash

The stack data structure is identical in concept to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the top-most item.

Stack Operations

Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.

There are only two essential operations for a stack:

• push: Add an element to the top of the stack.
• pop: Remove the top element of the stack.

Limiting the interface to these two operations means that you can only add or remove elements from one side of the data structure. In computer science, a stack is known as a LIFO (last-in-first-out) data structure. Elements that are pushed in last are the first ones to be popped out.

Stacks are used prominently in all disciplines of programming. To list a couple:

• Memory allocation uses stacks at the architectural level. Memory for local variables is also managed using a stack.
• Programming languages that support recursion manage the function calls with a stack. If you accidentally write an infinite recursion, you’ll get a stack overflow. Perhaps you’ve heard of a website that goes by that name. :]
• Search and conquer algorithms, such as finding a path out of a maze, use stacks to facilitate backtracking.

Implementation

Open up the starter project for this chapter. In the root of the project add a folder named lib, and in that folder create a file named stack.dart.

Note: If you are using DartPad rather than a full IDE, then just create your Stack class outside of the main function.

Then add the following code to stack.dart:

class Stack<E> {
  Stack() : _storage = <E>[];
  final List<E> _storage;
}

Here, you’ve defined the backing storage of your Stack. Choosing the right storage type is important. List is an obvious choice since it offers constant time insertions and deletions at one end via add and removeLast. Usage of these two operations will facilitate the LIFO nature of stacks.

For those unfamiliar with generics, the E in the code above represents any data type that you might want to put in your stack, whether that be String, int, double or your own custom type. While you don’t have to use the letter E, it’s customary to do so when you’re representing the elements of a collection.

You’ll want to observe the contents of the stack later on, so also override toString inside the class:

@override
String toString() {
  return '--- Top ---\n'
      '${_storage.reversed.join('\n')}'
      '\n-----------';
}

This will list all of the elements in _storage with the last one at the top.

Push and Pop Operations

Add the following two operations to your Stack:

void push(E element) => _storage.add(element);

E pop() => _storage.removeLast();

Calling push will add an element to the end of the list while pop will remove the last element of the list and return it.

Open bin/starter.dart and import your new stack at the top of the file:

import 'package:starter/stack.dart';

If you’re using your own project, just change starter to whatever your project name is.

Then test your stack in the main function of bin/starter.dart:

final stack = Stack<int>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
print(stack);

final element = stack.pop();
print('Popped: $element');

You should see the following output:

--- Top ---
4
3
2
1
-----------
Popped: 4

push and pop both have O(1) time complexity.

Non-Essential Operations

There are a couple of nice-to-have operations that make a stack easier to use.

Adding Getters

In lib/stack.dart, add the following to Stack:

E get peek => _storage.last;

bool get isEmpty => _storage.isEmpty;

bool get isNotEmpty => !isEmpty;

peek is an operation that is often attributed to the stack interface. The idea of peek is to look at the top element of the stack without mutating its contents.

Creating a Stack From an Iterable

You might want to take an existing iterable collection and convert it to a stack so that the access order is guaranteed. Of course it would be possible to loop through the elements and push each one. However, you can add a named constructor that just sets the underlying private storage.

Add the following constructor to your stack implementation:

Stack.of(Iterable<E> elements) : _storage = List<E>.of(elements);

Now, run this example in main:

const list = ['S', 'M', 'O', 'K', 'E'];
final smokeStack = Stack.of(list);
print(smokeStack);
smokeStack.pop();

This code creates a stack of strings and pops the top element “E”. The Dart compiler infers the element type from the list, so you can use Stack instead of the more verbose Stack<String>.

Less Is More

Since Stack is a collection of elements, you may have wondered about implementing the Iterable interface. After all, List and Set and even the keys and values of a Map are all iterable.

However, a stack’s purpose is to limit the number of ways to access your data, and adopting interfaces such as Iterable would go against this goal by exposing all the elements via the iterator. In this case, less is more!

Stacks are crucial to problems that search trees and graphs. Imagine finding your way through a maze. Each time you come to a decision point of left, right or straight, you can push all possible decisions onto your stack. When you hit a dead end, simply backtrack by popping from the stack and continuing until you escape or hit another dead end. You may want to try your hand at that sometime, but for now, work through the challenges in the following section.

Challenges

A stack is a simple data structure with a surprisingly large number of applications. Try to solve the following challenges using stacks. You can find the answers at the end of the book and in the supplemental materials that accompany the book.

Challenge 1: Reverse a List

Create a function that prints the contents of a list in reverse order.

Challenge 2: Balance the Parentheses

Check for balanced parentheses. Given a string, check if there are ( and ) characters, and return true if the parentheses in the string are balanced. For example:

// 1
h((e))llo(world)() // balanced parentheses

// 2
(hello world // unbalanced parentheses

Key Points

• A stack is a LIFO, last-in first-out, data structure.
• Despite being so simple, the stack is a key data structure for many problems.
• The only two essential operations for a stack are push for adding elements and pop for removing elements.
• push and pop are both constant-time operations.