数据结构 队列
学习完了线性结构的最后一个类型了，接下来似乎就是很难实现的分支结构了，一个红黑树似乎会有上千行代码的样子，不知道到时候要写多久。
实现了顺序队列，链式队列，循环队列，顺序双端队列，链式双端队列，同时对优先队列有了一定了解
代码实现如下：
顺序队列：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class m_queue
{
public:
m_queue(int n)
{
size = n;
data = new T[size];
if (data == nullptr)
{
cout << "开辟失败" << endl;
}
front = 0;
rear = 0; //指向最后一个元素下一个位置
}
void En_queue(T k)
{
//判满(牺牲一个位置)
if (rear == size - 1)
{
cout << "队满" << endl;
}
else
{
data[rear] = k;
cout << k << "入队" << endl;
rear++;
}
}
void Del_queue()
{
int x(0);//记录出队元素
//判空
if (front == rear)
{
cout << "队空" << endl;
}
else
{
x = data[front];
cout << x << "出队" << endl;
front++;
}
}
void m_empty()
{
if (front == rear)
{
cout << "队空" << endl;
}
}
void m_full()
{
if (rear == size)
{
cout << "队满" << endl;
}
}
public:
int size;//队列大小
T* data;
int front; //队头指针
int rear; //队尾指针
};
int main()
{
m_queue<int> q(5);
q.En_queue(10);
q.En_queue(9);
q.En_queue(8);
q.En_queue(7);
q.En_queue(6);
q.En_queue(6);
q.Del_queue();
q.Del_queue();
q.Del_queue();
return 0;
}
链式队列：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class q_node
{
public:
T data;
q_node<T>* next;
};
template<class T>
class Link_queue
{
public:
Link_queue()
{
head = new q_node<T>;
rear = head;
if (head == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
head->next = nullptr;
rear->next = nullptr;
}
}
void En_queue(T k)
{
q_node<T>* s = new q_node<T>;
if (s == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
s->data = k;
s->next = nullptr; //新节点插入队尾
rear->next = s;
rear = s;
cout << k << "入队" << endl;
}
}
void Del_queue()
{
//出队时需要注意是否时首元节点出队
T x(0);//保存出队元素
//判空
//1.head->next == nullptr
//2.head == rear
if (head->next == nullptr)
{
cout << "队空" << endl;
}
else
{
q_node<T>* p = head->next;
x = p->data;
head->next = head->next->next;
if (head->next == nullptr)//删除唯一节点时避免队尾指针成为野指针
{
rear = head;
}
delete p;
p = nullptr;
cout << x << "出队" << endl;
}
}
void m_empty()
{
if (head->next == nullptr)
{
cout << "队空" << endl;
}
}
public:
q_node<T>* head;//指向头节点的指针
q_node<T>* rear;//指向队尾元素所在节点的指针
};
int main()
{
Link_queue<int> q;
q.En_queue(3);
q.En_queue(4);
q.En_queue(5);
q.En_queue(6);
q.En_queue(7);
q.En_queue(8);
q.En_queue(9);
q.Del_queue();
return 0;
}
循环队列：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class m_queue
{
public:
m_queue(int n)
{
size = n;
data = new T[n];
if (data == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
rear = 0; //指向队尾元素下一个位置
front = 0;
}
}
void enqueue(T k)
{
//判满(牺牲一个空间与判空区分)
if ((rear + 1) % size == front)
{
cout << "队满" << endl;
}
else
{
data[rear] = k;
cout << k << "入队" << endl;
rear = (rear + 1) % size;
}
}
void dequeue()
{
int x; //用于保存出队元素
//判空
if (front == rear)
{
cout << "队空" << endl;
}
else
{
x = data[front];
front = (front + 1) % size;
cout << x << "出队" << endl;
}
}
void m_empty()
{
if (front == rear)
{
cout << "队空" << endl;
}
}
void m_full()
{
if ((rear + 1) % size == front)
{
cout << "队满" << endl;
}
}
public:
T *data;
int front; //队头指针
int rear; //队尾指针
int size; //队列大小
};
int main()
{
m_queue<int> q(10);
q.enqueue(10);
q.enqueue(11);
q.enqueue(12);
q.enqueue(13);
q.enqueue(14);
q.enqueue(15);
q.enqueue(16);
q.enqueue(17);
q.enqueue(18);
q.enqueue(19);
q.dequeue();
q.dequeue();
return 0;
}
顺序双端队列：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class dequeue
{
public:
dequeue(int n)
{
length = n;
data = new T[length];
if (data == nullptr)
{
cout << "分配失败" << endl;
}
else
{
size = 0;
left = 0;
right = 0;
}
}
//规定0位置存储右端入队第一个元素
void En_queue_left(T k)
{
//判满
if (size == length)
{
cout << "队满" << endl;
}
else
{
//防止左指针为负数
left = (left - 1 + length) % length;
data[left] = k;
cout << k << "入队" << endl;
size++;
}
}
void Del_queue_left()
{
//判空
if (size == 0)
{
cout << "队空" << endl;
return;
}
T x(0);//存储出队元素
x = data[left];
left = (left + 1 + length) % length;
cout << x << "出队" << endl;
size--;
}
void En_queue_right(T k)
{
//判满
if (size == length)
{
cout << "队满" << endl;
}
else
{
//右指针指向最后一个元素下一个位置
data = k;
right = (right + 1) % length;
size++;
}
}
void Del_queue_right()
{
//判空
if (size == 0)
{
cout << "队空" << endl;
return;
}
T x(0);//存储出队元素
right = (right - 1 + length) % length;
x = data[right];//因为0位置存储右端入队第一个元素，所以right指向右端元素下一个位置
cout << x << "出队" << endl;
size--;
}
void m_empty()
{
if (size == 0)
{
cout << "队空" << endl;
return;
}
}
void m_full()
{
if (size == length)
{
cout << "队满" << endl;
}
return;
}
public:
T* data;
int left;
int right;
int size;//队列实际大小
int length;//队列长度
};
int main()
{
dequeue<int> dq(10);
dq.En_queue_left(10);
dq.En_queue_left(11);
dq.En_queue_left(12);
dq.Del_queue_right();
dq.Del_queue_right();
dq.Del_queue_right();
return 0;
}
链式双端队列：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cassert>
using namespace std;
template<class T>
class q_Node
{
public:
T date;
q_Node* next;
q_Node* pre;
};
template<class T>
class LinkDequeue
{
public:
q_Node<T>* right;
q_Node<T>* left;
public:
LinkDequeue()
{
left = new q_Node<T>;
if (left == nullptr)
{
cout << "开辟失败" << endl;
}
else
{
right = left;
right->next = nullptr;
right->pre = nullptr;
left->next = nullptr;
left->pre = nullptr;
}
}
//规定第一次入队时，中间节点固定存放右边第一次入队元素
void En_deque_left(T k)
{
q_Node<T>* s = new q_Node<T>;
s->date = k;
s->pre = left->pre;
s->next = left;
left->pre = s;
left = s;
cout << left->date << "入队" << endl;
}
void Del_deque_left()
{
//判空
if (left == right)
{
cout << "队空" << endl;
}
else
{
//存储出队节点
q_Node<T>* q = left;
left = left->next;
left->pre = nullptr;
cout << q->date << "出队" << endl;
delete q;
q = nullptr;
}
}
void En_deque_right(T k)
{
q_Node<T>* s = new q_Node<T>;
right->date = k;
cout << right->date << "入队" << endl;
s->pre = right;
s->next = right->next;
right->next = s;
right = s;
}
void Del_deque_right()
{
//判空
if (left == right)
{
cout << "队空" << endl;
}
else
{
//存储出队元素
q_Node<T>* s = right;
right = right->pre;
right->next = nullptr;
//从逻辑上实现出队
cout << right->date << "出队" << endl;
delete s;
s = nullptr;
}
}
void m_empty()
{
if (left == right)
{
cout << "队空" << endl;
}
}
};
int main()
{
LinkDequeue<int> dq;
dq.En_deque_left(6);
dq.En_deque_left(5);
dq.En_deque_left(4);
dq.En_deque_right(3);
dq.Del_deque_left();
dq.Del_deque_left();
dq.Del_deque_right();
dq.Del_deque_right();
return 0;
}