Description: Please complete the missing code of the stack ADT with a linked list, such that the program could output a correct answer.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include  #include  #include  typedef enum {PUSH = 1, POP, END, ERROR_OP} OP; /* the minimum value of interger type. 0x80000000 = -2147483648 * the maximum value of integer type. 0x7fffffff = 2147483647 * They are used to represent the error of stack underflow and stack overflow, respectively */ #define ERROR_UNDERFLOW 0x80000000 #define ERROR_OVERFLOW 0x7fffffff typedef struct node Node; struct node { int v; Node *next; Node *prev; }; typedef struct linked_list List; struct linked_list { Node *head; Node *tail; }; // insert an element 'x' at the back of the LinkedList void insert(List *L, int x) { Node *node = (Node *)malloc(sizeof(struct node)); node->v = x; node->prev = L->tail->prev; node->prev->next = node; node->next = L->tail; L->tail->prev = node; } // delete the node p void delete(List *L, Node *p) { Node *pred = p->prev; Node *succ = p->next; pred->next = succ; succ->prev = pred; free(p); } // create a empty stack List *create_stack() { List *L; L = (List *)malloc(sizeof(struct linked_list)); L->head = (Node *)malloc(sizeof(struct node)); L->head->prev = NULL; L->tail = (Node *)malloc(sizeof(struct node)); L->head->next = L->tail; L->tail->prev = L->head; L->tail->next = NULL; return L; } // destroy a stack and release its nodes void destroy_stack(List *L) { Node *curr = L->head->next; while (curr != L->tail) { Node *next = curr->next; free(curr); curr = next; } free(L->head); free(L->tail); free(L); return ; } int is_full(List *L) { //In C, zero is used to represent False return 0; } int is_empty(List *L) { // write down your code here } int push(List *L, int x) { if (is_full(L)) { return ERROR_OVERFLOW; } // write down your code here } int pop(List *L) { if (is_empty(L)) { return ERROR_UNDERFLOW; } // write down your code here } // decode the input operations OP get_op() { char str[20]; scanf("%s", str); if (strcmp(str, "push") == 0) { return PUSH; } else if (strcmp(str, "pop") == 0) { return POP; } else if (strcmp(str, "end") == 0) { return END; } else { return ERROR_OP; } } // display the elements in the stack from top to bottom void print_stack(List *L) { Node *ptr = L->tail->prev; if (ptr == L->head) { printf("empty "); return ; } while(ptr != L->head) { printf("%d ", ptr->v); ptr = ptr->prev; } printf(" "); return ; } int main(void) { int x; List *L = NULL; int flag = 0; L = create_stack(); int ret = 0; while (!flag) { switch(get_op()) { case PUSH: scanf("%d", &x); ret = push(L, x); if (ret == ERROR_OVERFLOW) { printf("stack overflow "); } break; case POP: ret = pop(L); if (ret == ERROR_UNDERFLOW) { printf("stack underflow "); } else { printf("%d ", ret); } break; case END: print_stack(L); flag = 1; break; default: printf("error input "); } } destroy_stack(L); return 0; }

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Input: M lines of stack operations, each chosen from one of the followings: push x, pop. The last line is an ending indicator, end. Output: The top element for per pop operation. If there exists underflow or overflow, please output "stack underflow" or "stack overflow", respectively. The remaining elements in the stack from top to bottom, separated by a space. If the stack is empty, please output empty. Sample Input 1: pop push 1 push 2 end Sample Output 1: stack underflow 2 1 Sample Input 2: push 1 pop end Sample Output 2: 1 empty