Abstract Data Types
Topic: Stack
Introduction of Stack
• A stack is a linear data structure in which all
the insertion(Push) and deletion(Pop) of data
or you can say its values are done at one end
only, rather than in the middle. ie. CD stack.
• Stacks can be implemented by using arrays of
type linear which is static Memory type and
Link List which dynamic memory type.
• Stack follows certain rules for insertion and
deletion.
• For Insertion: (FILO) First In Last Out
• For Deletion: (LIFO) Last In First Out
Basic Operation of Stack
• Push():Pushing (storing) an element on the stack.
• Pop():Removing (accessing) an element from the
stack.
• Peek():Return top most element of stock without
removing.
• isEmpty():check if stack is empty.
• isFull():check if stack is full.
Top: At all times, we maintain a pointer to the last PUSHED data
on the stack. As this pointer always represents the top of the
stack, hence named top. The top pointer provides top value of
the stack without actually removing it.
Logical Representation of Stack
• In empty Stack, always Top=-1. ie isEmpty=True
• After first push() operation Top will be
incremented by [Link] Top=Top+1 ie Top=0.
• pop() operation is carried out in an empty
stack is known as underflow condition.
• Push() operation carried out in a full stack is
known as overflow condition.
• If Top= StackSize-1 the isFull=True
Logical Representation of Stack
Empty Stack Full Stack
Size of the Stack=5 Size of the Stack=5
Push(4)
Push(1)
Push(5)
Push(6)
Top=4 7
Push(7)
6
5
15
4
Top=-1
Stack as Abstract Data type
The stacks of elements of any particular type is a finite
sequence of elements of that type together with the
following operations:
• Initialize the stack to be empty
• Determine whether the stack is empty or not
• Check whether the stack is full or not
• If the stack is not full, add or insert a new node at the top of
the stack. This operation is termed as Push Operation
• If the stack is not empty, then retrieve the node at its top
• If the stack is not empty, the delete the node at its top. This
operation is called as Pop operation
isfull() and isempty() Operation
Algorithm of isfull() function: Algorithm of isempty() function:
FUNCTION isfull () Return Boolean FUNCTION isempty () Return Boolean
If top = MAXSIZE -1 THEN If top < 0 THEN
Return True
Return True
Else
Else
Return False
Return False End if
End if END FUNCTION
END FUNCTION
Push() Operation
Push() Operation
A simple algorithm for Push operation can be derived as follows −
FUNCTION Push(data:INTEGER) Return Boolean
If top=Maxsize-1 THEN
Return False
Else
top ← top + 1
stack[top] ← data
Return True
End If
END FUNCTION
Pop() Operation
Pop() Operation
A simple algorithm for Pop operation can be derived as follows −
FUNCTION pop() Return Boolean
If top=-1 THEN
Return False
Else
data ← stack[top]
top ← top - 1
Return True
End If
END FUNCTION
Application of Stack
• Reverse a string. E.g. abcd
dcba
• Undo mechanism in text editor. E.g. abcde
Ctrl+z:abcd
Ctrl+z:abc
• Recursive Function.
• To check the balance of Parenthesis.
{
{
}
}
• Infix to postfix and Postfix to prefix.
PUSH( ) Operation in Python
POP( ) Operation in Python