A stack is a linear data structure meaning that is is like a list except you can only add or remove data from one end of the list. For this reason a stack is a last-in first-out data structure (LIFO). A stack in computer science behaves in the same way as a stack of plates at a salad bar. The last plate put onto the stack is the first plate taken off. We cannot reach a plate in the middle of the stack without taking off all of the plates above it. A stack typically has operations such as the following
In an array based stack we store the data in an array. We use a special index named "top" to keep track of the top of the stack. Operations such as push( ), pop( ) and emptyStack( ) will need to make appropriate adjustments to the value of "top". A push operation will need to increment the value of "top", a pop( ) operation will need to decrement the value of top( ) and emptyStack( ) will need to set the value of top to -1.
In a linked stack we use nodes. Each node contains a data member and a pointer to the next node. We use an external pointer named "top" to keep track of the top of the stack. Once at the top of the stack we can follow the pointers to move from one node to the next to implement operations such as print( ) and emptyStack( ). A push( ) operation will need to link a new node to the top of the stack and adjust the pointer "top" to point to this new node. A pop( ) operation will need to remove a node from the top of the stack and adjust the pointer "top" to point to the top of the resulting smaller stack.