What is a stack?

A Stack is a structure that can be implemented with arrays as well as linked lists. It is a sort of a bucket where the value you enter will be added at the bottom. The next item that you add to a stack will be kept just above the item that was added previously. The procedure of adding a value to the stack is called a push operation and the procedure of getting a value out of the stack is called a pop operation. The location where the value can be added or taken out of the stack is pointed at by a pointer called top. The value of the top pointer is -1 when the stack is empty:

Figure 3.1

When the push operation is executed, the value of top is incremented by 1, so that it can point to the location in the stack where the value can be pushed:

Figure 3.2

Now, the next value that will be pushed will be kept above value 1. More precisely, the value of the top pointer will be incremented by 1, making its value 1, and the next value will be pushed to the stack[1] location, as follows:

Figure 3.3

So, you can see that the stack is a Last In First Out (LIFO) structure; that is, the last value that was pushed sits at the top.

Now, when we execute a pop operation, the value at the top, that is, value 2, will be popped out first, followed by the popping out of value 1. Basically, in the pop operation, the value pointed at by the top pointer is taken out, and then the value of top is decremented by 1 so that it can point at the next value to be popped out.

Now, that we've understood stacks, let's begin with the first recipe.