[数据结构与算法]用链表实现的队列

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<stdbool.h>
#define TRUE 1
#define FALSE 0
using namespace std;

//队列用链表来实现
//需要设置两个指针分别指示队列的头和尾
typedef int QueueElemType;
typedef struct node {
	QueueElemType data;
	struct node *next;
}LinkQueueNode;

typedef struct {
	LinkQueueNode * front;
	LinkQueueNode *rear;
}LinkQueue;

//链队列的初始化
int InitLinkQueue(LinkQueue *Q) {
	Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
	if (Q->front) {
		Q->rear = Q->front;
		Q->front->next = NULL;
		return TRUE;
	}
	else
		return FALSE;
}

//判断队列是否为空
int IsEmpty(LinkQueue Q)
{
	return Q.front->next == NULL;
}

//判断队列是否满了
//int IsFull(LinkQueue Q)
//{
//
//}

//元素入队列操作
int EnterQueue(LinkQueue *Q, QueueElemType x)
{
	LinkQueueNode *p;
	p = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
	if (p) {
		p->data = x;
		p->next = NULL;
		Q->rear->next = p;
		Q->rear = p;
		return TRUE;
	}
	else
		return FALSE;
 }

//出队列操作
int DeleteQueue(LinkQueue *Q, QueueElemType *x)
{
	if (Q->rear == Q->front)
		return FALSE;
	LinkQueueNode * p;
	p = Q->front->next;
	Q->front->next = p->next;
	if (Q->rear == p)
		Q->rear = Q->front;
	*x = p->data;
	free(p);
	return TRUE;
}

//取队列的队头元素
int GetHead(LinkQueue *Q,  QueueElemType *x) {
	if (Q->front->next == NULL) {
		return FALSE;
	}
	*x = Q->front->next->data;
	return TRUE;
}

//清空队列
int ClearQueue(LinkQueue *Q) {
	LinkQueueNode * p = Q->front->next, *temp;
	Q->front->next = NULL;
	Q->rear = Q->front;
	while (p) {
		temp = p->next;
		free(p);
		p = temp;
	}
	return TRUE;
}

//打印杨辉三角形
//借助队列
void YangHuiTrianglePrint(int n)
{
	LinkQueue Q;
	InitLinkQueue(&Q);
	EnterQueue(&Q, 1);
	int temp, head,sum;
	for (int i = 2; i <= n; i++) {
		for (int k = 1; k <= n - i + 1; k++) {
			cout << " ";
		}
		EnterQueue(&Q, 1);
		for (int j = 1; j <= i - 2; j++) {
			DeleteQueue(&Q, &temp);
			cout << temp<<" ";
			GetHead(&Q, &head);
			sum = temp + head;
			EnterQueue(&Q, sum);
		}
		DeleteQueue(&Q, &temp);
		cout << temp;
		cout << endl;
		EnterQueue(&Q, 1);
	}
	while (!IsEmpty(Q)) {
		DeleteQueue(&Q, &temp);
		cout << temp<<" ";
	}
	cout<< endl;
}

int main()
{
	YangHuiTrianglePrint(8);
	return 0;
}