用织梦做网站都需要用什么,设计开发流程,名师工作室网站建设现状调查,外贸网站建设开发队列的概念
队列#xff0c;符合先进先出特点的一种数据结构#xff0c;是一种特殊的线性表#xff0c;但它不像线性表一样可以任意插入和删除操作#xff0c;而是只允许在表的一端插入#xff0c;也就是在队列的尾部进行插入#xff1b;只允许在表的另一端进行删除符合先进先出特点的一种数据结构是一种特殊的线性表但它不像线性表一样可以任意插入和删除操作而是只允许在表的一端插入也就是在队列的尾部进行插入只允许在表的另一端进行删除也就是在队列的头部进行删除。
以下的实现是顺序队列存储空间在内存上是连续的队列
队列的实现
队列的结构定义
#define MAX_SIZE 20 //队列的最大容量
typedef int DateElem; typedef struct _Queue
{DateElem date[MAX_SIZE];int head; //头指针int tail; //尾指针
}squeue;
队列的初始化
void InitQueue(squeue* sq)
{if (!sq) return;sq-head 0;sq-tail 0;
}
销毁清空队列
和队列的初始化有点类似哈哈。
bool DestoryQueue(squeue* sq)
{if (!sq) return false;sq-head 0;sq-tail 0;return true;
}判满
bool IsFull(squeue* sq)
{if(!sq) return false; //防御性编程if (sq-tail MAX_SIZE ) //每入队一个元素sq-tail入队了MAX_SIZE个元素刚好sq-tail等于MAX_SIZE{return true;}else{return false;}
}
判空
可以从 队列的初始状态空队列和 入队后再出队 中找到判空的条件。
bool IsEmpty(squeue* sq)
{if (!sq) return false;if (sq-head sq-tail) //两个指针之间没有元素{return true;}else{return false;}
}
入队
bool EnterQueue(squeue* sq, DateElem e)
{if (IsFull(sq)){cout 无法插入元素e队列已满。 endl;return false;}sq-date[sq-tail ] e; //尾部插入sq-tail; //尾指针指向下一块未被使用区域 return true;
}
出队
出队的方式有两种一种是乾坤大挪移每出队一个元素都要将后面所有的元素往前挪十分浪费时间。另一种是舍弃空间来达到快速出队元素。
第一种
bool PopQueue(squeue* sq, DateElem* date)
{if (!sq || IsEmpty(sq)) return false;*date sq-date[sq-head]; //返回出队的元素for (int i sq-head 1; i sq-tail; i){sq-date[i - 1] sq-date[i]; //从第二个结点开始将第二个结点赋值给第一个结点……}sq-tail--; //别忘记return true;
}
第二种
bool PopQueue2(squeue* sq,DateElem *date)
{if (!sq || IsEmpty(sq)) return false;//不是无限制的出队if (sq-head MAX_SIZE) return false;*date sq-date[sq-head];sq-head;return true;
}
本来头指针一直指向下标为 0 的地方但是这种出队方式会导致头指针一直向后移动出现“假溢出”明明队列还有空间存储可是却无法插入元素了。如下图 造成了空间的浪费不过在比赛时为了通过题目这点空间浪费无所谓使用顺序队列非常容易构建。 打印队列
和链表的打印一样。
bool PrintQueue(squeue* sq)
{if (!sq) return false;for (int i sq-head; i sq-tail; i){printf(%d , sq-date[i]);}return true;
}
获取队首元素
int GetHeadElem(squeue* sq)
{if (!sq || IsEmpty(sq)) return 0; //指针存在 或者 队列不为空return sq-date[sq-head]; //在队头不出队的清况下返回队首元素
}
获取队列长度
int GetLength(squeue* sq)
{if (!sq) return 0;return sq-tail - sq-head; //最开始为空队列sq-tail - sq-head 为 0 依次类推得到长度
}
主函数
我已经写好了测试的方法可以尽情调试看看代码的正确性。
int main(void)
{squeue* sq new squeue;DateElem* s new DateElem;InitQueue(sq);DateElem e 0;int choose -1;while (choose ! 0){cout 1.入队 endl 2.出队 endl 3.打印队列 endl 4.获取队首元素 endl 5.获取队列长度 endl 6.销毁队列 endl 0.退出 endl;cin choose;switch (choose){case 1:cout 请输入要入队的元素;cin e;if (EnterQueue(sq, e)){cout 入队成功 endl;}else{cout 入队失败 endl;}break;case 2:if (PopQueue(sq, s)){cout 出队的元素是 *s endl;}else{cout 出队失败 endl;}break;case 3:cout 队列中的元素是;PrintQueue(sq);cout endl;break;case 4:cout 队首元素是 GetHeadElem(sq) endl;break;case 5:cout 队列的长度是 GetLength(sq) endl;break;case 6:if (DestoryQueue(sq)){cout 队列已销毁 endl;}else{cout 队列不存在 endl;}break;case 0:cout 退出成功 endl;break;default:cout 输入非法 endl;break;}}return 0;
}
好了再见
