26.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Thursday 2006.12.14
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/26.txt)
Today: Chapter 12 continued

A stack: last-in, first-out.  No need to shift even in array implementation.
A queue: first-in, first-out (FIFO)
- we could use count only, but need to shift elements.
- normally maintain a head and a tail instead of element count

Question: how to indicate whether the queue is empty or full?
Answer: a little tricky! imagine this:
index of (head, tail)
Empty:(0, 0) -enqueue-> (0, 1) -enqueue-> (0, 2) -enqueue->..
      (0, 9) -enqueue-> (0, 10) 
      but actually, valid range is 0..9, so 10 % 10 => 0.
So, you are back to (0, 0) when the queue is full!!

Solutions:
- keep a separate state variable
  if head == tail after enqueue, then full;
  if head == tail after dequeue, then empty
- keep a count

/* array version of queue */
#include <stdio.h>
struct queue {
	int data[10];
	int size, head, tail;
	enum {Empty, Full, Neither} state;
};

typedef struct queue Queue, *QueuePtr;

void enqueue(QueuePtr q, int element);
int  dequeue(QueuePtr q);

/* this is to dequeue */
void
incrHead(QueuePtr q) {
	q->head = (q->head + 1) % q->size;
	q->state = (q->head == q->tail) ? Empty : Neither;
}

/* this is to enqueue */
void
incrTail(QueuePtr q) {
	q->tail = (q->tail + 1) % q->size;
	q->state = (q->head == q->tail) ? Full : Neither;
}


void enqueue(QueuePtr q, int element) {
	if (q->state == Full) {
		fprintf(stderr, "queue overflow\n");
		return;
	}
	q->data[q->tail] = element;
	incrTail(q);
}

int dequeue(QueuePtr q) {
	int element;
	if (q->state == Empty) {
		fprintf(stderr, "queue underflow\n");
		return;
	}
	element = q->data[q->head];
	incrHead(q);
	return element;
}

int printQueue(QueuePtr q) {
	/* print from head, as long as head is != tail */
	int i;
	printf("[");
	if (q->state != Empty) {
		int count = 0;
		for (i = q->head; i != q->tail || !count; i = (i + 1) % q->size, count++) {
			printf("%s%d", (count? ", ": ""), q->data[i]);
		}
	}
	printf("]\n");
}

int main() {
	char c[100];
	Queue Q;
	int element;
	Q.head = 0;
	Q.tail = 0;
	Q.size = 10;
	Q.state = Empty;
	while (fgets(c, 100, stdin) != NULL) {
		char cmd[10];
		int element;
		switch (sscanf(c, "%s%d", cmd, &element)) {
		case 0: continue;
		case 1: 
		case 2: 
			if (!strcmp(cmd, "enq")) { /* enqueue */
				enqueue(&Q, element);
				printQueue(&Q);
				continue;
			}
			if (!strcmp(cmd, "deq")) {
				int element = dequeue(&Q);
				printf("%d, ", element);
				printQueue(&Q);
				continue;
			}
			/* all others */
		}
		if (!strcmp(cmd, "quit")) {
			break;
		}
	}
}

Try it out (no prompt)

enq 10
[10]
enq 20
[10, 20]
enq 30
[10, 20, 30]
...
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
enq 101
queue overflow
...
120, []
deq
queue underflow
-1073745696, []


How to do it for a linked data structure?
easy: 

Maintain a queue head and a queue tail
- enqueue: pull from head
- dequeue: add to tail

(for complete code, see http://r638-2.cs.nthu.edu.tw/C/notes/qn.c )

struct queueNode {
	int data;
	struct qNode *next;
};

typedef struct queueNode QueueNode, *QueueNodePtr;

struct linkedQueue {
	QueueNodePtr head, tail;
};

typedef linkedQueue LQ, *LQPtr;

QueueNodePtr
MakeNewNode(int element, QueueNodePtr next) {
	QueueNodePtr newNode = malloc(sizeof(QueueNode));
	if (newNode == NULL) return NULL;
	newNode->data = element;
	newNode->next = next;
	return newNode;
}

void enqueue(LQPtr q, int element) {
	QueueNodePtr newNode = MakeNewNode(element, NULL);
	if (newNode == NULL) {
		fprintf(stderr, "queue overflow\n");
		return;
	}
	if (q->head == NULL) {
		q->head = q->tail = newNode;
	} else {
		q->tail = q->tail->next = newNode;
	}
}

int dequeue(LQPtr q) {
	QueueNodePtr dn;
	int element;
	if (q->head == NULL) {
		fprintf(stderr, "queue underflow\n");
	}
	dn = q->head;
	q->head = dn->next;
	if (q->head == NULL) {
		q->tail == NULL;
	}
	element = qn->data;
	free(dn);
	return element;
}