Stack Data Structure

STACK DATA STRUCTURE

A stack is an ordered collection of items in which operations take place on the principle LIFO (Last In First Out).  Items are deleted and inserted into the stack at only one end, called the top of the stack.  The item, which is inserted last will be retrieved first from the stack.

Unlike an array, a stack is a dynamic, constantly changing object.  The single end of the stack is designated as the stack Top.  New items may be put on top of the stack or items that are at the top of the stack may be removed from the stack.  Following is a representation of a stack containing items in it:

Fig.: A stack containing six items in it

In this figure, the vertical lines that extend past the items of the stack indicate the top of the stack.  If any new items are added to the stack, they are placed on top of E, and if any items are deleted, E is the first item to be deleted.

Primitive Operations:

The two primary operations performed often on stack are:  Insertion and Deletion of items from the stack.  These two operations are termed as Push and Pop respectively.  When an item is added to a stack, it is known as ‘pushing’ into the stack, and when an item is removed, it is called as ‘popping’ from the stack.

Given a stack S, and an item i, performing the operation push(s, i) adds the item i to the top of the stack.  Similarly, the operation pop(s) removes the top element and returns it as a function value.  Thus the assignment operation

i = pop(S);

            removes the element at the top of S and assigns its value to i.  Because of the push operation, which adds element to a stack, a stack is sometimes called a pushdown list.

There is no upper limit on the number of items that may be kept in a stack.  Pushing another item on to a stack makes the stack to grow and popping an item from the stack shrinks the stack downwards.  When there is no item in the stack, it is called as empty stack.  An empty stack can’t popup any value.

Another operation that can be performed on stack is to determine what the top item on a stack is without removing it.  This operation is written as

     stacktop(S);

It returns the top element of stack S, when it is not empty.  This operation can be implemented using the primitive operations pop followed by push.  Therefore,

     i = stacktop(S);

            is equivalent to

i = pop(S);

push(s, i);

The result of an illegal attempt to pop or access an item from an empty stack is called stackunderflow, which can be avoided by checking the emptiness of the stack.

Representing Stacks in C:

A stack in C may be implemented using a structure containing two objects: an array to hold the elements of the stack, and an integer to indicate the position of the current stack top within the array.  This may be done for a stack of integers by the declaration:

# define STACKSIZE 100

struct stack

{
    int top;

    int items[STACKSIZE];

} s;

Implementing the Pop operation:

To pop an element from the stack, first check whether the stack is empty.  If the stack is empty, print a warning message and halt execution or else remove the top element from the stack.  This operation is coded in C as follows:

     pop(ps)

     struct stack *ps;

{          

if(empty(ps)) {

     printf(“%s”, “Stack Underflow”);

               exit(1);

          }

          return(ps-->item[ps-->top--]); 

}

Implementing the Push operation:

Before pushing any element into the stack, check whether the stack is full.  If there any empty space in the stack, then increment the pointer top to point the next empty element in which the new item can be stored.  This operation is implemented using the following code in C:

push(ps, x)

     struct stack *ps;

     int x;

{          

if(ps-->top == STACKSIZE-1) {

            printf(“%s”, “Stack Overflow”);

                                    exit(1);

          }

          else

ps-->item[++(ps-->top)] = x;

          return;

}

Continue reading →

Arrays and Structures in C!

USING ARRAYS AND STRUCTURES!

An array is defined abstractly as a finite ordered set of homogeneous elements.  It is a data type, which is derived from primitive data types in C.  The simplest form of an array is one-dimensional array.  An example for one-dimensional array is a String of characters of size n, where n is the number of characters in the string.

The word ‘finite’ in the above definition indicates that there is a specific number of elements in the array.  The word ‘ordered’ means the elements of the array are arranged so that there is a zeroth, first, second, third and so forth.  By ‘homogeneous’ we mean that all the elements in the array must be of the same type.

Declaring an Array:

Array must be declared first, before we use it in a program.  Declaring an array involves the following details:

1.      Data type of the array

2.      Name of the array and

3.      Size of the array

Consider the following C statement for declaring an array of 100 integers:

