c++:不使用STL标准模板库,实现双端队列
文章目录
- c++:不使用STL标准模板库,实现双端队列
- 0.简介
- 1.怎么写
-
- 2.结尾
0.简介
最近一个实验验收要求不调用STL标准模板库(standard template library)用c++或c实现双端队列。那么如果使用标准模板库的话怎么实现呢?只需头文件包含deque,然后在代码中直接定义即可,定义参考 deque< int > Name;(上一篇博客已经提到过)。
不用stl直接实现的话也很简单,没有太多算法上的难度,只是稍微有一点繁琐。
1.怎么写
1.1思路
大概思路:
1.首先建立一个循环队列,采用宏定义定义NUM表示循环队列最多容纳的数据个数,也方便修改
2.根据简单算法类比双端队列的功能实现相应的功能,最终达到不采用stl实现双端队列的要求
1.2代码
下面上代码,
#include<iostream>
#include<stdlib.h>
#include<windows.h>
#include<vector>
#include<iomanip>
#include<stdlib.h>
#include<string>
#include<math.h>
using namespace std;
#define NUM 12
#define Elemtype int
typedef struct deQueue
{
Elemtype *base;
int front;
int back;
} deQueue;
void init(deQueue &Q)
{
Q.base = (Elemtype *)malloc(sizeof(Elemtype) * NUM);
Q.back = Q.front = 1;
}
int push_front(deQueue &Q, int x)
{
if(Q.front < Q.back)
if(Q.front == 1)
if(Q.back == NUM - 1) return 1;
else {
Q.front = NUM - 1;
Q.base[Q.front] = x;
}
else if(Q.front == Q.back)
if(Q.front == 1) {
Q.front = NUM - 1;
Q.base[Q.front] = x;
}
else {
--Q.front;
Q.base[Q.front] = x;
}
else
if(Q.front == Q.back + 1)
return 1;
else {
--Q.front;
Q.base[Q.front] = x;
}
}
return 0;
}
int push_back(deQueue &Q, int x)
{
if(Q.front == Q.back)
if(Q.back == NUM - 1) {
Q.base[Q.back] = x;
Q.back = 1;
}
else
Q.base[Q.back++] = x;
else if(Q.front < Q.back)
if(Q.back == NUM - 1)
if(Q.front == 1) return 1;
else {
Q.back = 1;
Q.base[Q.back] = x;
}
else Q.base[Q.back++] = x;
else
if(Q.back + 1 == Q.front) return 1;
else Q.base[Q.back++] = x;
return 0;
}
int pop_front(deQueue &Q)
{
if(Q.front == Q.back) return 1;
else if(Q.front < Q.back) ++Q.front;
else
if(Q.front == NUM - 1) Q.front = 1;
else ++Q.front;
return 0;
}
int pop_back(deQueue &Q)
{
if(Q.back > Q.front) --Q.back;
else if(Q.back == Q.front) return 1;
else
if(Q.back == 1) Q.back = NUM - 1;
else --Q.back;
return 0;
}
void print_queue(deQueue &Q)
{
int n;
if(Q.front == Q.back) {
cout << "empty!" << endl;
return;
}
else if(Q.front < Q.back) {
cout << "队列内容为: " << endl;
for (n = Q.front; n < Q.back; ++n)
{
cout << Q.base[n] << " ";
}
cout << endl;
}
else {
cout << "队列内容为: " << endl;
for (n = Q.front; n < NUM; ++n) cout << Q.base[n] << " ";
for (n = 1; n < Q.back; ++n) cout << Q.base[n] << " ";
cout << endl;
}
}
int main()
{
deQueue Q;
init(Q);
int choose;
cout << "输入1在队首加入元素" << endl
<< "输入2在队尾加入元素" << endl
<< "输入3在队首删除元素" << endl
<< "输入4在队尾删除元素" << endl
<< "输入5退出" << endl;
while(1)
{
cin >> choose;
switch(choose)
{
case 1:
cout << "要在队首添加一个23之后的队列为:" << endl;
if(push_front(Q, 23) == 1)
cout << "队列已满!" << endl;
print_queue(Q);
break;
case 2:
cout << "要在队尾添加一个12之后的队列为:" << endl;
if(push_back(Q, 12) == 1)
cout << "队列已满!" << endl;
print_queue(Q);
break;
case 3:
cout << "删除队首元素后的队列为:" << endl;
pop_front(Q) == 1;
print_queue(Q);
break;
case 4:
cout << "删除队尾元素后的队列为:" << endl;
pop_back(Q) == 1;
print_queue(Q);
break;
default:
goto loop;
}
}
loop:
system("pause");
return 0;
}
2.结尾
今天就到这里,希望明天能够验收成功!
结尾箴言:越努力,越幸运!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)