数组实现的循环队列

队列是一种常见的数据结构,是一个特殊的有序表,起插入操作都在表的一端进行,而删除操作都在表的另外一端进行,所以队列也称先进先出(FIFO)表。可以基于链表实现也可以基于数组实现。我们现在讲基于数组实现,队列的结构如下:

[cpp]
struct Queue {
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
};
[/cpp]

基于数组实现的线性队列很好实现,但这种顺序存储表示存在缺陷,很显然,随着时间的推移,队列逐渐右移。这意味着队列尾下标最终等于MAX_QUEUE_SIZE – 1,说明队列已满,此时需要把整个队列向左移动,使得第一个元素再次位于queue[0],切front = -1,同时还要重新计算rear,使其处在正确的位置上。数组的移动开销很大,特别是当队列中包含大量元素时。

如果将数组queue[MAX_QUEUE_SIZE ]看成是循环的,那么我得到一种更有效的存储表示。这就是循环队列了。

由于必须班长下标front和rear能够循环移动,所以实现循环队列的插入和删除操作要稍微困难些,通常利用模运算可以达到此目的,在插入操作是,队尾下标的循环移动实现语句为:

rear  = (rear + 1)%MAX_QUEUE_SIZE ;

注意在插入时,首先循环移动rear,然后将元素存入队列queue[rear],类似的,在删除过程中,首先用下面语句循环移动front:

front= (front+ 1)%MAX_QUEUE_SIZE ;

然后再删除元素。

下面我们给出c++的实现:

[cpp]
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>

/*
* 功能:数组实现的循环队列,C++实现,供学习
*/

using namespace std;

template <typename T>
class CircleQueue {
private:
T *queue; /* 存储用的数组 */
int capacity; /* 存放个数 */
int front ; /* 指向队首 */
int rear; /* 指向队尾 */
public:
CircleQueue( int a ); /* 无参构造 */
CircleQueue(); /*有参构造 */
~CircleQueue(); /* 析构 */
bool isEmpty(); /* 判断空 */

int getSize(); /* 返回个数 */

bool push( T a ); /* 入队 */

T pop(); /* 出队 */

};

template<typename T>
CircleQueue<T>::CircleQueue( int a ) : front ( 0 ),
rear( 0 ), capacity( a ), queue( NULL )
{
queue = new T[capacity];
}
template<typename T>
CircleQueue<T>::CircleQueue() : CircleQueue( 10 )
{
};
template<typename T>
CircleQueue<T>::~CircleQueue()
{
delete[] queue;
}
template<typename T>
bool CircleQueue<T>::isEmpty()
{
if ( front == rear )
return(true);
else
return(false);
}
template<typename T>
int CircleQueue<T>::getSize()
{
return( (rear – front + capacity) % capacity);
}
template<typename T>
bool CircleQueue<T>::push( T a )
{
if ( (rear + 1) % capacity == front )
{
cout<<"queue is full"<<endl;
return(false);
}

queue[rear] = a;
rear = (rear + 1) % capacity;
return(true);
}
template<typename T>
T CircleQueue<T>::pop()
{
if ( rear == front)
{
cout<<"queue is empty"<<endl;
return NULL;
}

T elem;
elem = queue[front];
front = (front + 1) % capacity;
return elem;
}

int main()
{
CircleQueue<string> queue( 6 );
queue.push( "one" );
queue.push( "two" );
queue.push( "three" );
queue.push( "four" );
queue.push( "five" );
queue.push( "six" );//报满
cout << "队列长度" << queue.getSize() << endl;
while ( !queue.isEmpty() )
{
cout << queue.pop() << endl;
}
getchar();
return(0);
}
[/cpp]

运行输出:

queue is full
队列长度5
one
two
three
four
five

十步学习法(二)

