INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS – 201 SECTION 55 & 56  (992 Semester)

INTRODUCTION TO COMPUTER SCIENCE

LAB  #08 TOPIC: ADT Stack

Instructor: Bashir M. Ghandi

 

Objective:       Learn how to implement ADTs following the principle of information hiding

 


Implementation of ADTs

·        An ADT is a type defined in terms of its behavior rather than its representation.

·        It usually consists of a data structure and a set of operations that are allowed on the structure

·        ADTs are usually implemented following the principle of information hiding.

·        This involves breaking the implementation into two – user interface and implementation details.

·        The user interface defines the structure and a set of function prototypes that implement the allowed operations.  These are made available to the user so that he can see how the ADT works.

·        The implementation details implements the operations of the ADT and is hidden from the user .  This has the advantage that:

·        In C, Information hiding is achieved using Header and Library files – The user interface is stored in a header file and the implementation detail is stored as a library.

 

What is Stack?

·        Stack is a linear structure that holds homogeneous data and has the property that data is entered (pushed) and removed (popped) at only one end called top.

·        Stack has many applications especially in system software and operating system.

·        The common operations that are defined on stack are: CreateStack, DestroyStack, EmptyStack, FullStack, Push, and Pop

 

Implementation of Stack using Array

·        One way of implementing a stack is to use a structure consisting of an array variable stack, (to hold the items of the stack) and an int variable top (to hold the positions of the top element). 

 

The user_inteface:

·        This consists of the definition of constants and types for the structure as well as function prototypes for the operations that are allowed. 

·        This should normally be stored in a header file (.h file) and should be made available to the user so that he can see how the ADT works and also be able to modify some of the constant and type definitions to suit his application.. 

·        A sample header file for the Stack ADT can be obtained from my home page on this link. stack.h

 

Implementation details

·        This should be stored in a separate file, (stack.c).  This can be completely hidden from the user by compiling it and providing only the compiled version (.obj file)

·        A sample implementation file can be obtained from my home page on this link. stack.c

·        Notice that you must include stack.h in the file stack.c and in any application file that uses the stack ADT.

 

Compiling an Application that uses user-defined ADT using the Project tool

·        When we use a system defined ADT, example the string ADT, we only need to include the header file string.h in our application and then compile and link the application to produce an executable file.

·        Similarly, when we write an application that uses our own ADT, we only need to include the header file, (example stack.h) and not the implementation (.c) file.

·        However, since our implementation file is not known by the system, our application my compile but it will not link.

·        To solve this problem, we use the Project utility which can be seen on the Project menu.  The following are the steps to follow:

  1. Choose Open project from the Project menu – this should display the Open project file window
  2. Change to the drive/folder containing your application and the ADT
  3. Since you are creating a new project, type a name for the project and click OK – you could give it same name as your application but do not give any file extension.  The system will automatically add .prj . This would create an empty project and opens a window that allows you to add files to your project.
  4. Locate your application file and click the add file button to add it to your project.  Do the same to your ADT implementation file (Note: DO NOT add the header file to the project) and click the Done button.
  5. Finally, open the compile menu and select Build all option.  This will compile and link your project.  Run your project using the Run option as normal.

·        Note that, we can add the compiled version of our ADT (.obj) instead of the source file.  Thus, we can indeed hide it from the user if we so wish.

  

Programming Exercise:

1.  (a)   Download the files stack.h ,  stack.c , and  lab8_1.c  from my home page.  Open each of them and study them to understand how they work.  You will notice that lab8_1.c is an application that uses the Stack ADT to read a sequence of characters from the user, push them onto the stack, pop them out and print them – they will be in reverse order.

(b)  Following the description above, open a project lab8_1.prj, add the files lab8_1.c and stack.c, build the project and test-run it.

(c)  Replace stack.c file from the project with stack.obj  then build and run the project.

 

2.         Modify the header file (stack.h) by changing the ITEM_TYPE from char to int.  Now modify lab8_1.c program to read 10 integer values onto the stack, pop them off and print them.  –They should now appear in reverse order.

Hint:    You need to change input_stack and output_stack to handle integers.

 

3. (a)    Introduce the following data types into the stack.h file (they should appear before the declaration of ITEM_TYPE).

typedef char STRING[81];

typedef struct {   long int id_no;

                    STRING name;

                    int exam1;

                    int exam2;

                    int exam3;

                    float average;

} STUDENT_REC;

Now change the ITEM_TYPE from int to STUDENT_REC.

    b.     Modify the program in (2) to read each of the student records in the file exams2.dat, computes the average and push the records onto the stack. Now pop off the records and print them out.

Hint:  You can use the functions get_record, get_average & print_record from the previous lab.

 

Home Work:

Write a program that uses a stack to check whether the bracketing operators, (), [], and {} in a given character string are balanced.  Example of a balances string is:  { s= 2* (a[2] + 3);  x=(1 + (2)); }

Examples of  unbalanced strings are: (([]) ,  a) (c, and  {(}).