Stacks

A Stack in computer science is quite similar to a stack in real world with some strictness in how one is used. Imagine a stack of books, like so:

image of stack of books

How to work with a Stack?

You want to get the book on the top. What do you do?

You pick it up, right?

You want to get the second book from the top. How do you get it?

You remove the 1st book from the top and pick the second book (which is now on the top).

How do you get the 5th book from the top?

You remove the first four books from the top and pick up the 5th one.

To fetch the one at the bottom, you need to remove all the books on the top and then get pick up the last one.

That was about removing books from the stack. How do you add new ones?

Simple - you place the new ones on top of the existing ones.

Rules of the Stack

In computing, a stack works the same way. There are basically two operations:

  1. Push: New elements are added on the top of the stack.
  2. Pop: Removing elements happens at the top.

Thus, if you want to add or remove elements from a stack, you do so on the top of the stack. Due to this behavior, Stacks are sometimes referred to as the LIFO (Last In First Out) data structure.

Most of the times Stacks are implemented using Arrays, though they can also be implemented using Linked Lists.

Usage

Stacks are at more locations than you can think of. One of the prime usages of stacks is in reusing the code that we humans write. Most programming laguages have these resusable pieces of code named functions. Sometimes a function calls another function. For example, a function which can print a multiplication table can call the function which actually does the multiplication. Everytime a function is called by another function and expects the called function to return a value, a call stack is created. If the nested function calls yet another function, a new call is added to the stack. When the last function called produces a value and returns, the corresponding call is removed from the stack.

This methodology is at the core of how computers operate; and hence, stacks are one of the most important data structures. When debugging code, knowing the call stack can be immensely useful.

Updated: