Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

4. Stacks
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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 topmost item.

Good news: a stack of pancakes with butter on top. Bad news: you have to eat the butter first.
Good news: a stack of pancakes with butter on top. Bad news: you have to eat the butter first.

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. You’ll learn more about this in Chapter 7, “Recursion”.
  • 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.

class Stack<E> {
  Stack() : _storage = <E>[];
  final List<E> _storage;
}
@override
String toString() {
  return '--- Top ---\n'
      '${_storage.reversed.join('\n')}'
      '\n-----------';
}

Push and Pop Operations

Add the following two operations to your Stack:

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

E pop() => _storage.removeLast();
import 'package:starter/stack.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');
--- Top ---
4
3
2
1
-----------
Popped: 4

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;

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.

Stack.of(Iterable<E> elements) : _storage = List<E>.of(elements);
const list = ['S', 'M', 'O', 'K', 'E'];
final smokeStack = Stack.of(list);
print(smokeStack);
smokeStack.pop();

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.

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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now