int a[100];

There are two basic operations that can be done on an array:  Storage and Retrieval (extraction) of data.  The storage operation is a function which accepts an array a, an index i, and an element x to store the value of x in a[i].  The storage operation is expressed as a[i] = x;  where as the extraction operation accepts an array a, and an index i, and returns an element of the array.  It is expressed in C as a[i].

Every array has a limitation in storing its elements - it can hold only a fixed number of elements in it.  It’s size or range is set by two limits called Upper Bound (UB) and Lower Bound (LB).  The smallest element of an array’s index is called its Lower Bound and in C is always 0, and the highest element is called its Upper Bound.

If L is the lower bound of an array and U is the upper bound, the number of elements in the array, called its range is given by (U-L+1).  For instance, if L is 0, and the U is 99, then the range is 99-0+1 = 100.  An important feature of a C array is that neither the upper bound nor the lower bound may be changed during the time of program execution.

Setting the Upper Bound for an Array:

An array can be declared using the data type of its elements and the Upper Bound.  The lower bound is always fixed at 0, and the upper bound is fixed at the time the program is written.  One useful technique is to declare a bound as a constant identifier, so that the work required to modify the size of an array is minimized.  Consider the following example:

#define NUMELTS 100

int a[NUMELTS];

for(i=0; i<NUMELTS; a[i++]=0);

In this example, the first line defines a constant NUMELTS with value 100.  Then in the second line, the array a is declared using the data type int and the constant NUMELTS.  Then in the third line, a ‘for’ loop statement is used to initialize the elements of the array with 0.  Now, only a single change in the constant definition is required to change the Upper Bound of the array as well as its initialization.

Structure in C:

A structure is a group of items in which each item is identified by its own identifier called member of the structure.  Each item in the structure may be of different types.  Using a structure, we can store a list of data items of a particular thing or person.  Hence, in some programming languages, a structure is called as ‘Record’, and its members as ‘Fields’.

Defining a Structure:

A Structure must be defined as a user-defined data type that contains variables of different types in it.  A group of variables are declared under the keyword struct and are called members of the structure.  Each and every member is defined using a data type and a name.  Following is the syntax for defining a structure:

struct Struc_tag

{

     datatype var-1;

     datatype var-2;

     ...

     ...

     ...

     datatype var-n;

}

where,
struct         -     is a keyword to indicate that the following is a structure definition.
Struc_tag   -     is the name given to the new data type defined by the user.
Body         -     Body of the structure contains a block of declarative statements for  defining a group of variables, which are enclosed within curly braces.

An example for a structure data type is as follows:

            struct nametype

       {
            char first_name[10];

       char midinit;

            char last_name[20];

       };

In this example, the name of the structure is nametype, which contains three members: first_name, midinit and last_name.  The first_name and last_name are arrays of characters, which will store the first name and last name of a person, and the midinit is a character field for storing the initial.

Structure Variables:

Structure variables are variables of type structure.  Variables must be declared using structure data type in order to make use of a structure, i.e.,  a structure data type can’t be directly used for storing values in its members; instead a variable of type structure can be used.

By declaring a structure variable, we allocate required memory locations for storing all the members of the structure in memory.  The amount of memory required by a structure is the sum of storage specified by each of its members.

Structure variables can be declared in two different ways: Implicitly and Explicitly.  In the first method, a variable can be declared in the structure definition itself.  At the end of the structure definition, i.e., after the closing brace of structure definition, we can include the structure variables.  The example for the first method is as follows:

            struct nametype

      {
           char first_name[10];

      char midinit;

           char last_name[20];

      } name;

In the second method, we declare the structure variables in a separate line apart from the structure definition.  Here, we define the structure first, and then using that newly defined structure data type, we declare structure variables (one or more).  Example for this method of defining structure variable is as follows:

            struct nametype

      {
           char first_name[10];

      char midinit;

           char last_name[20];

      };

      struct nametype e_name, s_name;

In the above example, the structure type nametype is defined separately first.  Then the structure variables e_name and s_name are declared next in a separate statement.  The same structure nametype can also be used for declaring more variables later.

