Queue
在C++中只要#include<queue>即可使用队列类,其中在面试或笔试中常用的成员函数如下(按照最常用到不常用的顺序)
1. push
2. pop
3. size
4. empty
5. front
6. back
接下来逐一举例说明:
1. push
队列中由于是先进先出,push即在队尾插入一个元素,如:
1 queueq;2 q.push("Hello World!");3 q.push("China");4 cout< <
可以输出:Hello World!
2. pop
将队列中最靠前位置的元素拿掉,是没有返回值的void函数。如:
1 queueq;2 q.push("Hello World!");3 q.push("China");4 q.pop();5 cout< <
可以输出:China
原因是Hello World!已经被除掉了。
3. size
返回队列中元素的个数,返回值类型为unsigned int。如:
queueq;cout< <
输出两行,分别为0和2,即队列中元素的个数。
4. empty
判断队列是否为空的,如果为空则返回true。如:
1 queueq;2 cout< <
输出为两行,分别是1和0。因为一开始队列是空的,后来插入了两个元素。
5. front
返回值为队列中的第一个元素,也就是最早、最先进入队列的元素。注意这里只是返回最早进入的元素,并没有把它剔除出队列。如:
1 queueq;2 q.push("Hello World!");3 q.push("China");4 cout< <
输出值为两行,分别是Hello World!和China。只有在使用了pop以后,队列中的最早进入元素才会被剔除。
6. back
返回队列中最后一个元素,也就是最晚进去的元素。如:
1 queueq;2 q.push("Hello World!");3 q.push("China");4 cout< <
输出值为China,因为它是最后进去的。这里back仅仅是返回最后一个元素,也并没有将该元素从队列剔除掉。
其他的方法不是很常用,就不再研究了。
接下来我们使用链表,自己将queue类写出来,将其所有方法都实现。代码都是自己写的,最后随便写了点main函数小测一下,没有发现问题,如果有不足还望能指正。如下:
#include#include using namespace std;template struct Node{ T value; Node *next; Node (){next = NULL;}}; template class MyQueue{private: unsigned int num; Node *first; Node *last; public: MyQueue(); ~MyQueue(); unsigned int size(); void push(T element); void pop(); bool empty(); T back(); T front();};template MyQueue ::MyQueue(){ num = 0; first = NULL; last = NULL;}template MyQueue ::~MyQueue(){ while(!empty()){ pop(); }}template unsigned int MyQueue ::size(){ return num;}template bool MyQueue ::empty(){ return (0==num);}template void MyQueue ::push(T element){ Node *temp = new Node ; temp->next = NULL; temp->value = element; if (0 == this->num){ first = temp; last = temp; }else{ last->next = temp; last = temp; } (this->num)++;}template void MyQueue ::pop(){ if (0==this->num){ cout<<"No elements in the queue!"< num){ delete first; first = NULL; last = NULL; this->num = 0; }else{ Node *temp = first; first = first->next; delete temp; (this->num)--; }}template T MyQueue ::back(){ if (0==this->num){ cout<<"No elements in the queue!"< value;}template T MyQueue ::front(){ if(0== this->num){ cout<<"No elements in the queue!"< value;}int main(){ MyQueue q; q.push("Hello world"); q.push("China"); cout< <
Stack
题目:两个数组,长度相同,都为n,两个数组分别为inseq和outseq,求出如果以inseq为入栈顺序,那么outseq可不可能是它的一个出栈顺序,可能则返回true
样例:
inseq = {1,2,3,4,5} outseq={5,4,3,2,1} 返回true;
inseq = {1,2,3,4,5} outseq={4,3,2,1,5},返回true;
inseq = {1,2,3,4,5} outseq={2,3,5,1,4},返回false。
解题思路:模拟整个过程,挨个把inseq的数据放入栈中。直到栈顶元素和出栈序列outseq所指的元素相同,则一直出栈,并将outseq指针后移,直到栈顶元素和outseq指针所指的元素不一样了,则又开始进栈。每次循环中,要么进栈,要么出栈,总要有一个动作在执行,如果既没出栈也没进栈,一定出了什么问题,直接跳出循环,最后进行判断。代码如下:
#include#include using namespace std;bool islegal(int *inseq, int *outseq, int n){ if(n==0) return true; if(n==1) return inseq[0]==outseq[0]; stack st; int i=0,j=0; bool flag = false; //用于确定每一个最外层while循环中有操作在执行,没有操作可以执行,则必然有违反的情况 while(j