队列的数组实现和链表实现

话不多少，数组实现上代码：

 

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
using namespace std;
const int maxsize=10;
//循环队列的结构体
typedef struct{
	int data[maxsize];
	int front;//队列头
	int rear;//队列尾
}sequeue;
sequeue *sq=new sequeue;//定义全局指针并且分配内存
/*front指向队头元素的前一个位置
 *rear指向队尾要插入元素的位置
 *数组中能存放的数据要比数组的空间小1，是为了判断队列满的情况。
 *定义值真是，sq->front。定义全局变量sequeue sq时，sq.front
 */
void SetEmpty(){//置空，为了第一个进入队列的元素的位置为0
	sq->front=maxsize;
	sq->rear=maxsize;
}
bool isEmpty(){//判空
	return (sq->rear==sq->front);
}
void EnQueue(int num){//进队，先判满，再移位后输入元素
	assert((sq->rear+1)%maxsize!=sq->front);
	sq->rear=(sq->rear+1)%maxsize;
	sq->data[sq->rear]=num;
}

bool isFull(){//判满
	return((sq->rear+1)%maxsize==sq->front);
}

int DeQueue(){//出队，先判空，再移位
	assert(sq->front!=sq->rear);	
	sq->front=(sq->front+1)%maxsize;
	int ndata=sq->data[sq->front];
	return ndata;
}
int main(){
	SetEmpty();
	if(isEmpty())
		cout<<"The queue is empty"<<endl;
	for(int i=0;i<9;i++)
		EnQueue(i);
	if(isFull())
		cout<<"The queue is full"<<endl;
	for(int j=0;j<3;j++)
		cout<<DeQueue()<<"was removed"<<endl;
	system("pause");
	return 1;
}

链表实现，上代码

//队列链表方式的限制为表头删除表尾插入的单链表，显然
//单链表的头指针不便于在表尾做插入操作，所以我们需要加上一个尾指针
//于是一个链队列由一个头指针和一个尾指针唯一的确定。
struct node{
	int data;//值
	struct node* next;//链接指针
};
struct linkqueue{
	struct node* front;//队头指针
	struct node* rear;//队尾指针
};
//初始化
void initQueue(struct linkqueue *hq){
	//hq=(linkqueue*)malloc(sizeof(linkqueue));
	hq->front=hq->rear=NULL;//将队手和队尾指针置空
	return;
}
//入队
void enQueue(struct linkqueue* hq,int x){
	//申请新节点
	struct node* newP;
	newP=(node*)malloc(sizeof(struct node));
	if(newP==NULL){
		cout<<"内存空间分配失败"<<endl;
		return;
	}
	newP->data=x;
	newP->next=NULL;
	if(hq->rear==NULL)
	{
		hq->front=newP;
		hq->rear=newP;
	}else{
		hq->rear->next=newP;
		hq->rear=newP;
	}
	return;
}
//出队
int outQueue(linkqueue* hq){
	struct node* p;
	int x;
	if(hq->front==NULL){
		cout<<"队列为空无法删除"<<endl;
		return -1;
	}
	x=hq->front->data;
	p=hq->front;
	if(hq->front==hq->rear){//判断是否只有一个节点
		hq->front=NULL;
		hq->rear=NULL;
	}
	else{
		hq->front=p->next;
	}
	free(p);
	return x;
}
//取队首元素
int peekQueue(struct linkqueue* hq){
	if(hq->front==NULL){
		cout<<"队列为空无法删除"<<endl;
		exit(1);
	}
	return hq->front->data;
}
//检查队列是否为空
bool emptyQueue(struct linkqueue* hq){
	if(hq->front==NULL)
		return true;
	else
		return false;
}
//清除队列所有元素
void clearQueue(struct linkqueue *hq){
	struct node* p=hq->front;
	while(p!=NULL){
		hq->front=hq->front->next;
		free(p);
		p=hq->front;
	}
}

int main(){
	struct linkqueue q;
	int a[8]={3,5,8,27,9,30,15,22};
	initQueue(&q);
	for(int i=0;i<8;i++)
		enQueue(&q,a[i]);
	cout<<outQueue(&q)<<endl;
	while(!emptyQueue(&q))
		cout<<outQueue(&q)<<endl;
	if(emptyQueue(&q))
		cout<<"队列已为空"<<endl;
	else
		clearQueue(&q);
	system("pause");
	return 1;
}