C -Programming

Additional Notes for Stack Program Development These should serve as a guide to help you in developing the stack program. These are intended as a guide only but should address most of the common questions. 1. Files Needed and their expected content: 1. boolean.h This file should contain the typedef for the boolean type as well as the definitions for TRUE and FALSE. This file will be reusable for many different programs in the future. 2 stack.h This file should contain the typedef for the stack type that is capable of handling a stack of integers as well as the prototypes for all of the subprograms that allow us to access that data on a LIFO basis: init_stack, is_empty, is_full, push, pop, and print_stack 3. stack.c This file should contain the definitions for all of the subprograms that allow us to access the stack of data on a LIFO basis 4. main.c This is the menu driven main program that you should write based off the example program from CPI that will allow the user to have 4 menu options: Push, Pop, Print, and Quit. . . 2. Pseudocode for menu driven main program: 1. Initialize the stack 2. Display menu and get user's selection 3. While selection is not 4 (quit) a. If selection is 1 (Push) i. If stack is not full Ask for number Read input for number Push number on top of stack ii. Otherwise Display error message indicating stack is full b.If election is 2 (Pop) i. If stack is not empty Pop number from top of stack Print number returned ii. Otherwise Display error message indicating stack is empty c. If selection is 3 (Print) i. If stack is not empty Print the stack contents Otherwise Display message indicating stack is empty d. If selection is not valid i. Display error message indicating not a valid menu selection e. Display menu and get user's selection 4. (Optional) Display a farewell message since user selected to quit the program Stack A collection of data long with operations that access that data on a LIFO (last-in, first-out) basis. Defining types: a single item in the stack consists of the data item and a pointer to the next stacknode structure typedef struct stacknode { int data; struct stacknode *next; } *stack; a boolean type is either true (1) or false (0) typedef int boolean; #define TRUE 1 #define FALSE O Subroutines are required for the following: Note: I'm assuming you have declared a variable in the main program using stack top; where top is a pointer to the top of the stack. 1. Initializing the stack Uses pass by reference to set the pointer to the top of the stack to NULL. Prototype: void init_stack(stack *); Call it using: init_stack(&top); void init_stack(stack *s) { (*s) = NULL; } 2. Checking to see if stack is full Checks to see if enough memory is available for another stacknode structure. We try to allocate memory the size of a stacknode structure. If successful, temp will be pointing to that memory which now needs to be freed. If not, temp will be equal to NULL. Returns TRUE or FALSE Prototype: boolean is full(void); Call it using: if (is fullO) OR if (!is fullo) boolean is_full(void) { stack temp; temp = (stack) malloc (sizeof(struct stacknode)); if (temp == NULL) return TRUE; else { free (temp); return FALSE; } 3. Checking to see if stack is empty Receives stack via pass by value and determines whether or not pointer to the top of the stack is pointing to NULL. Returns TRUE or FALSE Prototype: boolean is empty(stack); Call it using: if (isempty(top)) OR if (!is_empty(top)) boolean is empty(stack s) { if (s == NULL) return TRUE; else return FALSE; } 4. Pushing new items on the stack You must make sure stack is not full before calling this subroutine. Receives stack via pass by reference and data to be added via pass by value Allocates memory for new stacknode structure and assigns it to temp sets the data portion equal to the item to be pushed sets the next pointer to point to the top of the stack (ie top stacknode structure) moves the top pointer to this new stacknode structure Prototype: void push(stack, int); Call it using: push (&top, data_item); void push(stack *s, int x) { stack temp; temp = (stack) malloc(sizeof(struct stacknode)); temp -> data = x; temp->next = (*s); (*s) - temp; } 5. Popping items off the stack You must make sure the stack is not empty before calling this subroutine. Receives stack via pass by reference Uses a temporary stack called temp. set temporary stack pointer to the top of the stack set data to be popped equal to temp's data move top of stack to stacknode structure pointed to by temp's next pointer free temp (ie free memory used for stacknode structure temp is pointing to) Prototype: int pop(stack *); Call it using: something = pop(&top); int pop(stack *s) { stack temp; int data popped; temp = *s; data popped = temp->data; *s = temp->next; free (temp); return data popped; } 6. Listing contents of the stack (without dumping them) You must make sure stack is not empty prior to calling this subroutine. This subroutine will receive the stack via pass by value and list the contents without altering them. NOTE: This subroutine using recursion (calls upon itself) to print the contents of all stacknodes. Call it using: print_stack(top); void print stack(stack s) { if (!is empty(s)) { printf("%d ", s->data); print_stack(s->next); } } Here is the testcase for the stack program. Run the program Quit Run the program Pop - you should see an "empty" message List - you should see an "empty" message Push a 1 Push a 2 Push a 3 Push a 4 Push a 5 List - you should see the numbers 5, 4, 3, 2, 1 in that order Pop - message indicating "5 was removed" List - you should see the number 4, 3, 2, 1 in that order Push a 6 List - 6, 4, 3. 2. 1 in that order Pop - "6 was removed" Continue popping until you have removed 4, 3, 2, and 1 Enter an invalid menu option to get the error message - "empty" message should appear List - "empty" message should appear push a 10 pop - 10 is removed quit