数据结构：链队列

实验目标：

提示

（1）初始化链队列为空队列

（2）新元素e入队列，成功返回true，失败返回false

（3）出队列，即删除队首元素，并用e返回出元素值，成功返回true，失败返回false

（4）读队首元素，用e返回队首元素，不出队，成功返回true，失败返回false

（5）遍历链队列，将队列数据元素依次输出

（6）销毁链队列

提示

据我发现，所谓队列先进先出，和链表的尾插法类似之处

---

实验代码

#include <bits/stdc++.h>>
using namespace std;

#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0
#define INFEASIBLE  -1
#define OVERFLOW    -2

typedef int Status;
typedef int QElemType;

typedef struct QNode{//定义一个新队列
    QElemType data;
    struct QNode *next;
}QNode,*Queue;

typedef struct{
    Queue front;
    Queue rear;
}LinkQueue;

Status InitQueue (LinkQueue &Q) //初始化链队列为空队列
{
    Q.front=Q.rear=(Queue)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;

    cout<<endl;//纯粹为了好看
    return OK;
}

Status EnQueue (LinkQueue &Q, QElemType e) //入队列
{
    struct QNode* newNode=(Queue)malloc(sizeof(QNode));
    if(!newNode) exit(OVERFLOW);
    newNode->data=e;
    newNode->next=NULL;
    Q.rear->next=newNode;
    Q.rear=newNode;
    return OK;
}

Status DeQueue (LinkQueue &Q, QElemType &e)//出队列
{
    struct QNode* p=(Queue)malloc(sizeof(QNode));
    if(Q.front==Q.rear) return ERROR;
    p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    free(p);
    return e;
}

Status GetHead(LinkQueue &Q)//返回队首元素
{
    if(Q.front==Q.rear) return FALSE;
    struct QNode* posNode=(Queue)malloc(sizeof(QNode));
    posNode=Q.front->next;
    cout<<posNode->data<<endl;
    return OK;
}

Status Traverse(LinkQueue &Q)//遍历
{
    if(Q.front==Q.rear) return FALSE;
    struct QNode* posNode=Q.front->next;
    while(posNode!=NULL){
        cout<<posNode->data<<" ";
        posNode=posNode->next;
    }
    cout<<endl;//纯粹为了好看
    return OK;
}

Status Destroy(LinkQueue &Q)//销毁队列
{
    if(Q.front==Q.rear) return FALSE;
    while(Q.front){
        Q.rear=Q.front->next;
        free(Q.front);
        Q.front=Q.rear;
    }
    cout<<endl;//纯粹为了好看
    return OK;
}

int main()//主函数
{
    LinkQueue Q;
    int e;

    while(1){
		cout<<endl;
		cout<<"**1,初始化队列"<<endl;
		cout<<"**2,将元素e入列"<<endl;
	    cout<<"**3,出队列，用e返回出队列元素"<<endl;
	    cout<<"**4,返回列首元素"<<endl;
		cout<<"**5,遍历队列"<<endl;
		cout<<"**6,销毁队列"<<endl;
		cout<<"**0,退出系统"<<endl<<endl;

		int choice;
		cout<<"请输入要进行的操作：";
		cin>>choice;
		cout<<endl;

		switch(choice){
			case 1:InitQueue(Q);break;
			case 2:{
				int n;
				cout<<"请输入本次入队的元素个数：";
				cin>>n;

				cout<<endl<<"请输入要插入的元素：";
				for(int i=1;i<=n;i++){
					cin>>e;
					EnQueue(Q,e);
				}
				cout<<"入栈成功！"<<endl;
				break;
			}
			case 3:{
                DeQueue(Q,e);
				cout<<"出队成功！"<<endl;
				break;
			}
			case 4:GetHead(Q);break;
            case 5:Traverse(Q);break;
			case 6:Destroy(Q);break;
			case 0:exit(0);
		}
	}

    system("pause");
    return 0;
}