队列和循环队列的实现
队列
[blockquote]
定义:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(head)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
[/blockquote]
按照队列的定义,结合内存地址的理解,初始化队列的时候,准备head
和rear
指针分别指向头和尾。Push操作,只需要改变rear
指针;PopLeft操作只需要改变head
。由于是线性表结构,所以在封装GetSize的时候,不能简单的用rear-head
,因为每次申请的结点都是内存中随机的区域,正因如此,这种队列链(线性表实现)更具有灵活性。
代码实现
#include<iostream> using namespace std; typedef int DataType; struct Queue{ DataType data; Queue *next; }; void InitQueue(Queue *&head,Queue *&rear){ head = new Queue; head->next = NULL; rear = head; } void Push(Queue *&rear,DataType data){ Queue *q = new Queue; q->data = data; q->next = NULL; rear->next = q; rear = q; } void PopLeft(Queue *&head,DataType &data){ //data 是弹出的数据 if(!head->next) //判断是否是空的队列 return ; else{ Queue *q = head->next; //保存No 1的队列结点 delete head; head = q; data = q->data; } } int GetSize(Queue *head){ if(!head->next) //head->next是NULL的时候,队列为空 return 0; else{ //迭代计算长度 int length= 0; Queue *tem = head->next ; while(tem){ ++length; tem = tem->next; } return length; } } void DeleteQueue(Queue *&head){ Queue *p = head; //当前要删除的结点 Queue *q = p->next; while(q){ delete p; p = q; q = p->next; } delete p; } int main(){ Queue *head=NULL,*rear = NULL; DataType data ; //用来保存弹出的元素 InitQueue(head,rear); Push(rear,-1); Push(rear,-2); Push(rear,100); Push(rear,-100); cout<<"长度是:"<<GetSize(head)<<endl; PopLeft(head,data); cout<<"弹出元素:"<<data<<endl; PopLeft(head,data); cout<<"弹出元素:"<<data<<endl; DeleteQueue(head); //cout<<"长度是:"<<GetSize(head)<<endl; 无法执行,说明DeleQueue成功 return 0; }
循环队列
[blockquote]
定义:为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
[/blockquote]
虽然可以克服假溢出,但是循环队列长度有限,并且内存中不可能有类似循环的物理结构。我们需要用逻辑来实现这种循环队列。
如果采用一段连续地址进行实现,可以使用数组,实现简单,不做实现;这里是采用使用的连续指针进行实现。
需要准备base_front
指针来记录最初的头位置。需要count
和size
分别存放队列大小和队列中的数据个数。循环的逻辑实现就是:在特定条件下,front 和 rear 都要重新指向save_front ,形成一个环。
#include<iostream> using namespace std; const int SIZE = 3; //默认队列大小 template <class T> //为了适应各种数据类型,使用类模板 class CirQueue { private: T *front; T *rear; T *save_front; int size; int count ; //记录有多少个元素 public: CirQueue(){ count = 0; size = SIZE; front = new T [size]; save_front = rear = front; } CirQueue(int s){ count = 0; size = s; front = new T [size]; save_front = rear = front; } int GetSize(){ return size; } void Push(T data){ if(count==size) return ; //队列已满 *rear = data; ++count; if (count==size)//只剩最后一个位置 rear = save_front; //完成逻辑上的循环 else ++rear; } void PopLeft(T &data){ if(!count) //如果没有元素 return; --count; data = *front; if(front-save_front==size-1) front = save_front; else ++front; } void Delete(){ delete [] save_front; cout<<"删除成功"<<endl; } }; int main(){ CirQueue <int> tem; int data; for(int i=0;i<4;++i) tem.Push(i+1); //1 2 3 for(int i=0;i<tem.GetSize();++i){ tem.PopLeft(data); cout<<data<<endl; } tem.Delete(); return 0; }
[blockquote]
欢迎进一步交流本博文相关内容: 安科开发地址 : http://www.cnblogs.com/AsuraDong/ CSDN地址 : http://blog.csdn.net/asuradong 也可以致信进行交流 : [email protected] 欢迎转载 , 但请指明出处 : )
[/blockquote]