# What is a stack?

In this article we give you a description of what a stack is, and when this type of data structure is used. At the end of the article, we implement a custom stack in Java.

Let’s start this one of with an analogy:

Assume you have a **stack** of bills, which we’ll call a **bill-stack.** You want to go through your bills, one by one. The most obvious choice would be to look at the first bill on your **bill-stack.** When you’re done with your first bill, you remove it from your bill-stack, and continue with the next bill in the stack.

Now, let’s say you didn’t have time to go through all your bills, and decided to wait a few days before you pay for the rest of them. In the mean time you received a few more bills, which you placed **on top** of your bill stack. The next time you decide to go through your bills, you start of with the ones you recently inserted, and work your way **down **through the stack.

Moving on to the actual data structure.. A stack is a linear data structure, which only allows access to the last inserted item. The most recent item added to a stack is easily accessible, and you have to remove the most recent item to access the next item.

The order of a stack is either LIFO (Last In, First Out) or FILO (First In, Last Out).

This implies that we want to use a stack whenever we want access to the last inserted item. Said in other words, the stack data structure is appropriate if we only want access to the last item inserted.

That is really all there is to a stack. Let’s have a look at the operations supported by this handy data structure.

## Stack operations

In order to implement a stack, we need to support both *insertion at the top of the stack*, and *removal of the item at the top of the stack.
*Moving back to the previous analogy, let’s assume you want to have a look at the bill at the top of your

**bill-stack,**but you don’t want to throw it away just yet. This can also happen quite frequently with an actual stack, which tells us that we should also implement a method which allows us to

*have a look at the item on top of the stack, without removing it.*

The 3 most basic operations which should be supported by a stack is thus:

**Push:**Pushing an item to the stack, placing it on top.**Pop:**Removing the last inserted item from the stack.**Peek:**Looking at the the last inserted item, without removing it from the stack.

Keep in mind that these are just the characteristic operations of a stack. In addition to these operations, one should also implement other convenient methods (checking whether the stack is empty, for example).

## Analysis of the stack data structure

If you’re unfamiliar with basic algorithm analysis, and Big-Oh notation, have a look at this introduction the algorithm analysis.

The stack is a basic, linear data structure. As previously mentioned, the supported operations of are **push, pop **and **peek. **Let’s have a look at these three operations, in terms of their efficiency. What is their actual run-time?

Each of the three operations run in constant time, **O(1)**. This is as good as it gets, which suggests that a stack is a **highly efficient **data structure. But how come each operation run in constant time?

Let’s assume the stack is implemented with an **array**.

Whenever we **push** items to the stack, we place them at “the end” of the array, at the highest index. This obviously takes constant time, as we only need to know the size of the array prior to insertion, and insert the object at the arrays size + 1.

**Proof:
**Assume you have an array with

*n*objects. This implies that the length of the array is equal to

*n.*To insert an item at the end of the array, you place the item in index-position

*n + 1.*This takes constant time, as there is no need to iterate through the array (assuming the arrays length is already known).

Whenever we **pop **(remove) an item from the stack, we simply remove from “the end” of the array. This also takes constant time, as we only need to remove the object at the highest index-position in the array.

**Proof:**

Assume you have an array with *n *objects. This implies that the length of the array is equal to *n. *To remove an item from the end of the array, you remove the item at index-position *n.* This takes constant time, as there is no need to iterate through the array (assuming the arrays length is already known).

The same also goes for the **peek **operation. We perform the exact same steps as with the **pop **operation, but instead of removing the item, we return it without altering the stack.

## When to use a stack

A stack has a whole lot of applications in computer science. As a rule of thumb, whenever it is considered convenient to get fast access to the last inserted object, you use a stack.

Some applications of the stack data structure is:

- Balanced symbol checker, used in compilers etc.
- Infix to postfix conversion (evaluating mathematical operators and operands)
- Backtracking
- Memory Management

## How to implement a stack

There are two common ways to implement a stack. You can implement a stack using an **array**, or by using a **linked list**.

The most intuitive way to implement it, in my opinion, is by using an **array**. When implementing a stack with an array, you don’t get memory overhead, as you do with linked lists (because of the reference between the nodes).

However, the array does have some drawbacks compared to the linked list. The drawback is that with an array, assuming you implement it in Java, you *can’t guarantee that the insertion is done in O(1), constant time. *The reason for this is that arrays in Java have a fixed size. If you the array is full, you have to resize the array – this includes copying, and is done in O(N).

In this article we implement the stack with an array. The same principles can of course be used to implement it with a linked list.

## Java implementation of a Stack.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | package stack; import java.util.Arrays; import java.util.NoSuchElementException; /** * Custom implementation of a Stack in Java. * The stack is represented with an array. * The operations supported by the Stack is: * <p> * push(): Pushing an item to the stack, placing it on top. * pop(): Removing the last inserted item from the stack. * peek(): Returning the last inserted item, leaving the stack unaltered. * * @author Anders Engen Olsen.com */ public class Stack<AnyType> { // Initial size of the array private final static int INIT_SIZE = 10; // Inner data structure for the stack private AnyType[] array; // Helper variable, keeping track of the top of the stack. private int stackTop = -1; /** * Constructor. Creating an empty stack. No parameters. */ public Stack() { this(INIT_SIZE); } /** * Constructor. Creating an empty stack with given size. * * @param size size of the stack */ public Stack(int size) { array = (AnyType[]) new Object[size]; } /** * Inserting an item at the top of the stack. * The method checkCapacity ensures that the array is not full. * * @param x item to insert * @see #checkCapacity(int) */ public void push(AnyType x) { checkCapacity(stackTop + 1); array[++stackTop] = x; } /** * Returning and removing the item at the top of the stack. * * @return item at top * @throws NoSuchElementException empty stack */ public AnyType pop() { if (isEmpty()) throw new NoSuchElementException("Empty stack"); return array[stackTop--]; } /** * Returning item at the top of the stack. Stack is unaltered * * @return item at top * @throws NoSuchElementException empty stack */ public AnyType peek() { if (isEmpty()) throw new NoSuchElementException("Empty stack"); return array[stackTop]; } /** * Checking whether the stack is empty or not. * * @return true if empty */ public boolean isEmpty() { return stackTop == -1; } /** * Checking the capacity of the internal array. * If the array is full, we expand it by doubling it's size. */ private void checkCapacity(int size) { if (size == array.length) { // Creating new array, twice the size. int previousSize = array.length; int newSize = previousSize * 2; array = Arrays.copyOf(array, newSize); } } } |