A stack is an abstract data type(ADT) in form of ordered list in which insertion and deletion are done at one end, called top. It follows the LIFO/FILO principle (Last In First Out/First In Last Out) as last element inserted is the first one to be deleted. Objects can be inserted into a stack at any time, but only the most-recently inserted (that is, “last”) object can be removed at any time.
- Piles of plates in a restaurant. The plates are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is taken from the top of the stack. The first plate placed on the stack is the last one to be used.
- Web browser stores the address of last visited websites on a stack. As & when user visit a new site, its address is pushed on to the stack.
As stack is an abstract data type, all operations on stack are abstract in nature & real implementation is hidden.
- Push (o) - Insert an object o at the top of the stack if stack is not full else full-stack exception
- Pop () – Remove & return the top object of the stack. This is the most recent object added to the stack. Stack-empty exception in case stack is empty
- Size() – returns the current size of the stack
- IsEmpty() – returns a boolean true if stack is empty i.e. no objects in stack
- IsFull() – returns a boolean if stack is full i.e. there is an object at the top of the stack & top is pointing to size of the stack.
- Top() – return the top element of the stack without removing it.
- Balancing of symbols
- Infix-to-postfix conversion
- Evaluation of postfix expression
- Implementing function calls (including recursion)
- Finding of spans (finding spans in stock markets, refer to Problems section)
- Page-visited history in a Web browser [Back Buttons]
- Undo sequence in a text editor
- Matching Tags in HTML and XML
- Simple Array Based
- Linked List Based
Array vs. Linked List Implementation
Array Implementation - Operations take constant time. - Expensive doubling operation every occasionally. - Any sequence of n operations (starting from empty stack) amortized bound takes time proportional to n.
Linked List Implementation - Grows and shrinks gracefully. - Every operation takes constant time O(1). - Every operation uses extra space and time to deal with references.
Dimit Chadha DATASTRUCTURES
datastructures data structures Stacks