Stack is the other common linear data structure which is been used now a days. Just like we did with the ordered list, we will examine the abstract view of the stack first and then look at the couple of ways a stack can be implemented.

By seing the figure above you can see that this data structure is really a restricted list. You have restricted the access to one end of the list by using the pop and push operations. The result of this restriction is that items in the list will be stored one on top of the other. We must first remove all the items above it till you get to the bottom item. "Last-In, First-Out" or LIFO, which is used to describe the behavior, since the last item to enter the stack is the first item to leave the stack. The top item is the item always the last item to enter the stack and it is always the first item to leave the stack since no other items can be removed until the top item is removed.

In order to implement a stack using pointers, we need to link nodes together just like we did for the pointer implementation of the list. Each node contains the stack item and the pointer to the next node. We also need a special pointer(stack pointer) to keep track of the top of our stack.

push(new-item:item-type)

All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).