Stacks and Queues

Stacks and Queues-

              The linear data structure such as an array or linear list allows us to insert and delete an element at any place, namely either at the beginning or at the end or in the middle of the linear list. It is possible that we need a data structure which takes operations on only one end i.e. either at the beginning or at the end of the list Stack and Queue two such types of data structure which take operation only at the ends or at the beginning of the list.

Stack:-

              A stack is a linear data structure. But in this data structure elements are added to and removed only from one end of the list i.e. top of the stack. Thus stack provides the information in the reverse of the entry order, so it is called the last-in-first-out (LIFO) list.

              The operation of removing an entry from a stack is called a pop operation. If the elements are added continuously to a stack, it grows at the top end. New items are pushed on the top of the stack.

                           Representation of stack after inserting element

                          Representation of stack after inserting element

Type of Linked List, Singly linked list, Doubly Linked List, Circular Linked List

Type of Linked List:-

           There are three types of linked list:-

·       Singly linked list
·        Doubly linked list
·        Circular linked list

Singly linked list:-

          In This type of linked list, each node contains two fields i.e. data and a link pointing to the next node in the list.

The first node in the list is pointed by a start pointer. The node in the list has a link pointer field containing a Null.

Doubly Linked List:-

           In this type of linked list, each node contains and two links, one link pointing to the previous node and one link pointing to the next node. Doubly linked list can be traversed forward as well as well as backward.

Circular Linked List:-

          Circular linked list are the linked lists which are obtained by linking the last node of the linked list to the first node of the list. In circular linked list, the last node does not contain the NULL pointer. Instead it contains the pointer of the first node.

Linked List, Advantages and Disadvantages of linked list

Linked List:-

          A linked list is the chain of nodes or date items connected by pointers and each node contains a pointer pointing to the address of next node or data item. A linked list is an ordered list of data items.

          A link list is a collection of records of the same data type, and all such records are connected through pointers each record in a linked list has a pointer field pointing to the next record in the list. The pointer field in the last record of the list is assigned the null value. A pointer variable is used to point to the first record in the list.

Advantages of linked list:-

• It is not necessary to know in advance the number of elements to be stored in the list and therefore, need not allocate. d as and when necessary.
• In a linked list, insertions and deletions can be handled efficiently without fixing the size of the memory in advance.
• An important advantage of linked lists over arrays is that the linked list uses exactly as much memory as it needs, and can be made to expand to fill all available memory locations if needed.

Disadvantages:-

• The traversal is sequential.
• Increased overhead for storing pointers for linking the data items.

Unions

Unions:-

          Structure data type is so defined that it is able to accept heterogeneous data type. Thus structure data type allows to pack together different types of data values as a single unit. Unions are also similar to structure data type except that the members are over laid one on top of another, so members of a union data type share the same memory.

          Unions obey the same syntactic rules as structures. We can access elements with either the dot operator (.) or right arrow operator (à). The major use of union in memory space utilization. Union would hold a value for one data type of the larger storage of their members.

          Ex-

                    #include<stdio.h>

                    #include<conio.h>

                    void main()

                    {

                          struct date

                            {

                                int day;

                                 int month;

                                int year;

                            };

                          union value

                          {

                                   int i;

                                  float f;

                                   struct date bdate;

                           };

                        union value x;

                           x.i=10;

                            x.f=-1456.45;

                            x.bdate.day=25;

                           x.bdate.month=7;

                           x.bdate.year=1972;

                   printf(“frist member%d\n”,x.i);

                   printf(“second member%f\n”,x.f);

                   printf(“structure:\n”);

                   printf(“%d%d%d\n”,x.bdate.day,x.bdate.month,x.bdate.year);

           }

Structure, Declaration, Declaring Structure Variable

Structure:-

          A variable declared in ‘C’ holds data of one type at one time. Arrays hold a number of data items of the same type. But if we want to process many data items of different types together as a unit, them array is not useful. In order to solve this problem, C provides a data type, called structure which enables us to store and process different data types at the same time.

          Def- A structure is a collection of one or more variables grouped as a unit under a single name for easy processing.

          The construct structure is mainly used to store a “record” that contains different data types.

Declaration:-

          Syntax:-

                             struct name

{

data_type mem1;

data_type mem2;

-----------------

-----------------

data_type mem-n;

};

          In this declaration, struct is a keyword, ‘name’ is the name that identifies structure of this type and mem1, mem2, mem-n, are individual member declarations.

Ex:-

#include<stdio.h>

void main()

{

struct simple

{

int num;

char ch;

};

struct simple ez1;

ez1.num=2;

ez1.ch=’z’;

printf(“\n ez %num= %d,ez1.ch=%c\n”,ez1.num,ez1.ch);

}

Declaring Structure Variable:-

          After the declaration of structure data type, we may declare one or more variables to be of that type. As in above example ez1 is the variable of type simple.

Arguments passing by Reference, Arrays of Pointers

Arguments passing by Reference:-

          In passing by reference method, the addresses of actual arguments in the calling function are copied into formal arguments in the called function. Passing an argument by reference instead of by value offer an advantage as well as a disadvantage. These are:-

The advantage is that the function can be used to modify the value of the argument variable.

The disadvantage is that the function can modify the value of the argument variable, which may not be desired in some cases.

          When we pass arguments by reference, we must ensure that the function definition and proto type reflect the fact that the argument passed to the function is a pointer. Within the body of the function, we must use the indirection operator to access the value of the variable passed by reference.

Example:-

#include<stdio.h>

#include<conio.h>

void main()

