Stacks!

First-In First-Out Friend

Stacks

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.

DATASTRUCTURES
datastructures data structures Stacks


Dialogue & Discussion