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(“%d\n”, 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 Pop - “empty” message should appear List - “empty” message should appear push a 10 pop – 10 is removed quit