队列:链表实现
结构描述:
typedef int DataType;
typedef struct QueueNode {
DataType A;
struct QueueNode * Next;
}Node;
class QueueLinked {
public:
//队头、队尾指针
Node * Front;
Node * Next;
//队列操作
//把元素X入队
void Push(DataType X);
//把队头元素出队
void Pop();
//销毁队列
void MakeEmpty();
//判断队列是否为空,为空返回true
bool IsEmpty();
//初始化(创建空队)
void Init();
//获取队头,队尾元素
DataType GetFront();
DataType GetRear();
//创建节点
Node * BuyNode(DataType X);
};
初始化:(创建空队)
把 Front
和 Rear
指向空。
void QueueLinked::Init() {
Front = Rear = nullptr;
}
判空
当 Front
指向空时,即队列为空
bool QueueLinked::IsEmpty() {
return Front == nullptr;
}
创建节点
把数据 X
传到 BuyNode()
方法中,用 malloc()
函数动态分配一个节点:
- 分配成功:返回节点指针;
- 分配失败:报错退出;
Node * QueueLinked::BuyNode(DataType X) {
Node * NewNode = (Node *)malloc(sizeof(Node));
// Node * NewNode = (Node *)malloc(sizeof(DataType));
if (NewNode == nullptr) {
cout << "Malloc Failed!" << endl;
exit(-1);
}
else {
NewNode->A = X;
NewNode->Next = nullptr;
}
return NewNode;
}
入队:
- 若队为空,则创建新节点
NewNode
,把NewNode
同时赋值给Front
与Rear
- 若队非空,则把
NewNode
接在Rear
指针之后,即Rear->Next = NewNode
void QueueLinked::Push(DataType X) {
if (IsEmpty()) {
Node * NewNode = BuyNode(X);
Front = Rear = NewNode;
}
else {
Node * NewNode = BuyNode(X);
Rear->Next = NewNode;
Rear = Rear->Next;
}
}
出队
- 若队为空:报错
- 若队非空:操作
Front
指针,进行出队操作- 用临时变量
Tmp
保存当前Front
指针所指向的位置; - 把
Front
指针向后移动一位Front = Front->Next
; - 释放
Tmp
,并将其置空
- 用临时变量
void QueueLinked::Pop() {
if (IsEmpty()) {
cout << "Queue Is Empty!" << endl;
exit(-1);
}
else {
Node * Tmp = Front;
Front = Front->Next;
free(Tmp);
Tmp = nullptr;
}
}
获取队头、队尾元素
直接返回 Front
和 Rear
的数据域即可,若表为空,则不可获取。
DataType QueueLinked::GetFront() {
if (IsEmpty()) {
cout << "Queue Is Empty!" << endl;
exit(-1);
}
return Front->A;
}
DataType QueueLinked::GetRear() {
if (IsEmpty()) {
cout << "Queue Is Empty!" << endl;
exit(-1);
}
return Rear->A;
}
摧毁队列
只要队列不为空,即 IsEmpty()
为假时,就一直出队,直到队空为止。
void QueueLinked::MakeEmpty() {
while (!IsEmpty()) {
Pop();
}
}
踩坑记录
报错:
warning: HEAP[a.exe]:
warning: Heap block at 0000000000A93BA0 modified at 0000000000A93BB8 past requested size of 4
Thread 1 received signal SIGTRAP, Trace/breakpoint trap.
0x00007ffe6fb8a503 in ntdll!RtlRegisterSecureMemoryCacheCallback () from C:\Windows\SYSTEM32\ntdll.dll
原因:
在动态内存分配时,都将 DataType
类型大小分配给了 Node
类型的指针,导致的错误。
Node * NewNode = (Node *)malloc(sizeof(DataType));
修正
Node * NewNode = (Node *)malloc(sizeof(Node));
标签:Node,队列,QueueLinked,链表,DataType,Front,NewNode,数据结构,Rear
From: https://www.cnblogs.com/codels/p/18309459