{

int a,b;

a=2;

b=3;

inter (&a,&b);

{

printf(“\n a=%d”,a);

printf(“\n b=%d”,b);

}       

inter( int *x, int *y);

{
int  temp;

temp=*x;

*x=*y;

*y=temp;

printf(“\n x=%d”,*x);

printf(“\n y=%d”,*y);

}

Arrays of Pointers:-

          As these are arrays of ints, or of float, similarly also. As a pointer variable always of pointers is collection of address. The most common use of an array of pointers in with strings.

          Syntax of declaration:-

                                      datatype  *pointer_var[index];

          Ex:-           char  *ar_p[5];

Program to demonstrate pointer to a pointer

/*   Program to demonstrate pointer to a pointer  */

#include(stdio.h)

main()

{

int x=2;

int  *y;

int  **z;

y=&x;

z=&y;

printf(“\n  Address of x=%u”,&x);

printf(“\n  Address of x=%u”,y);

printf(“\n  Address of x=%u”,*z);

printf(“\n  Address of y=%u”,&y);

printf(“\n  Address of y=%u”,z);

printf(“\n  value of y=%u”,y);

printf(“\n  value of z=%u”,z);

printf(“\n  value of x=%d”,x);

printf(“\n  value of x=%d”,*(&x));

printf(“\n  value of x=%d”,*y);

printf(“\n  value of x=%d”,**z);

                  }

Pointer type variable declaration, Pointer to a Pointer

Pointer type variable declaration:-

          Pointer is defined as a variable used to store memory address. It is similar to any other variable and must be declared before it can be used. Just like an integer variable can hold any integers each pointer to a specific data type, such as int, char, float, double, etc.

Syntax:-

                   datatype  *prtname;

Ex:-            int   *a;

Note:-  Asterisk is a unary operator i.e it operator on one variable. Thus compiler can not confuse it with the same symbol used for multiplication.

Ex:-            int   a=20;

                   int  b,x,y;

                   int *pa,*pb,*px;

                   pa=&a;

                   x=*pa;

                   b=x+a;

                   pb=&b;

                   px=&x;

                   y=*pa+*pb;

Result:-

                   pa will be 100

                   x will be 20

                   pb will be 40.

                   *pb will be 102.

                   *px+pb will have a value 60.

Pointer to a Pointer:-

          a pointer to a pointer is a construct used frequently in more complex programs. To declare a pointer to a pointer, place the variable name after two successive asterisks(*).

Ex:-            int   ***z;

                   int   r=5;

                   int  *pr=&r;

                   int   **p=&q;

Pointers, Benefits of Pointers, The &(Address of) and *(dereferencing) operator

Pointers:-

          A Pointer is a variable that holds the memory address of another variable. The storage and retrieval of data using the memory address of a variable (i.e. a pointer) is faster than that of using variable. To declare and refer to a pointer type variable, C provided two special unary operator namely * and &.

Benefits of Pointers:-

Passing arguments to functions by address when modifications of formal arguments are to be reflected on actual arguments.

Passing arrays and strings more conveniently form one function to another.

Manipulating arrays more easily by moving pointers to them instead of moving the arrays themselves.

Creating complex data structure, such as linked lists are binary tree, where one data structure must contain references to other data structures.

The &(Address of) and *(dereferencing) operator:-

          All the variables defined in a program reside at specific addresses in the memory of computer. it is possible to obtain the address of a variable by using the &(ampersand) operator.

          The other pointer operator available in C is the character ‘*’ and this is called value at address operator. It returns the value stored at a particular address. (indirection operator)

Ex:-

                             main()

                             {

                               int a=2;

                              printf(“\n Address of a=%d”,&a);

                             printf(“\n value at address a=%d”,a);

                             printf(“\n value of a=%d”,*(&a));

                             }

Type of User defined functions, No argument no return, With argument no return, With argument with return, Prototype of a function, Function Definition, Accessing a function, Parameter Passing, Call by value, Call by reference, Recursion

Type of User defined functions:-

          The user defined functions may be classified in the following three types. Each type is based on the formal arguments or parameters passed to the functions and the usage of return statement.

No argument no return:-

          A function is called without passing any argument from the calling portion of a program and also the function does not return any value to the calling function.

With argument no return:-

          A function is called and formal arguments are passed from the calling program but function does not return any value to the calling program.

With argument with return:-

          A function is invoked with formal arguments form the calling portion of a program and the function return value to the calling program.

Prototype of a function:-

          The prototype tells ‘C’ compiler in advance about some characteristics of a function used in a program.

          Syntax:-

                             type   function_name(type_argument1,type_argument2,……..);

          The function “type” is the type of the returned value. If the function does not return a value, the function name is any legal identifier followed by the parenthesis.

          The arguments or parameters are given inside the parenthesis, preceded by their type and separated by commas.

Function Definition:-

          A function definition contains the code that will be executed when a function is called upon.

          Syntax:-

                         return_type   function_name(type_argument1,type_argument2,….);

                         {

                                      statement;

                                      statement;

                          }

Accessing a function:-

          A user defined function is called from the main program simply by using the name of the function, including the parenthesis followed by a semicolon.

Parameter Passing:-

          Parameter passing is a method for communication of data between the calling function and called function. This can be done by following two type-

• Call by value
• Call by reference

Call by value:-

          In C, arguments are passed by the value, which means that a copy of the argument is passed to function. The function can change the value of this copy but cannot change the value of the argument is calling function.

          Note:-

                   The argument that is passed is often called an actual argument and while the received copy is called a formal argument or formal parameter.

Call by reference:-

          Call by reference technique passes the addresses or references of the actual parameter to the called function. Thus the actual and formal parameters share the some memory locations. This is achieved by applying an address operator, that is the ‘&’ to the formal parameters in the function definition.

Recursion:-

          A Recursion function is a function that calls itself to perform a specific operation. The process of a function calling itself is known as recursion.