Linked list implementation of Stack

Linked list implementation of Stack

1. LINKED LIST
IMPLEMENTATION OF
STACK
MODULE 3
DR. SINDHIA LINGASWAMY, VIT 1

2. DR. SINDHIA LINGASWAMY, VIT 2

3. •Thedrawbackofusingarraymethodisfixedsize,butin
thismethodit’sremoved.
•Thestoragerequirementoflinkedrepresentationofthe
stackwithnelementsisO(n)andthetypicaltime
requirementfortheoperationisO(1).
•Inalinkedstack,everynodehastwoparts:onethat
storesdataandanotherthatstorestheaddressofthe
nextnode.
•TheSTARTpointerofthelinkedlistisusedasTOP.
DR. SINDHIA LINGASWAMY, VIT
3

4. OPERATIONS
PushOperation:-
•The push operation is used to insert an element
into thestack.
•The new element is added at the topmost position
of thestack.
LinkedStack
DR. SINDHIA LINGASWAMY, VIT
4

5. •Toinsertanelementwithvalue8,wefirstcheckif
TOP=NULL.
•Ifthisisthecase,thenweallocatememoryforanew
node,storethevalueinitsDATApartandNULLinitsNEXT
part.
•ThenewnodewillthenbecalledTOP.
•IfTOP!=NULL,thenweinsertthenewnodeatthe
beginningofthelinkedstackandnamethisnewnode
asTOP.
8
Linked stack after inserting a newnode
DR. SINDHIA LINGASWAMY, VIT
5

6. ALGORITHM
TO PUSH AN ELEMENT INTO A LINKED
STACK
DR. SINDHIA LINGASWAMY, VIT 6

7. •InStep1,memoryisallocated
forthenewnode.
•InStep2,theDATApartofthe
newnodeisinitializedwiththe
valuetobestoredinthenode.
•InStep3,wecheckifthenew
nodeisthefirstnodeofthe
linkedlist.
•ThisisdonebycheckingifTOP=
NULL.IncasetheIFstatement
evaluatestotrue,thenNULLis
storedintheNEXTpartofthe
nodeandthenewnodeiscalled
TOP.However,ifthenewnodeis
notthefirstnodeinthelist,then
itisaddedbeforethefirstnode
ofthelist(thatis,theTOPnode)
andtermedasTOP.
Step 1: Allocate memory for the new
node and name it asNEW_NODE
Step 2: SET NEW_NODE -> DATA = VAL
Step 3: IF TOP =NULL
SET NEW_NODE -> NEXT =NULL
SET TOP =NEW_NODE
ELSE
SET NEW_NODE -> NEXT = TOP
SET TOP =NEW_NODE
[END OF IF]
Step 4:END
DR. SINDHIA LINGASWAMY, VIT 7

8. POPOPERATION
•The pop operation is used to delete an element
into thestack.
•The element is deleted at the topmost position of
thestack.
•However, before deleting the value, we must first
check if TOP=NULL, because if this is the case, then
it means that the stack is empty and no more
deletions can be done
DR. SINDHIA LINGASWAMY, VIT
8

9. •If an attempt is made to delete a value from a stack that
is already empty, an UNDERFLOW message isprinted.
•In case TOP!=NULL, then we will delete the node
pointed by TOP, and make TOP point to the second
element of the linked stack. Thus, the updated stack
becomes likethis.
Linked stack after deleting anode
TOP
DR. SINDHIA LINGASWAMY, VIT 9

10. ALGORITHM
TO POP AN ELEMENT INTO A
LINKEDSTACK
DR. SINDHIA LINGASWAMY, VIT 10

11. Step 1: IFTOP=NULL
PRINT“UNDERFLOW”
Goto Step5
[END OFIF]
Step 2: SET PTR =TOP
Step 3: SET TOP = TOP->NEXT
Step 4: FREEPTR
Step5:END
•In Step 1,we first check for
the UNDERFLOWcondition.
TOP!=NULL
•In Step 2,we use a pointer
PTR that points toTOP.
•In Step 3,TOP is made to
point to the next node in
sequence.
•In Step 4,the memory
occupied by PTR is given back
to the freepool.
DR. SINDHIA LINGASWAMY, VIT 11

12. PeekOperation
•The Peek operation is used to see the value of the
topmost element of the stack without deleting it
from thestack.
•Peekoperationfirstchecksifthestackisempty,
i.e.,ifTOP=NULL,thenanappropriatemessageis
printed,elsethevalueisreturned.
DR. SINDHIA LINGASWAMY, VIT
12

13. TO PEEK AN ELEMENT FROM A
LINKEDSTACK
•In step 1, ifTOP
•=NULL means that the stack is
empty.
•Else it will returnthe data on TOP,
which will be our output or Peeped
outValue.
Step 1: IF TOP =NULL
PRINT“UNDERFLOW”
ELSE
RETURNTOP->DATA
[END OFIF]
Step 2:END
DR. SINDHIA LINGASWAMY, VIT 13