Stacks - Eishaaya/GMRDataStructuresTest GitHub Wiki

What is a Stack?

A stack is a data structure that stores data in a way that is similar to that of a linked list in that the nodes are ordered in a linear manner. However, stacks have a unique characteristic called last-in-first-out (LIFO). This means that the first object to enter the stack is the last object that is accessible. You would have to “pop” everything off the stack to reach the first object that you placed onto the stack. In other words, data can only be placed and accessed from the “top” of the stack. Like a stack of papers in real life.

To ensure that the LIFO ordering is maintained, certain constraints must be placed on how the data can be accessed. There are two ways to manipulate data in a stack: pushing and popping. Objects can either be pushed onto the stack or popped off from the top of the stack. Often times peeking is used to see the top-most object in the stack.

There are two ways to implement a stack data structure. One way is to back the stack using a doubly linked list to store all the data. The other is an array-backed stack which stores all the data in the array.

Linked-List backed Stack:

public class Stack<T>
{
  public int Count { get; private set; }
  private LinkedList<T> data;
  
  public Stack() { ... }
  public void Push(T value) { ... }
  public T Pop() { ... }
  public T Peek() { ... }

  // Optional Functions
  public void Clear() { ... }
  public bool IsEmpty() { ... }
}

Array backed Stack:

public class Stack<T>
{
  public int Count { get; private set; }
  private T[] data;

  public Stack(int capacity = 10) { ... }
  public void Push(T value) { ... }
  public T Pop() { ... }
  public T Peek() { ... }
  private void Resize(int size) { ... }

  // Optional Functions
  public void Clear() { ... }
  public bool IsEmpty() { ... }
}

Implementation Guide

Push

Always add items on the top of the stack:

  • Linked-List: Use the head or the tail of the list as the top of the stack. Just AddFirst or AddLast.
  • Array: Either end of the array can be used as the top or bottom of the stack; just keep an integer variable to represent the index that is the top of the stack. Add the new element at the next available spot in the array. If there are no more spots in the array, double the size of the array with the Resize function.

Pop

Always remove elements from the top of the stack:

  • Linked-List: The head/tail is the top of the stack so just remove the head/tail and return it's value.
  • Array: Clearing the value at the top of the stack from the array is not necessary. All that is needed is to move the integer variable that represents the top of your stack and return the value. When the number of in-use elements in the stack is 1/4 the size of the array, we can call the Resize function to reduce the size of the array to 1/2 in order to save space. Just don't copy the values we didn't clear earlier!

Peek

  • Return the element at the top of the stack (not the node if using a linked list).

Stacks are used in everyday applications to manage the "stack" for recursion (yes, that is a stack) and ordered placement of objects in diagrams.

Assignments to be done with a Stack

Easy:

  • Array Backed Stack
    • Implement a stack using an array to store the values instead of a linked list.

Hard:

  • Undo/Redo
    • Create a simple text editor or paint project that allows for undo and redo operations.

Very Hard:

  • Tower of Hanoi
    • A mathematical puzzle, solvable by stacks see link.

References

<-- Previous | Next -->