stacks data structure by mayukh datta

Stack is a linear data structure. It follows LIFO (Last-in, First-out) policy. It has two main operations - push (insert element onto stack) and pop (delete element from stack). Stack has two exceptions - underflows (if we attempt to pop an empty stack) and overflows (trying to push an element on a full stack).

The concept of data structures have been taken from the real world. So, let's dive into an instance from the physical world: the picture shows a stack of books. There are n (n is 6) books (elements) in total. Let's index the books with numbers starting from 0 to n-1. The first book placed on the table is "Rain in the Mountains" whose index is 0 and the latest book placed is "The Da Vinci Code" with index 5. Now, if we remove the last placed book (executing pop) then the topmost element becomes the book with index 4. Now, if we place the previously removed book (executing push) on top of the stack then the topmost element will have index 5. This is how it follows LIFO policy, every time the last inserted element gets removed first from the stack. We cannot remove or insert a book from otherwise positions, doing so would break the rule of sequential access.

Suppose, you have a box with size limit of keeping only 6 books. When the box is full and you try to insert another book, as there is no space, this would be an exception (overflows). Likewise, when the box is empty and you think of fetching a book from the box, as it has nothing, this would also be an exception (underflows).

That's all about how stacks work :)

The most interesting application of stack to me is the support it provides for recursion. It is also used for undo sequence in text editors, matching tags in HTML and XML, etc.

There are two common ways in which stacks are implemented:-
  • With simple array - here the size of the stack must be predefined. Resizing is not allowed.
  • With linked list - resizing is allowed here and this is the advantage over simple array implementation.

Code for simple array implementation of stack:-

Code for linked list implementation of stack:-


Post a Comment