Implementations and Program Design for Stack ADT and Modularity

Stack ADT & Modularity 2 implementations of the Stack abstract data type: Array Linked List Program design: modularity, abstraction and information hiding

What is a Stack? stack: abstract data type that represents a collection of elements access only allowed at one point of the structure, typically called the top of the stack access to the most recently added item only like a stack of plates in a cafeteria last in, first out (LIFO) new elements/plates placed on top the top plate/element is always the first to be removed Fundamental operations push: add item to stack pop: remove top item from stack top: get top item without removing it isEmpty https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Abstract Data Type (ADT) Type with public interface & hidden implementation User only knows the available operations In C: public interface contains function prototypes in a header file Implementation in separate .c file: function definitions Client code can use type to declare variables & use provided operations Implementation of ADT can change with no impact on client or change in interface

Stack ADT Stack.h: #include<stdbool.h> typedef struct stackType *Stack; Stack create(); void destroy(Stack s); bool isEmpty(Stack s); // return true if stack is empty, false otherwise bool isFull(Stack s); // return true if stack is full, false otherwise void push(Stack s, int n); // add n to top of stack int pop(Stack s); // remove and return top stack element // create new empty stack // remove stack and all its elements

Stack ADT Client code, stackEx.c: #include<stdio.h> #include "Stack.h" int main() { Stack s1, s2; int n; s1 = create(); s2 = create(); push(s1, 1); push(s1, 2); push(s1, 3); while(!isEmpty(s1)) { n = pop(s1); push(s2, n); } destroy(s1); while(!isEmpty(s2)) { printf("Popped from s2: %i\n", pop(s2)); } If stack implemented correctly, output is: Popped from s2: 1 Popped from s2: 2 Popped from s2: 3 destroy(s2); }

Stack ADT: Array Implementation Stack.c: #include<stdio.h> #include<stdlib.h> #include "Stack.h" void destroy(Stack s) { free(s); } bool isEmpty(Stack s) { return s top == 0; } #define STACK_SIZE 100 typedef struct stackType { int contents[STACK_SIZE]; int top; } stackType; bool isFull(Stack s) { return s top == STACK_SIZE; } Stack create() { Stack s = malloc(sizeof(stackType)); if(s == NULL) exit(EXIT_FAILURE); s top = 0; return s; } void push(Stack s, int n) { if(isFull(s)) exit(EXIT_FAILURE); s contents[s top] = n; s top++; }

Stack ADT: Linked List Implementation void destroy(Stack s) { while(!isEmpty(s)) pop(s); free(s); } Stack.c, version 2: #include<stdio.h> #include<stlib.h> #include "Stack.h" struct node { int data; struct node *next; }; struct stackType { struct node *top; }; Stack create() { Stack s = malloc(sizeof(struct stackType)); if(s == NULL) exit(EXIT_FAILURE); s top = NULL; return s; } bool isEmpty(Stack s) { return s top == NULL; } bool isFull(Stack s) { return false; }

Stack ADT: Linked List Implementation void push(Stack s, int n) { struct node *newNode = malloc(sizeof(struct node)); if(newNode == NULL) exit(EXIT_FAILURE); newNode data = n; newNode next = s top; s top = newNode; } int pop(Stack s) { struct node *oldTop; if(isEmpty(s)) exit(EXIT_FAILURE); oldTop = s top; int n = oldTop data; s top = oldTop next; free(oldTop); return n; }

Program Design

Introduction Most full-featured programs are at least 100,000 lines long. Although C wasn t designed for writing large programs, many large programs have been written in C. Writing large programs is quite different from writing small ones. Issues that are important when writing large programs: Style Documentation Maintenance Design Your program design should make programs readable and maintainable.

Modules Can view a program as a number of independent modules Module: collection of services (functions) some are made available to other parts of the program Each module has: interface: describes available services header file containing prototypes, made available to clients implementation: source code file contains implementation of module's functions

Modules in C The C library is a collection of modules Each header in the library serves as interface to a module: <stdio.h>: interface to module containing I/O functions <string.h>: interface to module containing string-handling functions Advantages of dividing program into modules: abstraction a distancing between ideas and details. We can use modules without knowing how they work. reusability a module can be reused in other programs. maintainability a bug is contained to a single module, making it easier to find and fix.

Modular Design Decisions to consider during modular design: What should the program's modules be? Which services should each module provide? How should the modules be interrelated? Want modules to have two properties: high cohesion: a module has a well-defined purpose. All elements of module are closely related to each other. low coupling: modules should be as independent of each other as possible. loosely coupled modules make it easier to modify the program Types of Modules: libraries: collection of related functions. E.g., <string.h> abstract data types: a type whose representation is hidden data pool: a collection of related variables and constants Often just a header file in C. E.g., <float.h>, <limits.h>

Information Hiding A well-designed module often keeps some information secret from clients Clients of our Stack module don't need to know how the Stack is implemented (array, linked list, etc.) Information hiding: concealing information from clients of a module Advantages: Security: Clients don't know how a module's data is stored so they can't corrupt it. We control the client's access to data through the operations we provide. Flexibility: Changing the implementation is easy because the client isn't dependent on a particular implementation.