Implementing Stacks and Queues in C using Linked Lists and Header Files

1. Senem Kumova Metin Spring2009 STACKS AND QUEUES Chapter 10 in A Book on C

2. Senem Kumova Metin Spring2009 A LINKED LIST IMPLEMENTATION OF A QUEUE data next data next NULL data next cnt front rear queue node node node Queue: First-In-First-Out (FIFO) data structure

3. Senem Kumova Metin Spring2009 The header file: queue.h #define EMPTY 0 #define FULL 10000 typedef int data; typedef enum {false, true} boolean; struct node { int d; struct node *next; }; typedef struct node node; struct queue { int cnt; /* count of the elements */ node *front; /* ptr to the front element */ node *rear; /* ptr to the rear element */ }; typedef struct queue queue;

4. Senem Kumova Metin Spring2009 The header file: queue.h data front(const queue *q); boolean isempty(const queue *q); boolean isfull(const queue *q); void initialize(queue *q); void enqueue(data x, queue *q); data dequeue(queue *q);

5. Senem Kumova Metin Spring2009 Basic queue routines : ISEMPTY(),ISFULL() boolean isempty(const queue *q) /* RETURNS TRUE IF QUEUE IS EMPTY */ { return ((boolean) (q -> cnt == EMPTY)); /* if(q->cnt==EMPTY) return true; else return false */ } boolean isfull(const queue *q) /* RETURNS TRUE IF QUEUE IS FULL */ { return ((boolean) (q -> cnt == FULL)); }

6. Senem Kumova Metin Spring2009 Basic queue routines : FRONT() , INITIALIZE() data front(queue *q) // RETURNS DATA OF FRONT NODE { return (q -> front -> d); } void initialize(queue *q) // Count=0, No front and rear nodes { q -> cnt = 0; q -> front = NULL; q -> rear = NULL; }

7. Senem Kumova Metin Spring2009 Basic queue routines : ENQUEUE() /* Creating queue enqueue */ void enqueue(data x, queue *q) { node *p; p = malloc(sizeof(node)); // CREATE A NEW NODE p -> d = x; p -> next = NULL; if (!isempty(q)) /* IF QUEUE IS NOT EMPTY APPEND NEW NODE FROM REAR */ { q -> rear -> next = p; q -> rear = p; } else /* IF QUEUE IS EMPTY NEW NODE WILL BE FRONT AND REAR */ q -> front = q -> rear = p; q -> cnt++; }

8. Senem Kumova Metin Spring2009 data dequeue(queue *q) { data x; node *p; x = q -> front -> d; /* store data in x */ p = q -> front; /* store address of front node that will be deleted */ q -> front = q -> front -> next; /* determine new front node */ q -> cnt- - ; /* decrease count */ free(p); /* free node */ return x; } Basic queue routines : DEQUEUE()

9. Senem Kumova Metin Spring2009 void print(queue *q) { node * p; for(p=q->front; p!=NULL; p=p->next) printf("%d ", p->d); printf(\n); } Basic queue routines :PRINT()

10. Senem Kumova Metin Spring2009 main() { queue my_q; data x; int op; initialize(&my_q); do { printf(" PLEASE SELECT OPERATION\n"); printf(" ENQUEUE 1\n DEQUEUE 2\n FRONT 3\n IS FULL 4\n IS EMPTY 5\n PRINT 6 \n EXIT 7\n " ); scanf("%d",&op); /* SWITCH- CASE NEXT SLIDE */ } while(op!=7); }

11. Senem Kumova Metin Spring2009 switch(op) { case 1 : printf("Enter data : "); scanf("%d",&x); enqueue(x,&my_q); break; case 2: dequeue(&my_q); break; case 3: printf(" front: %d",front(&my_q)); break; case 4: if(isfull(&my_q)==true) printf("Queue is FULL"); else printf("Queue is NOT FULL"); break; case 5: /* similar to case 6 */ case 6: print(&my_q); break; case 7: exit(0); default : break; }

12. Senem Kumova Metin Spring2009 STACKS SAMPLE PSEUDO CODE: push(1) to Stack push(2) to Stack push(3) to Stack pop() from Stack push(4) to Stack

13. Senem Kumova Metin Spring2009 STACKS : Array Implementation #define STACK_SIZE 4 typedef struct { int data [STACK_SIZE]; int top; } stack;

14. Senem Kumova Metin Spring2009 STACKS(array imp. ) : Basic routines void reset(stack * stk) { stk->top=-1; } void push( int c, stack * stk) { if(stk->top!= STACK_SIZE-1) { stk->top++; stk->data[stk->top]=c; } else printf(Stack is full!!\n); } int pop (stack * stk) { if(stk->top!=-1) return (stk->data[stk->top- -]) else printf(stack is empty); }

15. Senem Kumova Metin Spring2009 STACKS (array implementation): main() x= pop(&n); push(11,&n); x= pop(&n); x= pop(&n); x= pop(&n); push(3,&n); push(2,&n); x= pop(&n); } main() { stack n; int x; reset(&n); push(4,&n); push(5,&n); push(3,&n); push(2,&n); push(1,&n);

16. Senem Kumova Metin Spring2009 Stacks: Linked List Implementation

17. Senem Kumova Metin Spring2009 #define EMPTY 0 #define FULL 10000 typedef char data; typedef enum {false, true} boolean; typedef struct { data d; struct node *next; } node ; typedef struct { int cnt; /* count of the elements */ node *top; /* pointer to the top element */ } stack; The header file: stack.h

18. Senem Kumova Metin Spring2009 boolean empty(const stack *stk); boolean full(const stack *stk); void initialize(stack *stk); void push(data d, stack *stk); char pop(stack *stk); char top(stack *stk); The header file: stack.h

19. Senem Kumova Metin Spring2009 boolean isempty(const stack *stk) { return (stk -> cnt == EMPTY); } boolean isfull(const stack *stk) { return (stk -> cnt == FULL); } void initialize(stack *stk) { stk -> cnt = 0; stk -> top = NULL; } data top(stack *stk) { return (stk -> top -> d); } Basic routines : Isempty(),Isfull(), Initialize(), Top()

20. Senem Kumova Metin Spring2009 void push(data d, stack *stk) { /* create new node */ node *p; p = malloc(sizeof(node)); p -> d = d; p -> next = stk -> top; /* assign new node as top node */ stk -> top = p; stk -> cnt++; } Basic routines : Push(),Pop() data pop(stack *stk) { data x; // will store the top data node *p; x = stk -> top -> d; p = stk -> top; stk -> top = stk -> top -> next; stk -> cnt- -; free(p); return x; }

21. Senem Kumova Metin Spring2009 void main(void) { char str[] = CS115; int i; stack s; initialize(&s); /* initialize the stack */ for (i = 0; str[i] != '\0'; ++i) /* fill stack */ { if (!full(&s)) push(str[i], &s); } printf(String in the stack: "); while (!empty(&s)) putchar(pop(&s)); }