C範例程式 : 堆疊與佇列

堆疊(stack) : 先進後出(First In Last Out, FILO), 可以將容器想像成桶子, 放進去的東西一層一層疊上去. 拿出來時自然就是後來進去的東西先拿出來.
佇列(queue) : 先進先出(First In First Out, FIFO),可以將容器想像成水管, 只從一頭放東西進去, 且只能從另一頭取出. 所以自然是先進入的東西先拿出來.
以上兩種資料結構都將以陣列及鍊結串列實現.

堆疊
陣列 include stdio.h

#define ASIZE 5

int stack[ASIZE]={0};
int top=-1;

void push();
void pop();
void display();
void release();

int main()
{
	int choice;

	printf("陣列堆疊測試程式(可儲存資料筆數%d)\n", ASIZE+1);

	while(1)
	{
		printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
		scanf("%d",&choice);

		if(!choice)
			break;

		switch(choice)
		{
			case 1:		push();		break;
			case 2:		pop();		break;
			case 3:		display();	break;
			default:	display();	break;
		}
	}
	printf("清空堆疊\n");
	release();

	return 0;
}

void push()
{
	int d;

	if(top < ASIZE)
	{
		printf("請輸入資料(整數) : ");
		scanf("%d",&d);
		top++;
		stack[top] = d;
	}
	else
	{
		printf("堆疊滿了\n");
	}
}


void pop()
{
	if(top >= 0)
	{
		printf("%3d\n",stack[top]);
		top--;
	}
	else
	{
		printf("堆疊是空的\n");
	}
}

void display()
{
	int pos = top;
	while(pos >= 0)
	{
		printf("%3d ",stack[pos]);
		pos--;
	}
	printf("\n");
}

void release()
{
	while(top >= 0)
		pop();
}

鍊結串列 include stdio.h malloc.h

typedef struct _node * pnode;

struct _node{
	int data;
	pnode next;
}node;

pnode head;

void init();
void push();
void pop();
void display();
void release();

int main()
{
	int choice;

	init();

	printf("串列堆疊測試程式\n");

	while(1)
	{
		printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
		scanf("%d",&choice);

		if(!choice)
			break;

		switch(choice)
		{
			case 1:		push();		break;
			case 2:		pop();		break;
			case 3:		display();	break;
			default:	display();	break;
		}
	}
	printf("清空堆疊\n");
	release();

	return 0;
}

void init()
{
	head = NULL;
}

void push()
{
	int d;
	pnode p = (pnode)malloc(sizeof(node));

	printf("請輸入資料(整數) ");
	scanf("%d",&d);

	p->data = d;
	p->next = head;
	head = p;
}


void pop()
{
	pnode p;

	if(head)
	{
		p = head;
		head = head->next;
		printf("刪除 %d \n",p->data);
		free(p);
	}
	else
	{
		printf("堆疊是空的\n");
	}
}

void display()
{
	pnode p = head;

	while(p)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
}

void release()
{
	pnode p;
	while(head)
	{
		p = head;
		head = head->next;
		free(p);
	}
}

佇列
陣列 include stdio.h

#define QSIZE 5

int queue[QSIZE];
int head, tail;

void init();
int isFull();
int isEmpty();
void enqueue();
void dequeue();
void display();
void release();

int main()
{
	int choice;

	printf("陣列佇列測試程式(可儲存資料筆數%d)\n", QSIZE+1);

	while(1)
	{
		printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
		scanf("%d",&choice);

		if(!choice)
			break;

		switch(choice)
		{
			case 1:		enqueue();	break;
			case 2:		dequeue();	break;
			case 3:		display();	break;
			default:	display();	break;
		}
	}
	printf("清空串列\n");
	release();

	return 0;
}

void init()
{
	head = tail = 0;
}

int isFull()
{
	if((tail+1)%QSIZE == head)
	{
		printf("佇列已滿\n");
		return 1;
	}
	return 0;
}

int isEmpty()
{
	if(head%QSIZE == tail%QSIZE)
	{
		printf("佇列已空\n");
		return 1;
	}
	return 0;
}

void enqueue()
{
	int d;

	if(!isFull())
	{
		printf("請輸入資料 ");
		scanf("%d",&d);
		tail++;
		tail%=QSIZE;
		queue[tail] = d;
	}
}


void dequeue()
{
	if(!isEmpty())
	{
		head++;
		head%=QSIZE;
		printf("刪除資料 %d\n",queue[head]);
	}
}

void display()
{
	for(int i = (head+1)%QSIZE; i != (tail+1)%QSIZE;)
	{
		printf("%d ",queue[i]);
		i++;
		i%=QSIZE;
	}
	printf("\n");
}

void release()
{
	for(int i = (head+1)%QSIZE; i != (tail+1)%QSIZE;)
	{
		queue[i]=-1;
		i++;
		i%=QSIZE;
	}
}

鍊結串列 include stdio.h malloc.h string.h

#define MAXSTR 50

typedef struct _node * pnode;

struct _node{
	char name[MAXSTR];
	char phone[MAXSTR];
	pnode next;
}node;

pnode head, tail;

void init();
void enqueue();
void dequeue();
void display();
void release();

int main()
{
	int choice;

	printf("鍊結串列佇列測試程式\n");

	while(1)
	{
		printf("1) 新增\t2) 刪除\t3) 顯示\t0) 結束 : ");
		scanf("%d",&choice);

		if(!choice)
			break;

		switch(choice)
		{
			case 1:		enqueue();	break;
			case 2:		dequeue();	break;
			case 3:		display();	break;
			default:	display();	break;
		}
	}
	printf("清空串列\n");
	release();

	return 0;
}

void init()
{
	head = tail = NULL;
}

void enqueue()
{
	pnode p = (pnode)malloc(sizeof(node));

	if(p)
	{
		printf("請輸入姓名 ");
		scanf("%s", p->name);
		printf("請輸入電話 ");
		scanf("%s", p->phone);
		p->next = NULL;
		if(head)
		{
			tail->next = p;
			tail = p;
		}
		else
		{
			head = tail = p;
		}
	}
	else
	{
		printf("無法取得記憶體空間新增資料\n");
	}
}


void dequeue()
{
	pnode p;

	if(head)
	{
		p = head;
		if(head->next)
			head = head->next;
		else
			head = tail = NULL;
		printf("刪除資料姓名 %s 電話 %s\n", p->name, p->phone);
		free(p);
	}
	else
	{
		printf("串列已空\n");
	}
}

void display()
{
	pnode p;
	p = head;

	while(p)
	{
		printf("姓名 %s 電話 %s\n", p->name, p->phone);
		p = p->next;
	}
}

void release()
{
	pnode p;

	tail = NULL;
	while(head)
	{
		p = head;
		head = head->next;
		free(p);
	}
}