循环队列的存储结构定义

Loops are among the most basic and powerful of programming concepts. A loop in a computer program is an instruction that repeats until a specified condition is reached. In a loop structure, the loop asks a question. If the answer requires action, it is executed. The same question is asked again and again until no further action is required. Each time the question is asked is called an iteration. 

 循环是最基本，最强大的编程概念之一。 计算机程序中的循环是一条重复指令，直到达到指定条件为止。 在循环结构中，循环会提出一个问题。 如果答案需要采取措施，则将其执行。 一次又一次询问相同的问题，直到不需要采取进一步的措施为止。 每次提出问题都称为迭代。 

A computer programmer who needs to use the same lines of code many times in a program can use a loop to save time.

 需要在程序中多次使用同一行代码的计算机程序员可以使用循环来节省时间。 

Just about every programming language includes the concept of a loop. High-level programs accommodate several types of loops. C, C++, and C# are all high-level computer programs and have the capacity to use several types of loops.

 几乎每种编程语言都包含循环的概念。 高级程序可容纳多种类型的循环。 C ， C ++和C＃都是高级计算机程序，并且具有使用几种类型的循环的能力。 
 
 循环类型 (  Types of Loops  )
A for loop is a loop that runs for a preset number of times.
 for循环是运行预设次数的循环。 
A while loop is a loop that is repeated as long as an expression is true. An expression is a statement that has a value.
 while循环是只要表达式为真就重复的循环。 表达式是具有值的语句。 
A do while loop or repeat until loop repeats until an expression becomes false.
 do while循环或重复直到循环重复直到表达式变为假为止。 
An infinite or endless loop is a loop that repeats indefinitely because it has no terminating condition, the exit condition is never met or the loop is instructed to start over from the beginning. Although it is possible for a programmer to intentionally use an infinite loop, they are often mistakes made by new programmers.
 无限循环或无限循环是无限重复的循环，因为它没有终止条件，从不满足退出条件，或者指示循环从头开始。 尽管程序员可能有意使用无限循环，但是它们经常是新程序员犯的错误。 
A nested loop appears inside any other for, while or do while loop.
 嵌套循环出现在for ， while或do while循环的任何其他循环中。 

A goto statement can create a loop by jumping backward to a label, although this is generally discouraged as a bad programming practice. For some complex code, it allows a jump to a common exit point that simplifies the code.

 goto语句可以通过跳回标签来创建循环，尽管通常不建议这样做，因为这是一种不良的编程习惯。 对于某些复杂的代码，它允许跳转到简化代码的公共出口点。 
 
 循环控制语句 (  Loop Control Statements  )

A statement that alters the execution of a loop from its designated sequence is a loop control statement. C#, for example, provides two loop control statements.

 从指定的顺序改变循环执行的语句是循环控制语句。 例如，C＃提供了两个循环控制语句。 
A break statement inside a loop terminates the loop immediately.
 循环内的break语句会立即终止循环。 
A continue statement jumps to the next iteration of the loop, skipping any code in between.
 Continue语句跳转到循环的下一个迭代，跳过两者之间的任何代码。 
 
 计算机程序设计的基本结构 (  Basic Structures of Computer Programming  )

Loop, selection, and sequence are the three basic structures of computer programming. These three logic structures are used in combination to form algorithms for solving any logic problem. This process is called structured programming.

 循环，选择和顺序是计算机编程的三个基本结构。 这三个逻辑结构结合使用以形成用于解决任何逻辑问题的算法。 此过程称为结构化编程。 
翻译自: https://www.thoughtco.com/definition-of-loop-958105
循环队列的存储结构定义

五、队列的定义
定义：队列（queue）：队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入操作的一端称为队尾，允许删除操作的一端称为队头。
队列与现实生活中的排队机制很像，排在队头的出队，而想入队则只能从队尾开始。
===============================================================================
队列：
顺序存储结构：（循环队列）

#define N 10
typedef int data_t;
typedef struct 
{
	data_t data[N]；    //数据存储
	int length；        //不能用，注意想想方式       
}Node;

