Page 83 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes {
printf ( “\n” ) ;
/* traverse the entire linked list */
while ( q != NULL )
{
printf ( “%2d “, q -> data ) ;
q = q -> link ;
}
printf ( “\n” ) ;
}
/* counts the number of nodes present in the linked list representing
a stack */
count ( struct node * q )
{
int c = 0 ;
/* traverse the entire linked list */
while ( q != NULL )
{
q = q -> link ;
c++ ;
}
return c ;
}

3.4 Summary

Stack is a linear data structure having a very interesting property that an element can be
inserted and deleted not at any arbitrary position but only at one end. One en d of a stack
remains sealed for insertion and deletion while the other end allows both the operations.
A stack possesses LIFO (Last In First Out) property. There are two basic methods for the
implementation of stacks – one where the memory is used statically and the other where
the memory is used dynamically.
Push is a stack operation in which an element is added to a stack.

Pop is a stack operation that removes an element from the stack.
Stack is used to store return information in the case of function/procedure/subroutine

calls. Hence, one would find a stack in architecture of any Central Processing Unit (CPU).
In infix notation operators come in between the operands. An expression can be evaluated

using stack data structure.
3.5 Keywords

Infi x: Notation of an arithmetic expression in which operators come in between their operands.
LIFO: (Last In First Out) The property of a list such as stack in which the element which can be
retrieved is the last element to enter it.
Pop: Stack operation retrieves a value form the stack.

78 LOVELY PROFESSIONAL UNIVERSITY