数据结构——链队列
程序员文章站
2022-05-04 16:25:20
...
链队列
空队列
元素x入队列
元素y入队列
元素x出队列
C++代码实现
/*------链队列基本操作-------*/
/*
front指针指向头结点(第一个结点的前一个)
rear指针指向最后一个结点
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef int Status;
typedef int QElemType;
#define MAXSIZE 100
typedef 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