===============================================================================
六、循环队列
线性表有顺序存储和链式存储两种结构，队列作为特殊的线性表，自然也有顺序队列和链式队列两种形式。
但是，队列的顺序存储却有很大的缺陷。如果我们要建立元素个数为n的队列，则需要建立一个数组长度不小于n的数组，数组下标为0的为队头，当最大下标的为队尾。若有元素要入队，则只需将其存储在第n+1个位置即可。
而若想出队，则删除了下标为0的元素后，所有在其后的元素都需要向前移动一格，即保持下标为0的元素为队头。但这样做显然浪费了大量时间。
解决该问题的方法就是不再限制下标为0的元素为队头，每次出队后，队头自动变成当前数组下标最小的元素即可。这样就无需所有元素向前移动。
但是，若如此做，则会造成大量的已出队的元素的存储空间浪费。而且，若此时入队元素已经大于n，则我们需要更大的存储空间才行，但队头位置有大量空间未利用，空间浪费严重。
解决以上问题的方法就是如果后面满了，则我们就从头开始，也就是将队列做成头尾相接的循环。我们把这种头尾相接的顺序存储结构的队列称为循环队列。
这样，我们就需要两个指示其队头（front）和队尾（rear）的下标变量。
typedef int data_t;
typedef struct
{
	data_t data[MAXSIZE];
	int front；   头位置下标
	int rear；    尾位置下标
}SqQueue;

循环队列的操作：
1、创建空的循环队列（CreateSqQueue）
2、判断是否为空队列（SqQueueEmpty）
3、判断是否为满队列（SqQueueFull）
4、新数据元素入队（EnQueue）
5、数据元素出去（OutQueue）
6、求队长（SqQueueLenght）
7、遍历循环队列（VisitSqQueue）

当front==rear时，此时队头和队尾重合，则该队列为空队列；当(rear+1)%QueueSize==front时，此时队尾的下个位置就是队头，则该队列为满队列。注意rear的位置不是队尾元素的位置，而是队尾元素的下一个位置，即当队列满时，队列中还有一个空闲存储空间，但我们规定该状态下就是满队列。
那么，定义好队列的的队头和队尾位置，我们来考虑怎样计算队列长度。
当rear>front时，表示队尾在队头右边，此时队列长度为rear-front；当rear<front时，表示队尾在队友左边，此时计算队列长度应分成两部分，即rear一部分，QueueSize-front一部分，总体长度为rear-front+QueueSize。
通用计算队列长度的公式是
length=(rear-front+QueueSize)%QueueSize
1、判断队是否为空EmptyQueue
//代码见附录
2、判断队是否为满FullQueue
//代码见附录
3、入队操作EnQueue
//代码见附录
4、出队操作DeQueue
//代码见附录
从循环队列的特性我们可以看出，循环队列虽然操作较为简单，但是由于队列定长，因此会出现数据溢出问题。这时我们需要考虑使用队列的链式存储结构。
===============================================================================
七、队列的链式存储结构及实现
队列的链式存储结构本质上是从单链表演化而来的。将单链表改造成链式队列，如果将头结点做为队头，最后一个节点做为队尾，则该队列的出队操作方便，而入队操作较慢；反之，如果将头结点做为队尾，最后一个节点做为队头，则该队列的入队操作方便，而出队操作较慢。
那么，能否将单链表稍加改进，使得该链式队列的入队操作和出队操作一样方便呢？
答案是可以的，只需要改进头结点。将“头结点存储一个next指针”改为“头结点存储两个指针front和rear”，front指针指向队头，rear指针指向队尾。这样我们进行出队/入队操作时，只需要访问这两个指针就能快速地找到队头/队尾。
1、队列的链式存储结构定义
将单链表的头结点稍加改造
typedef int data_t;
typedef struct node_t//定义单链表
{
	data_t data;
	struct node_t *next;
	
} linknode_t, *linklist_t;
typedef struct//定义链式队列
{
	linklist_t front, rear;
} linkqueue_t;

链式队列的操作：
申请的头指针为lq，lq->front == lq->rear
1、创建空链式队列（CreateLinkQueue）
2、判断是否为空（LinkQueueEmpty）    rear == front ！= NULL
3、清空链式队列（ClearLinkQueue）
4、求链式队列的长度（LinkQueueLength）
5、新数据元素入队（EnLinkQueue）  rear指向最后元素
6、数据元素出队（DeLinkQueue）
7、遍历整个链式队列数据元素（PrintLinkQueue）

2、判定链式队列是否为空
由于单链表的属性，链式队列几乎不会出现“队列已满”的情况，因此不考虑判定链式队列是否已满的操作。
判定链式队列是否为空，只需要判定队列的front指针是否为空即可。
//代码见附录
3、队列的链式存储结构——入队操作
入队操作其实就是在链表尾部插入节点。新来的数据节点附在当前rear节点之后，并将rear节点指向该节点即可。
//代码见附录
4、队列的链式存储结构——出队操作
出队操作就是将链表的头结点的后继节点出队，并将其之后的节点设置为头结点的后继节点。若链表除头结点外仅剩一个元素，则需将rear指向头结点。
//代码见附录

对于循环队列和链式队列的比较，二者从时间复杂度上来说都是O(1)，不过链式队列需要花费额外的申请节点的时间，而且链式队列删除节点也需要一些时间。从空间上来说，循环队列有固定长度，就意味着循环队列有其存储上限，因此也就存在元素溢出以及空间浪费等问题，而链式队列则不存在这些问题。
总体来说，若可以大致确定元素个数的情况下，推荐使用循环队列；若无法事先预知元素个数，则应使用链式队列。
===============================================================================
======================================================================

队列只允许在队尾插入，在队头删除

循环队列防止假溢出现象

顺序存储结构用数组实现
#include <iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define MAXSIZE 6
typedef int ElemType;
typedef int Status;

/* 定义顺序存储结构的循环队列：SqQueue(循环队列防止假溢出)
 * 思路：
 * 1、用数组实现
 * 2、头指针front指向队头元素的下标
 * 3、尾指针rear指向队尾元素下一个位置的下标
 */
typedef struct
{
	ElemType data[MAXSIZE];
	int front;
	int rear;
}SqQueue;

/* 循环队列的初始化：InitQueue
 * 思路：
 * 1、头指针和尾指针指向的下标位置均为0
 */
Status InitQueue(SqQueue *Q)
{
	Q->front = 0;
	Q->rear = 0;
	return 0;
}

/* 循环队列求队列长度：Queuelength
 * 思路：
 * 1、队列满的条件是：(rear+1)%MAXSIZE==front
 * 2、规定：数组中只有一个空闲单元时3，规定已满
 * 3、当rear>front时,长度为：rear-front，
 * 4、当rear<front时,长度为：rear-front+MAXSIZE
 * 5、将3和4结合：长度为：(rear-front+MAXSIZE)%MAXSIZE
 */
