General Discussions

Formal Definition of Stack DS

If you know the definition of stack, then you can go ahead and understand it formally. But before that lets see the operations on Stack:

Si. No. Name Description of the

Operation

1. PUSH Insert an item into the stack.
2. POP Delete an item from the stack.
3. PEEK Look out for the top most item from the stack.
4. UNDERFLOW Stack is empty. PEEK / POP are not allowed.
5. OPERATIVE PUSH / POP / PEEK operations are allowed.
6. OVERFLOW Stack is full. PUSH is not allowed.

We can define stack S, with following tuples:

S = <Q, Qo, I, O, δ >
Q = {Underflow, Operative, Overflow}
Qo = Underflow
I = Input Items of specified data type
O = {Push, Pop, Peek}
δ =

stack-transition

Quick Review:
S = <Q, Qo, I, O, δ >
Q = set if states                     I = Input                                  δ = Transition Diagram
Q0 = initial state                    O = Set of operations

Let us talk a little more about the transition diagram. The δ is the abstraction of the operations. It does not cover the implementation constraints. It only describes the possible moves from each state when a user issues an operation. For example, while in ‘Operative’ state, the transition to ‘Overflow’ happens on ‘Push’ only if the stack is full, otherwise it transits back to ‘Operative’ state. A ‘Peek’ operation just looks at the top of the stack, returns result to user and transits back to the same state. Similar other constraints follow. The implementer has to carefully achieve the operations by adhering to stack operative conditions.

Advertisements

Let me Know What you Think!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s