第三篇.
感觉队列和栈是必须的……所以决定加上这两个……
我发现我已经买域名买上隐了……今天又买了个.top……真是智障……
Queue(队列FIFO)和Statk(栈LIFO).
那么为什么要这两个一块讲呢?理由很简单,数据结构小班同志们都学了,基础原理都会了,这两个东西很像,无论是在操作上还是其他别的方面……
而这篇博客主要是详解STL中queue和statk的用法。
首先,回顾一下队列和栈:
(1) 非STL的队列实现方法:
用数组模拟一个队列,两个指针,分别指向队列的头和尾,入队++尾指针,队首出队++头指针;程序如下:
int a[];
int tail=,head=;//tail:队尾指针,head:队首指针
/*队列尾进头出 FIFO(First In First Out)*/
void pop(){
head++;//头指针++,相当于弹出(删除)队首元素
}
void push(x){
tail++;
a[tail]=x;//在队尾添加元素
//a[tail++]=x;
}
int front(){
return a[head];//返回队首元素
}
int back(){
return a[tail];//返回队尾元素
}
其实这个样子,有可能因为头指针和尾指针超过了这个用来模拟队列的数组的大小,可能爆掉,所以,读者自行加个判断就好了(其实还有如果队列为空了再pop就会出错了(都是使用者的事),一本通上写的很明白了)
(2) 非STL的栈实现方法:
用数组模拟一个栈,一个头指针,指向栈顶,入栈++头指针,出栈—头指针;程序如下:
int a[];
int t=;//栈顶指针
/*栈顶进栈顶出(好像腔肠动物:D),LIFO(Last In First Out)*/
void push(int x){
t++; //栈顶指针++
a[t]=x;//放进栈顶元素
//a[t++]=x;
}
void pop(){
t--;//栈顶元素--,相当于删掉栈顶元素
}
void top(){
return a[t];//返回栈顶指针指向的元素(栈顶元素)
}
OK,回顾完之前学的,现在让我们来看一下STL中队列和栈是怎么实现的:
(一) 队列
1.普通队列:
(1) 首先,通常,头文件是不可少的: #include<queue>
#include<queue>
queue<int> que;
(2) 定义完了,入队出队操作(还记的刚刚上面非STL方式的例程中的函数名嘛):
que.push(a);//将变量a放到队列que的队尾,a入队。
que.pop();//弹出队列que的队首元素(删掉队首元素),队首出队
怎么样?就两句话,简不简单?
(3) 其他操作:
que.front();//将会返回队列que的队首元素
que.back();//将会返回队列que的队尾元素
que.size();//返回队列que的大小(目前队列有多少元素)
que.empty();//如果队列为空,则返回1,不为空则返回0
是不是很方便?
2.优先队列:(优先队列其实就是普通队列加了个排序。操作上是跟普通队列一样的,不过队列中的元素是有序的)
3.双端队列:(普通队列是跟只能在某一端进行入队另一端进行出队操作的(也就是队首和队尾),而双端队列可在队列两段都可进行入队出队操作)
(二) 栈
1. 同上,头文件: #include<stack>
2. 同上,入栈出栈操作:
3. 同上,其他操作: