Write a menu driven program to allow the user to 1) Push, 2) Pop, 3) Print, and 4) Quit. You must use separate compilation with files main.c, boolean.h, stack, h, and stack.cst

Here is the tes tca s e for the stack progr a m.

Run the progr a m Quit

Run the progr a m Pop – you sho ul d see an “emp ty” mes s age List – you sho ul d see an “empty” mes s a ge Push a 1 Push a 2 Push a 3 Push a 4 Push a 5 List – you sho ul d see the nu m b e r s 5, 4, 3, 2, 1 in that order Pop – mes s age indicating “5 was rem ove d” List – you sho ul d see the nu m b e r 4, 3, 2, 1 in that order Push a 6 List – 6, 4, 3, 2, 1 in tha t order Pop – “6 was remove d” Contin ue pop pi ng until you have remove d 4, 3, 2, and 1 Enter an invalid men u option to get the error mes s age Pop – “empty” mes s a ge shoul d appea r List – “empty” mes s a ge shoul d appea r pus h a 10 pop – 10 is remove d quit

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 0

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_full()) OR if (!is_full())

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 (is_empty(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(“%dn”, s->data); print_stack(s->next); } }