top of page

Subscribe to Wisdom

Thanks for Subscribing!

  • Writer's picturePuru Uttam

Stack

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.

15 views0 comments

Recent Posts

See All

Comments


Modern Digital Watch
bottom of page