首页 / C++ / 《数据结构》C++代码 栈与队列
《数据结构》C++代码 栈与队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《数据结构》C++代码 栈与队列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1403字，纯文字阅读大概需要3分钟。
内容图文
线性表中，先进先出的叫队列，先进后出的叫栈。队列常用于BFS，而在函数递归层数过高时，需要手动实现递归过程，这时候便需要写一个“手动栈”。
有时候，我们会有大量数据频繁出入队列，但同时存在其内的元素却不多，此时需要写“循环队列”。其代码并不难，但里面下标递增的语句值得斟酌一下。
k=(k+1)%maxn;
这句话用到了取模运算%，是非常浪费时间的。若能避免使用%，则可以大大提高代码运行速度。我做了一个测试，把下面五种语句写法分别运行5×10^8次，在我的机器上用codeblocks10.05各运行5次，取平均数，时间如下所示：
1 i=(i==maxn-1)?0:(i+1); // 用时1.582s2if(i==maxn-1) i=0; else ++i; // 用时1.588s3 ++i; if(i==maxn) i=0; // 用时1.605s4 ++i; i=(i==maxn)?0:i; // 用时2.040s5 i=(i+1)%maxn; // 用时4.538s
考虑到codeblocks本身的误差，我单单除去这条语句，将代码其余部分在codeblocks下的运行，依旧5次取平均，时间为：0.015s。
因此，算入误差可以发现，前两条语句最快，第三条也不错，第四条较慢，最后一条用了3倍的时间。故而我的代码中采用了第一行的写法，建议大家尽量采用前三行的写法。
下面给出代码：
1
//
假设储存的信息类型是int
2
3
//
栈
4
class
Stack
5
{
6
static
const
int maxn = 10000;
7int S[maxn],L;
8public:
9 Stack(): L(0) {}
10voidin(int x) { S[L++]=x; }
11intout() { return S[--L]; }
12int size() { return L; }
13};
1415// 队列16class Queue
17{
18staticconstint maxn = 10000;
19int Q[maxn],i,j;
20public:
21 Queue(): i(0), j(0) {}
22voidin(int x) { Q[j++]=x; }
23intout() { return Q[i++]; }
24int size() { return j-i; }
25};
2627// 循环队列28class CycleQueue
29{
30staticconstint maxn = 10000;
31int Q[maxn],i,j;
32void add(int &k) { k=(k==maxn-1)?0:(k+1); }
33public:
34 CycleQueue(): i(0), j(0) {}
35voidin(int x) { Q[j]=x; add(j); }
36intout() { int x=Q[i]; add(i); return x; }
37int size() { return (j>i)?(j-i):(j+maxn-i); }
38 };
原文：http://www.cnblogs.com/icedream61/p/4142466.html
内容总结
以上是互联网集市为您收集整理的《数据结构》C++代码 栈与队列全部内容，希望文章能够帮你解决《数据结构》C++代码 栈与队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。