接着上篇文章十步学习法(一)我们来讲述十步学习法的剩下七到十步的内容。接下来四个步骤会在你的学习计划所定义的各个模块中循环往复。步骤七到十的目标是通过“学习–实践–掌握–教授”(LDLT)的方式真正领会知识。你从掌握恰到好处可以开始的基础知识开始,然后通过操作来学习,同时也通过自我探索收集问题,之后,你掌握了足够多的有用的知识。最后,你能将自己学到的教给他人,以此来弥补自己在学习过程中的不足,同时通过深入思考巩固知识。

第七步:开始学习,浅尝辄止

学习过程切忌犯的两种错误,一是在知之不多的情况下就盲目开始,行动太快。二是在行动之前准备太多,行动太晚。你要在这二者之间取得平衡。就是你掌握的知识足以让你开始学习,但又不会多到让你无力探索,这样学习效果最佳。快速学习一定的基础知识立刻开始实际操作。好像你在玩一个拼装玩具,拿到东西后,我们先看一遍说明,然后就会动手拼装了,但是用不了多久你还得重新仔细的阅读说明。

第八步:动手操作,边玩边学

在这一步,重要的就是要动手去实践去操作,学习编程语言更是要写代码。然后编译运行,修改调试。在这个过程中,你的大脑会自然的产生各种问题,也会遇到各种问题:它是如何工作的?是如何运行的?如果我这么做会发生什么?我将如何解决这个问题?等等。这个写问题将引导你走向正在重要的方向。当回过头寻找问题的答案时,不只是这些问题等到解答,而且你记得的东西比你学习的东西要多得多,因为你所学到的都是对你很重要的 东西。下面就是写个小项目来测试这一步的效果。把暂时还没答案的问题记录下来,你在下一步中会有机会找出这些问题的答案。

第九步:全面掌握,学以致用

这一步的目标就是让你找回好奇心驱动的学习,在第八步中,你通过动手操作发现了一些尚未解决的问题,现在是时候来回答这些问题了,在这一步中,你要利用先前收集到的所有资料,进行深入学习。仔细查找相关问题的内容,阅读文字、观看视频、与他人交流都是必要的手段。这个能让你沉浸在学习资料中,尽可能的汲取知识。不要害怕回头再去操作,付出更多,因为这不仅能让你找到问题的答案,也能让你学习的新的东西,给自己足够多的时间去深入理解自己的主题。不是说广度是深度的衍生物嘛。不过要记住,你依然没有必要把所有收集到的资料去不仔细看一遍。你只需要关注当前的所学相关的内容。

第十步:乐为人师,融会贯通

大多数人都不敢为人师,我曾经也是。当你在思考自己知道的东西是否值得教给别人的时候,很容易陷入自我怀疑之中,但是如果你想深入的掌握一门学问。相对这门学问做到融会贯通,那么你必须要做到“好为人师”。除此之外别无他法。

在这一步中,你要走出自己的舒适区,将自己所学到的知识教给别人。要想确定你确实掌握了某些知识,这是唯一的办法;同时,在你将自己所学介绍给他人是,这也是查漏补缺的好方法,在这一过程中,你要切实剖析并理解自己所学的知识,将其内化到自己的思想;同时,你也要用能够让他人理解的方式精心组织这些信息。你可以有多种方式将自己所学教给他人,你可以写博客,这是大多数人的选择,也可以制作视频。还可以与自己的好友探讨,重点在于你要花时间将自己学到的东西从大脑中提取出来,让别人理解明白。

最后的思考

学会自我教育需要奉献精神和辛勤的工作,但是你也能从中收获无比丰厚的回报,“十步学习法”并不是一个神奇的公式,能够让你瞬间变得聪明伶俐,但这种方法可以将学习过程更为结构化,而不是漫无目标的一头扎进浩淼的知识海洋。

如果此方法中的有些步骤对你不起作用,或者你觉得某些形式玩去没有必要,完全可以弃之不理。这些步骤并不重要,这是学习过程的背后的理念才是真正重要的。重点是你要开发出一套适合自己的自学体系,一套你可以持续不断的加以运用而获得丰硕的成果的方法体系。