Stack is linear list data structure which allows all operations at one end of the list. The operations are usually performed at one end called the top. The top item is inserted last. Any other item that is not at the top of the stack is not allowed to be accessed. Since we can access last item inserted in the list first stack is called to be a Last In First Out (LIFO) data structure.
Fig: Stack with top, insert and remove positions
Stack supports three operations- push, pop and top
Push operation
Inserts an item on top of the stack.
push(item) if top >= max items allowed //overflow throw error stack[top]=data top=top+1
Pop operation
Removes the item at the top from the stack and returns it.
Pop() if top<0 throw error item= stack[top] top=top-1 return item
Top operation
Returns the item at top of the stack
Top() if top<0 throw error //underflow return stack[top]
Stack operation example
Start with an empty stack [ | | | | | | ] top=-1 Push(15) [ 15 | | | | | | ] top = 0 Push(18) [ 15 | 18 | | | | | ] top = 1 Push(3) [ 15 | 18 | 3 | | | | ] top = 2 Pop() ---> returns 3 [ 15 | 18 | | | | | ] top = 1
Overflow and underflow
Stack usually has an upper limit of number of items that can be inserted before we run out of memory. If we try to push an item on the stack when stack is full and no more memory can be allocated an error condition is occured. This condition is known as overflow.
Another error condition occured when the stack is empty and pop() method is called. This is called underflow.
Fixed and Dynamic stack
Stack can be implemented such that maximum amount of memory that can be used is allocated when stack in created nad this amount is fixed. This type of implementation may use a fixed array.
Another implementation may allocate memory dynamically as the stack grows and overflow occurs only when the application can no longer allocate more memory. When items are popped from the stack the extra memory may be released. This type of application may use a linked list that grows and shrinks dynamically.
