| 数据结构：队列（顺序队列）&链式队列 | 您所在的位置：网站首页 › 顺序循环队列的结构体定义 › 数据结构：队列（顺序队列）&链式队列 |
数据结构：队列（顺序队列）&链式队列
|
队列
一、什么是队列？
1.是一种特殊的线性表 2.只允许在一端进行插入数据，在另一端进行删除数据 二、队头&队尾&入队列&出队列1.队头：进行删除数据的一端 2.队尾：进行插入数据的一端 3.入队列：在队尾处进行插入数据的操作 4.出队列：在队尾处进行删除数据的操作 三、队列的特性First In First Out—–FIFO,即就是先进先出 先进先出就是指先进来的先出去，就像我们吃饭排队一样，谁早排谁就可以早买到饭且可以先走，其实排队就是一种队列 顺序队列 一、什么是顺序队列顺序队列是队列的一种，只是说队列的存在形式是队列中的元素是连续的，就像数组 二、顺序队列的实现方式 1.队头不动，队尾动循环队列是首尾相接的顺序存储队列，顾名思义循环队列就是队列的内存可以循环使用 二、为什么会有循环队列？在顺序队列中，出现了假溢出问题，那循环队列就是为了假溢出问题的，假溢出造成了内存浪费，循环队列可以使得内存得到有效的利用 三、循环队列的实现方式？给定两个指针，分别标记队头和队尾，标记队头的指针是front,标记队尾的是rear 1.空队列 开始时，front是队头指针，rear是队尾指针，空队列时front和rear指向同一位置 ps：循环队列是空队列时，front和rear都指向队列的起始位置，随着元素的插入和删除，rear会跟着向后或者向前移动，而front是不会动的 1.少使用一个循环队列中的存储空间就是说呢，在存储元素时，少用一个存储单元，那队列空的时候，front和rear指向同一位置，那随着插入元素，rear向后移动，最后一个存储单元不使用，所以队列满的时候，rear的下一个位置就是front指向的元素
ps：M是循环队列的空间大小，即就是M标记了循环队列中最多可以存储几个元素 本来rear+1就是front指向的位置，那为什么还要跟队列的空间大小取模呢？是因为当rear指向最后一个位置的时候，下标为7，那rear+1=8，而循环队列中没有下标为8的元素，如图可知，必须对相加的结果取模 2.给一个标记flag，默认flag为false就是说呢，给一个标记flag ，默认此标记为false，当插入元素就把标记flag改为true，当删除元素就把标记改为false ps：当队列为空的时候，front和rear指向同一位置，当队列为满的时候，front和rear也是指向同一位置 队列为空时的判断条件：front==rear&&flag==false 队列为满时的判断条件：front==rear&&flag==true 3.给一个计数器count插入一个元素时count++，删除一个元素时count - - 队列为空时的判断条件：count==0 队列为满时的判断条件：count=M 或者（count>0 && rear==front） ps：M是循环队列的空间大小 这三种方法中，第三种方法最简单方便 五、循环队列的删除和插入 1.插入front和rear开始时都位于下标为0的位置，插入一个元素，插入的位置=rear指向的位置，插入完成后，front不动，rear向后移动一个位置，但是要注意边界情况，当rear移动到等于N的位置时，此时需要把rear归位，即就是让rear=0，从而开始下一轮的移动，每插入一个元素count加1 void Push(const T&data)//给队列中插入元素 { if (_count == N) return; _array[_rear++] = data; //_rear = (_rear + 1) % N; //不用此种方式是因为取模的效率不高 //而且使用此种方式的话，每插入一个元素都需要取模 if (_rear == N) _rear = 0; _count++; } 2.删除删除元素时，只需要把front向后移动一个位置就好，随着元素的删除，当front==N时，注意把front置为0，每删除一个元素，count也需要减去1 void Pop()//删除元素 { if (Empty()) return; ++_front;//删除元素时，只需要把队头的标记向后移动一个位置就好 if (_front == N) _front = 0;//删除元素时注意边界问题 _count--; } 源代码 #include using namespace std; template//N标记的是队列中的元素个数，默认为8 class Queue { public: Queue() :_front(0) , _rear(0) ,_count(0) {} void Push(const T&data)//给队列中插入元素 { if (_count == N) return; _array[_rear++] = data; //_rear = (_rear + 1) % N; //不用此种方式是因为取模的效率不高 //而且使用此种方式的话，每插入一个元素都需要取模 if (_rear == N) _rear = 0; _count++; } void Pop()//删除元素 { if (Empty()) return; ++_front;//删除元素时，只需要把队头的标记向后移动一个位置就好 if (_front == N) _front = 0;//删除元素时注意边界问题 _count--; } T&Front()//获得队头元素 { return _array[_front]; } const T&Front()const { return _array[_front]; } T&Back()//获得队尾元素 { return _array[(_rear - 1 + N)%N]; } const T&Back()const { return _array[(_rear - 1 + N)%N]; } bool Empty()const//判断队列是否为空 { return _count == 0; } size_t Size() { return _count;//_count标记的是队列中元素的个数 } private: int _front;//用来标记队头 int _rear;//用来标记队尾 T _array[N];//数组是用来存储顺序队列中的元素的 size_t _count;//是用来标记队列是否满的 //count=0时队列为空，count=N表示队列已满 }; void TestQueue() { Queue q; q.Push(1); q.Push(2); q.Push(3); q.Push(4); q.Push(5); cout |
2.队列中有元素 在插入元素时，rear会随着元素的插入而向后移动，front不会动，如果删除元素的话，那rear会向前移动，front也还是不会动 
队列为空时的判断条件：front==rear时 ，队列为空队列 队列为满时的判断条件：（rear+1）%M == front时，队列为满队列【本文地址】
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |