NPTEL -Lecture 2(Stacks)

So Day 2 sat through the Stacks Lecture and here are the notes

Stacks

Abstract Data Type - Here is the fancy defintion , ADT is a mathematically specified entity that defines a set of its instances with:

A specific interface - a collection of signatures of operations that can be invoked on an instance
A set of axioms ( preconditions and postconditions) that define the semantics of the operations ( i.e. what the operations do to the instance of ADT, not how)

so in terms of Java ADT is pretty much like a Interface with decent JavaDoc

There are three types of operations
Construction (Constructor in Java)
Access functions ( something like a getter(), list())
Manipulation functions (something like a setter(), put(), add())


Stack
LIFO Datatype

operations on a stack , new - creates it, push - pushes , pop - pops, top - just reads the top most element without removing it, size - gives the size, isEmpty - checks if Empty

Formally axioms will be defined like this for example
Pop(Push(S,v)) = S
Top(Push(S,v)) = v

Stack interface in Java and some basics of Exceptions was covered

Creating an Array based stack in Java and it's implementation was shown


All methods of Stack run at O(1) - so Stack is very efficient

Example of Calculating the Stock Span i.e. If you have an array of daily stock prices , create another array such that for each element in the stock price array you have a corresponding element for the Span of that day. For example let us say the stock prices varied like this {10, 3,1,8,3,2 }, Span is defined as the difference between current day index and the index of the last day when the stock price is greater than the current day , for example Span for the day Stock price was 2 is 1 , for 8 it is 3

1)First approach using loop of loops so order was O(n**2)
2)More efficient Stack approach where order was O(n)


A growable ArrayBased Stack, Everytime the Stack is full you increase the size
1)Tight Strategy - Add the constant to the current max size and create a new Stack -O(n**2/c) where c is the constant
2)Growth Strategy - Double the size of Stack everytime is full - O(n)

So growth Strategy is a better option