Stack

A stack is a very commonly used ADT. It is so named because it resembles a stack of plates used in a restaurant. In such a stack, a plate that has been washed and put last would stay on top. This would be the first plate to be picked up when a plate is needed. The plate that went in first would be at the bottom of the stack and would be picked last. So, the last plate to be placed in the stack is the first plate to get out, we can also call this last in first out (LIFO).

Similarly, a stack ADT has a protocol where the last value that is put in it must be returned on the first attempt to get a value out, and the value that went in first must come out last. The following figure will make it more clear:

The operation of putting a new value in a stack is called push, and the operation of retrieving a value from a stack is called pop. The element that was pushed last must be popped first. The operation that allows one to see what the next pop will return is called peek. The peek operation...