数据结构——链队列

数据结构——链队列"/>

数据结构——链队列

链队列

空队列

元素x入队列

元素y入队列

元素x出队列

C++代码实现

/*------链队列基本操作-------*/
/*
front指针指向头结点（第一个结点的前一个）
rear指针指向最后一个结点
*/
#include<iostream>
#include<stdlib.h>
using namespace std;#define OK 1
#define ERROR -1
#define OVERFLOW -2typedef int Status;
typedef int QElemType;#define MAXSIZE 100typedef struct Qnode {QElemType data;struct Qnode* next;
}Qnode, * QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;
}LinkQueue;Status InitLQueue(LinkQueue& Q) {Q.front = new Qnode;if (!Q.front) exit(OVERFLOW);Q.rear = Q.front;Q.front->next = NULL;return OK;
}// 判断链队列是否为空
bool LQueueEmpty(LinkQueue Q) {return (Q.front == Q.rear);
}// 入队
Status PushLQueue(LinkQueue& Q, QElemType e) {QueuePtr q;q = new Qnode;if (!q)  exit(OVERFLOW);q->data = e;q->next = NULL;Q.rear->next = q;Q.rear = q;return OK;
}// 出队
Status PopLQueue(LinkQueue& Q, QElemType& e) {QueuePtr q;if(LQueueEmpty(Q)) return ERROR;q = Q.front->next;e = q->data;Q.front->next = q->next;if (Q.rear == q) Q.rear = Q.front;delete q;return OK;
}// 销毁链队列
Status DestroyQueue(LinkQueue& Q) {while (Q.front) {Q.rear = Q.front->next;delete Q.front;Q.front = Q.rear;}return OK;
}// 获取队头元素
Status GetHead(LinkQueue Q, QElemType& e) {if (LQueueEmpty(Q)) return ERROR;e = Q.front->next->data;return OK;
}// 创建链队列
void CreateLQueue(LinkQueue& Q, int m) {QElemType e;for (int i = 1; i <= m; i++) {cout << "请输入第" << i << "个元素: ";cin >> e;PushLQueue(Q, e);}
}// 输出链队列
void OutPut(LinkQueue Q) {QueuePtr q;q = new Qnode;q = Q.front->next;while (q) {cout << q->data << " ";q = q->next;}cout << endl;
}int main()
{// 测试代码LinkQueue Q;int m;QElemType e;InitLQueue(Q);cout << "请输入链队列的长度: ";cin >> m;CreateLQueue(Q, m);cout << "链队列元素为: ";OutPut(Q);GetHead(Q, e);cout << "队头元素为: " << e << endl;cout << "请输入入队元素: ";cin >> e;PushLQueue(Q, e);cout << "链队列元素为: ";OutPut(Q);PopLQueue(Q, e);cout << "出列元素为: " << e << endl;cout << "链队列元素为: ";OutPut(Q);return 0;
}

请输入链队列的长度: 3
请输入第1个元素: 1
请输入第2个元素: 2
请输入第3个元素: 3
链队列元素为: 1 2 3
队头元素为: 1
请输入入队元素: 4
链队列元素为: 1 2 3 4
出队元素为: 1
链队列元素为: 2 3 4