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.

Quick tip: If you wish to expand your Java skill-set and become an advanced Java developer, I highly recommend you to get yourself a copy of the best-selling Effective Java, by Joshua Bloch!

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *