首页 > 代码库 > 数据结构2-队列
数据结构2-队列
队列是可以在它的两端可以进行操作,一端入队列,一端出队列。
队列中用两个标志来表示队列头和队列尾,front和rear,front指向队列头元素的前一个位置,rear指向队列尾的那个元素。
用C++实现如下:
//定义一个队列#include<iostream>using namespace std;const int MAX=5;class queue{private: int a[MAX]; int front,rear;public: queue() { front=0; rear=0; } ~queue(){} bool empty()const; bool full()const; void InQueue(int); //入队列 void OutOfQueue(); //出队列 void GetFront()const; //得到队列头元素};bool queue::empty()const{ return front==rear;}bool queue::full()const{ return rear==MAX-1;}void queue::InQueue(int x){ if(full()) { cout<<"full!"<<endl; } else { rear++; a[rear]=x; }}void queue::OutOfQueue(){ if(empty()) { cout<<"empty!"<<endl; } else { front++; }}void queue::GetFront()const{ if(empty()) { cout<<"empty!"<<endl; } else { cout<<a[front+1]; }}int main(){ queue a; a.GetFront(); a.InQueue(1); a.InQueue(2); a.InQueue(3); a.InQueue(4); a.InQueue(5); a.GetFront(); a.OutOfQueue(); a.GetFront(); return 0;}
这里只实现了queue最基本的几个功能。由于这种顺序队列,当插入的数据达到MAX-1时,队列就会溢出,为了防止溢出,我们可以用循环队列。
循环队列,即尾元素的下一个元素为头元素。即rear=MAX-1时,当再有一个元素入队列的时候,rear=0。
实现代码如下:
//实现一个循环队列#include<iostream>using namespace std;const int MAX=3;class xhqueue{private: int a[MAX+1]; int front,rear; int count;public: xhqueue() { front=0; rear=0; count=0; } ~xhqueue(){} bool empty()const; bool full()const; void inq(int); void outq(); void getfront()const;};bool xhqueue::empty()const{ return count==0;}bool xhqueue::full()const{ return count==MAX+1;}void xhqueue::inq(int x){ if(full()) { cout<<"full!"<<endl; } else { rear=(rear+1)%(MAX+1); a[rear]=x; count++; }}void xhqueue::outq(){ if(empty()) { cout<<"empty!"<<endl; } else { front=(front+1)%(MAX+1); count--; }}void xhqueue::getfront()const{ if(empty()) { cout<<"empty!"<<endl; } else { int j=(front+1)%(MAX+1); cout<<a[j]; }}int main(){ xhqueue a; if(a.empty()) { cout<<"empty!\n"; } a.getfront(); a.inq(1); a.getfront(); cout<<endl; a.inq(2); a.getfront(); cout<<endl; a.inq(3); a.inq(4); a.getfront(); cout<<endl; a.outq(); a.getfront(); cout<<endl; a.inq(5); a.inq(6); cout<<endl; return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。