队列与一般线性表不同的是，它只能在同一个方向进，另一方向出，由实现方法分成顺序栈和链栈，我们首先实现顺序栈。

我们建立一个头文件（duilie.h）用于建立结构体与函数等。

#include<iostream>
#include<string.h>
using namespace std;

struct Queue  //实现顺序队列
{
	char data[50];
	int front, rear;//队头队尾指针
};

void initQueue(Queue*& q)  //初始化空队列
{
	q = (Queue*)malloc(sizeof(Queue));
	q->front = q->rear = -1;
}

void createQueue(Queue*& q, char ass[])  //用ass建立队列
{
	q = (Queue*)malloc(sizeof(Queue));
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	q->front = q->rear = -1;
	for (i = ; i < n;i++)
	{
		q->rear = q->rear + 1;
		q->data[i] = ass[i];
	}
}

void destroyQueue(Queue*& q)  //销毁队列
{
	free(q);
}

bool emptyQueue(Queue*& q)  //判断队列是否空
{
	return q->front == q->rear;
}

void enQueue(Queue*& q, char e)  //将e进队
{
	if (q->rear >= 49)
		cout << "队列溢出";
	else
	{
		q->rear = q->rear + 1;
		q->data[q->rear] = e;
	}
}

char deQueue(Queue*& q)  //出队，并传出输出元素
{
	if (q->rear == q->front)
	{
		cout << "没有元素可出队";
		return ;
	}
	else
	{
		q->front = q->front + 1;
		return q->data[q->front];
	}
}

下面是验证程序。

#include<iostream>
#include<math.h>
#include<string.h>
#include"duilie.h"
using namespace std;
int main()
{
	char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
	Queue* qu;
	initQueue(qu);
	createQueue(qu, a);
	cout << emptyQueue(qu) << endl;
	enQueue(qu, '2');
	cout << qu->rear - qu->front << endl;
	int i;
	for (i = ; i < 10; i++)
	{
		cout << deQueue(qu);
	}
	destroyQueue(qu);
}

注：以上实现方法的缺陷是如果有元素出队，那么这些元素所占据的空间不会被释放；可以通过在front与rear上使用同余操作，从而构建环形队列，解决这个问题。

下面创建链队列，创建两种结构体，一种是普通结点，存储数据与后继指针，一种是链队结点，存储队头和队尾的指针，用于出入队操作。

struct qNode  //存储结点
{
	char data;
	qNode* next;
};
struct qHead  //链队结点，存储队头，队尾指针
{
	qNode *front, * rear;
};

void initQueue2(qHead*& q)  //初始化空队列
{
	q = (qHead*)malloc(sizeof(qHead));
	q->front = q->rear = NULL;
}

void initQueue2(qHead*& q)  //初始化空队列
{
	q = (qHead*)malloc(sizeof(qHead));
	q->front = q->rear = NULL;
}

void createQueue2(qHead*& q, char ass[])  //用ass为队列赋值
{
	qNode* s,*r;
	s = (qNode*)malloc(sizeof(qNode));
	s->data = ass[];
	s->next = NULL;
	q->front = q->rear = s;
	int i, n;
	n = strlen(ass) / sizeof(ass[]);
	for (i = 1; i < n; i++)
	{
		r = (qNode*)malloc(sizeof(qNode));
		s->next = r;
		r->data = ass[i];
		r->next = NULL;
		s = r;
	}
	q->rear = s;
}

void destroyQueue2(qHead*& q)  //销毁队列
{
	qNode *pre, *p;
	if (q->front != NULL)
	{
        pre = q->front;
		p = pre->next;
		while (p != NULL)
		{
			free(pre);
			pre = p;
			p = p->next;
		}
		free(pre);
		free(q);
	}
}

bool emptyQueue2(qHead*& q)  //判断队列是否为空
{
	return q->rear == NULL;
}

void enQueue2(qHead*& q, char e)  //将e入队
{
	qNode* s;
	s = (qNode*)malloc(sizeof(qNode));
	s->data = e;
	s->next = NULL;
	if (q->rear == NULL)
		q->rear = q->front = s;
	else
	{
		q->rear->next = s;
		q->rear = s;
	}
}

char deQueue2(qHead*& q)  //出队并输出出队元素
{
	if (q->rear == NULL)
	{
		cout << "队列为空";
		return ;
	}
	else
	{
		char e;
		qNode *s;
		s = (qNode*)malloc(sizeof(qNode));
		if (q->rear == q->front)
		{
			s = q->rear;
			e = s->data;
			free(s);
			q->rear = q->front = NULL;
		}
		else
		{
			s = q->front;
			e = s->data;
			q->front = s->next;
			free(s);
		}
		return e;
	}
}

下面是验证程序。

#include<iostream>
#include<math.h>
#include<string.h>
#include"duilie.h"
using namespace std;
int main()
{
	char x = '5', a[27] = "abcdefghijklmnopqrstuvwxyz";
	qHead* qu;
	initQueue2(qu);
	createQueue2(qu, a);
	cout << emptyQueue2(qu) << endl;
	enQueue2(qu, '2');
	int i;
	for (i = ; i < 27; i++)
	{
		cout << deQueue2(qu);
	}
	destroyQueue2(qu);
}

ITPub博客

数据结构与算法实现代码（5）——队列

最新文章