Storing and Accessing data from a Structure:

Structure variables can be used for storing values (a set of values of different data types) after their declaration in a program.   Following is the notation used for accessing the members of a structure:

      
StrcutureVariable.MemberVariable;

Use the dot (.) operator for accessing the members of a structure.  The syntax includes the structure variable first, followed by a dot (.) operator and then the member variable.

Examples for using structure is given below.  They make use of the structure variables (e_name and s_name) defined above:

            e_name.first_name = “Rahul”;

      e_name.last_name = “Dravid”;

      s_name.first_name = “Sachin”;

      s_name.last_name = “Tendulkar”;

      printf(“%s %c %s”, e_name.first_name, e_name.midinit, e_name.last_name);

Here is a video presentation on Defining and Using Structures:

Continue reading →

Introduction to Data Structures

INTRODUCTION TO DATA STRUCTURES

A data structure is a scheme designed for organizing a set of data that can be manipulated using a set of operations.  It is a system which is implemented independent of the way in which the data are physically arrayed in secondary storage.  A simple example for a data structure is a Stack.

A stack is a data structure, which operates on the principle of “Last In First Out” (LIFO).  Stacks are widely and extensively used in modern computer systems, and are usually implemented through a combination of hardware and software.

                        Figure:  Simple representation of a Stack

Examples for data structures already exist in C are: array and pointer.  Simple data structures like array and pointer can be defined in a language like C using the simple data types - int, float and char.  Whereas, complex data structures can be defined using the simple data structures such as array and pointer.

It is possible to present several implementations of the same data structure, each with its own strengths and weaknesses.  But, sometimes no implementation, hardware or software, can model a mathematical concept completely.  When several implementations are possible, one implementation may be better than another for a specific application.

One important consideration in any implementation is its efficiency.  Efficiency is usually measured by two factors: time and space.  Unfortunately, there is usually a trade-off between these two measures, because an implementation that is fast uses more storage than one that is slow.  The choice of implementation in such a case involves a careful evaluation of the trade-offs among the various possibilities.

Abstract Data Type (ADT):

An Abstract Data Type is a data type which defines a data structure with a set of operations to be performed on it.  Objects such as list, set and graph, along with their operations, can be viewed as Abstract Data Type (ADT).

A data type is defined with a collection of values and a set of operations to be performed on those values.  Whereas, an Abstract Data Type (ADT) is a mathematical abstraction of a data structure; no where in an ADT's definition is there any mention of how the set of operations is implemented.

The class in C++ allows for the implementation of ADTs, with appropriate hiding of implementation details.  Thus any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate method.

Pointers in C:

Pointer is a derived data type in C, whose possible values are memory locations.  For instance, if x is declared as an integer, then &x refers to the location that has been set aside to contain x.  Therefore &x is said to be a pointer.

Examples for pointer variable declarations are:

            int *pi;

            float *pf;

            char *pc;

In these examples, pi is a pointer to an integer, pf is a pointer to a float number, and pc is a pointer to a character.  The asterisk indicates that the values of these variables being declared are pointers to values of the type specified in the declaration rather than object of that type.

Pointer values can be assigned like any other values.  For eg., the statement,

            pi = &x;

assigns the address of variable x to the pointer pi.

The notation *pi in C refers to the integer at the location referenced by the pointer pi.  Thus the statement

            x = *pi;

assigns the integer available in the memory location pointed by pi to the variable x.

Arithmetic operations on Pointers:

While declaring a pointer variable, C insists that the pointer should be specified of a particular data type.  For example,

            int *pi;

declares a pointer pi as not simply “a pointer”, but “pointer to an integer”.  This is required for doing the arithmetic operations on pointers such as incrementing or decrementing the address of the pointer to refer to the next or previous locations of the current memory location indicated by the pointer.

If we consider that pi is a pointer to an integer, then pi + 1 is the pointer to the integer immediately following the integer *pi in memory, pi - 1 is the pointer to the integer immediately proceeding *pi, pi + 2 is the pointer to the second integer following *pi, and so on.

Continue reading →