First-In First-Out Friend
Stack 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. Examples
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.
Two operations
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
Auxiliary operations
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.
Famous Applications
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
Implementation Strategy
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.
תגובות