What is a Stack?

nikoo28

11 years ago

A stack is a simple data structure for storing data (similar to Linked List). The most important attribute of this data structure is that the order in which the data arrives is maintained. A pile of plates at a cafeteria is a very good good example.

Suppose you are eating at this cafeteria. As soon as you are done, you keep the plate at the counter for it to get washed. Any person that comes after you, will keep the plate on TOP of the plate you just kept. Hence, any new plates that are added to this stack can only be added to the top of the previous plate. The last person to eat would keep the plate at the very last and his plate would be at the very TOP.

Now, when we start to clean the plates, we will first pick the plate at the TOP. This means that the last plate to get in the stack became the first one to be cleaned.

Definition:

A stack is an ordered list in which insertion and deletion are done at one end, where the end is called as top. the last element inserted is the first one to be deleted. Hence, it is called LAST IN FIRST OUT (LIFO) or FIRST IN LAST OUT (FILO) list.

A stack can be made out of any type of elements, but since we talk about it in computer science and programming, it only consists of a single datatype. Hence, you can have a stack of integers, strings, characters etc.

Building a Stack:

Just like the example of plates, we can make a stack using two types of operations. Either you add a plate, or you remove the plate. Note that, you cannot perform any other operation. It is not possible to remove a plate from anywhere in between the stack. These operations have special names:

PUSH:- In this operation, we add an element on top of the previous element such that the new element is now the TOP element. Similar to adding a new plate on top of the existing plates.
POP:- This is the deletion operation, when this operation is called, we simply return the TOP element and then delete it from the stack. Similar to taking a plate for cleaning and then removing it from the dirty dishes.

In some cases, you might have a limited memory available. Hence, if you reach the memory limit and still try to push a new element, you might get a StackOverflow exception. Similarly, if the stack is empty, and you try to do a POP operation, you will get a StackUnderflow exception.

Here is a visualization in two operations PUSH and POP.

Fig: Visualization of PUSH and POP operation

Examples of STACK in real life

Consider a working day in the office. Let us assume a developer is working on a long-term project.

|                      |
| -------------------- |
|  long-term project   |       <- TOP
| -------------------- |       < -- Stack formed in developer's mindCode language: plaintext (plaintext)

The manager then gives the developer a new task, which is more important. The developer places the long term project aside and begins working on the new task.

|                      |
| -------------------- |
|       new task       |       <- TOP
| -------------------- |
|  long-term project   | 
| -------------------- |       < -- Stack formed in developer's mindCode language: plaintext (plaintext)

The phone then rings and there is an urgent requirement. The developer then PUSHES the current task in the pending tray and begins the urgent task.

|                      |
| -------------------- |
|      phone call      |       <- TOP
| -------------------- |
|       new task       |
| -------------------- |
|  long-term project   |
| -------------------- |        < -- Stack formed in developer's mindCode language: plaintext (plaintext)

When this urgent task is finished, he POPS the task from pending tray and completes the new task that was assigned to him. If you look at the mind stack, you can see that the developer is looking only at the TOP task.

Once that is completed, he POPS the task from pending tray again and resumes his long-term project.

Common operations:

push ( ) : Add a new element. So, in the above example, a new element will go on TOP of 3.
pop ( ) : Remove an element. Hence, it will remove 3.
peek ( ) / top ( ) : Just look at the top element. This is similar to pop() but the element is not deleted.
isEmpty ( ) : Returns true if the stack is empty. Used to prevent exceptions.
isFull ( ) : Returns true if the stack is full.

Video Explanation:

Watch this video to see a demonstration of how a stack is actually formed. You will also see all the operations done on it. Also, a hidden bonus of how the UNDO operation works.