《数据结构》C++代码 栈与队列
2024-10-21 07:45:57
线性表中,先进先出的叫队列,先进后出的叫栈。队列常用于BFS,而在函数递归层数过高时,需要手动实现递归过程,这时候便需要写一个“手动栈”。
有时候,我们会有大量数据频繁出入队列,但同时存在其内的元素却不多,此时需要写“循环队列”。其代码并不难,但里面下标递增的语句值得斟酌一下。
k=(k+)%maxn;
这句话用到了取模运算%,是非常浪费时间的。若能避免使用%,则可以大大提高代码运行速度。我做了一个测试,把下面五种语句写法分别运行5×10^8次,在我的机器上用codeblocks10.05各运行5次,取平均数,时间如下所示:
i=(i==maxn-)?:(i+); // 用时1.582s
if(i==maxn-) i=; else ++i; // 用时1.588s
++i; if(i==maxn) i=; // 用时1.605s
++i; i=(i==maxn)?:i; // 用时2.040s
i=(i+)%maxn; // 用时4.538s
考虑到codeblocks本身的误差,我单单除去这条语句,将代码其余部分在codeblocks下的运行,依旧5次取平均,时间为:0.015s。
因此,算入误差可以发现,前两条语句最快,第三条也不错,第四条较慢,最后一条用了3倍的时间。故而我的代码中采用了第一行的写法,建议大家尽量采用前三行的写法。
下面给出代码:
// 假设储存的信息类型是int // 栈
class Stack
{
static const int maxn = ;
int S[maxn],L;
public:
Stack(): L() {}
void in(int x) { S[L++]=x; }
int out() { return S[--L]; }
int size() { return L; }
}; // 队列
class Queue
{
static const int maxn = ;
int Q[maxn],i,j;
public:
Queue(): i(), j() {}
void in(int x) { Q[j++]=x; }
int out() { return Q[i++]; }
int size() { return j-i; }
}; // 循环队列
class CycleQueue
{
static const int maxn = ;
int Q[maxn],i,j;
void add(int &k) { k=(k==maxn-)?:(k+); }
public:
CycleQueue(): i(), j() {}
void in(int x) { Q[j]=x; add(j); }
int out() { int x=Q[i]; add(i); return x; }
int size() { return (j>i)?(j-i):(j+maxn-i); } // 此处提醒,循环队列元素个数应在0~maxn-1之间,不可达到maxn
};
最新文章
- Python为8bit深度图像应用color map
- 一般处理程序如何获取session值
- Effective Java
- Java API ——Scanner类
- sublime 安装 Terminal 使用 cmder
- lightoj 1026 无向图 求桥
- 使用iftop网络流量监控
- git flow 的使用
- PHP下用正则表达式分割preg_split、替换reg_replace、匹配preg_match_all等出现乱码的解决方法
- MYSQL数据库常用操作命令
- Python:Day29 信号量、条件变量
- python将目录切换为脚本所在目录
- 一不小心发现了个Asp.Net Bug
- C# dmp debug, can't load pdb file
- mongodb基础学习2-基本CRUD
- MySql基本学习知识点:
- 初识Qt鼠标、键盘事件及定时器和随机数
- WebDriver获得表格里所有单元格的文本
- 《JavaWeb从入门到改行》多重外键关系在java中的处理方案
- java.lang.ClassFormatError: Extra bytes at the end of class file