Palindrome check program using C language. Text can only contain uppercase letters and blanks, and it should end with a final dot. We can only use stacks and/or queues for this code.

Sample run:

Enter a text ending with '.' : RACE CAR. A palindrome! Enter a text ending with '.' : CAR CAR. Not a palindrome! Enter a text ending with '.' : NO LEMON NO MELON. A palindrome!

Further notes:

We are advised to include a header file named "Stack_Queue_wList.h" in order to reduce the length of the program

which contains the following code:

#include

// This version of Linked List keeps also a tail pointer to the last Node. // Hence, it becomes O(1) to access the last one or to insert to the end.

struct Node { int val; struct Node *next; };

struct List { struct Node *head, *tail; int size; };

// LIST is new name for "struct List" typedef struct List LIST;

void LInit(LIST *l){ // initialize list to empty l->head = l->tail = NULL; // pointers to first and last node l->size = 0; // number of nodes }

int LGetPos(LIST *l, int x) { struct Node *p; int i=0; // go through all nodes for (p=l->head; p!=NULL; p=p->next) if (p->val == x) return i; // found, so return i++; // not yet, go to next return -1; // not found in the list }

int LGetAt(LIST *l, int pos) { struct Node *p=l->head; int i; if(pos >= l->size) { // we have less items printf("LGetAt: Position not exist "); return -99; } // last one, so directly return if(pos==l->size-1) return l->tail->val; // go to position for(i=1; i<=pos; i++) p = p->next; // go to pos return p->val; // return item at pos }

void LInsert(LIST *l, int x, int pos) { struct Node *new, *p; // p: previous node int i; if(pos > l->size) { // we have less items printf("LInsert: Position not possible "); return; } // create a new node new = (struct Node *) malloc(sizeof(struct Node)); new->val = x; if(pos==0) { // insert to start new->next = l->head; l->head = new; // only one, so it also tail if(l->size==0) l->tail=new; } else if(pos==l->size) { // insert to end l->tail->next = new; l->tail = new; new->next = NULL; } else { // insert after p p = l->head; for(i=1; inext; // go to pos-1 new->next = p->next; p->next = new; } l->size++; }

void LDelete(LIST *l, int pos) { struct Node *p, *d; // p: previous int i; if(pos >= l->size) { // we have less items printf("LDelete: Position not exist "); return; } if(pos==0) { // delete first node d = l->head; l->head = d->next; } else { // delete after p p = l->head; for(i=1; inext; // go to pos-1 d = p->next; p->next = p->next->next; // last node deleted, so update tail if(pos==l->size-1) l->tail = p; } l->size--; free(d); }

int LIsEmpty(LIST * l){ return (l->size == 0); }

int LSize(LIST * l){ return (l->size); }

void LDisplay(LIST *l) { struct Node *p; printf("List: "); for(p=l->head; p!=NULL; p=p->next) printf("--> %d ", p->val); printf(" "); }

int LHeadOf(LIST *l) { if (!LIsEmpty(l)) return l->head->val; else { printf("LHeadOf: Linked list empty "); return -99; } }

int LTailOf(LIST *l) { if (!LIsEmpty(l)) return l->tail->val; else { printf("LHeadOf: Linked list empty "); return -99; } }

// STACK is new name for "struct List" typedef struct List STACK;

void SInit(STACK *s) { LInit(s); // call Init of Link List }

void SPush(STACK *s, int item) { // call Insert of Link List to insert item at position 0 LInsert(s, item, 0); }

int SIsEmpty(STACK *s) { // call IsEmpty of Link List return LIsEmpty(s); }

int SPop(STACK *s) { if(LIsEmpty(s)) { printf("SPop: Stack empty "); return -99; } else { int t=LGetAt(s, 0); // get top element into t LDelete(s, 0); // delete it from stack return t; // return t (ex-top element) } }

// QUEUE is new name for "struct List" typedef struct List QUEUE;

void QInit(QUEUE *q) { LInit(q); // call Init of Link List }

void QInsert(QUEUE *q, int item) { // call Insert of Link List to insert item to the end (pos size) LInsert(q, item, LSize(q)); }

int QIsEmpty(QUEUE *q) { // call IsEmpty of Link List return LIsEmpty(q); }

int QRemove(QUEUE *q) { if(LIsEmpty(q)) { printf("QRemove: Queue empty "); return -99; } else { int t=LGetAt(q, 0); // get first element into t LDelete(q, 0); // delete it from list return t; // return t (ex-first element) } }