int Queuelength(SqQueue Q)
{
	return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

/* 循环队列的入队，只在队尾入队：EnQueue，入队元素为e
 * 思路：
 * 1、判断队列是否已满,队列满的条件是：(rear+1)%MAXSIZE==front
 * 2、在队尾的下一个元素入队，即data[rear]=e;
 * 3、将尾指针后移一位i，若在最后择移动到数组头部，即：rear=(rear+1)%MAXSIZE
 */
Status EnQueue(SqQueue *Q, ElemType e)
{
	if ((Q->rear + 1) % MAXSIZE == Q->front)
	{
		cout << "队列已满" << endl;
		return ERROR;
	}
	Q->data[Q->rear] = e;
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return OK;
}

/* 循环队列的出队：只在队头出队：DeQueue,返回元素为e
 * 思路：
 * 1、判断队列是否空，空的条件是front==rear
 * 2、将队头元素返回e：e=data[front];
 * 3、将头指针front后移一位，若到数组最后则移到数组头部，即：front=(front+1)%MAXSIZE
 */
Status DeQueue(SqQueue *Q, ElemType *e)
{
	if (Q->rear == Q->front)
	{
		cout << "队列已空" << endl;
		return ERROR;
	}
	*e = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZE;
	return OK;
}

/* 输出队列函数：PrinftQueue
 * 思路：
 * 1、判断队列是否为空
 * 2、由于数组中始终有一个空闲单元，所以front！=rear
 * 3、当rear>front时，按下标从front到rear-1输出
 * 4、当rear<front时，先输出front到MAXSIZE-1，再输出0到rear-1
 */
Status PrinftQueue(SqQueue *Q)
{
	int i;
	if (Q->rear == Q->front)
	{
		cout << "队列已空" << endl;
		return ERROR;
	}
	if (Q->rear > Q->front)
	{
		for (i = Q->front; i < Q->rear; i++)
		{
			cout << Q->data[i] << ' ';
		}
	}
	else
	{
		for (i = Q->front; i < MAXSIZE; i++)
		{
			cout << Q->data[i] << ' ';
		}
		for (i = 0; i < Q->rear ; i++)
		{
			cout << Q->data[i] << ' ';
		}
	}
	return OK;
}

int main()
{
	SqQueue Q;
	InitQueue(&Q);
	int i,j,k,l,m,n;

	cout << "队列最大长度：" << MAXSIZE-1 << endl;

	cout << "输入入队元素个数：";
	cin >> i;
	cout << "依次入队元素：";
	for (j = 0; j < i; j++)
	{
		cin >> k;
		EnQueue(&Q, k);
	}

	cout << "输出队列：";
	PrinftQueue(&Q);
	cout << endl;

	int length;
	cout << "输出队列长度：";
	length = Queuelength(Q);
	cout << length << endl;

	cout << "输入出队元素个数：";
	cin >> l;
	cout << "输出出队元素：";
	for (j = 0; j < l; j++)
	{
		DeQueue(&Q, &m);
		cout << m << ' ';
	}
	cout << endl;

	cout << "输出队列：";
	PrinftQueue(&Q);
	cout << endl;

	cout << "输出队列长度：";
	length = Queuelength(Q);
	cout << length << endl;

	cout << "输入入队元素个数：";
	cin >> n;
	cout << "依次入队元素：";
	for (j = 0; j < n; j++)
	{
		cin >> k;
		EnQueue(&Q, k);
	}

	cout << "输出队列：";
	PrinftQueue(&Q);
	cout << endl;

	cout << "输出队列长度：";
	length = Queuelength(Q);
	cout << length << endl;


	return 0;


}

结果为：

/**************************
循环队列的顺序存储结构

功能代码包含：
1）循环队列的顺序存储结构的数据结构定义
2）初始化循环队列
3）往循环队列中插入元素--入队
4）删除循环队列中的元素--出队
5）求循环队列的实际长度

注意：代码不进行debug，只实现基本功能

Author:tmw
date:2018-3-9
**************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXSIZE 100 //定义队列大小
#define error -65530;

/**循环队列的顺序存储结构的数据结构定义**/
typedef struct SqQueue
{
    int data[MAXSIZE];
    int front;  /**头指针**/
    int rear;   /**尾指针**/
}SqQueue;

/**初始化循环队列**/
void initSqQueue( SqQueue *Q )
{
    Q->front = 0;
    Q->rear = 0;
}

/**往循环队列中插入元素e--入队**/
bool EnQueue( SqQueue *Q, int e )
{
    /**入队前提：队列不能满**/
    if( ( Q->rear+1 ) % MAXSIZE == Q->front )
        return false;

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXSIZE;

    return true;
}

/**出队操作，并返回出队元素**/
int DeQueue( SqQueue *Q )
{
    /**出队前提条件：队列非空**/
    if( Q->front == Q->rear )
        return error;

    int e = Q->data[Q->front];
    Q->front = ( Q->front+1 ) % MAXSIZE;

    return e;
}

/**求循环队列的实际长度**/
int len_of_SqQueue( SqQueue *Q )
{
    return ( Q->rear + MAXSIZE - Q->front ) % MAXSIZE;
}

梦想还是要有的，万一实现了呢~~~ヾ(◍°∇°◍)ﾉﾞ