一、介绍

用一组地址连续的存储单元依次存放从队列头到队列尾的元素叫做顺序队列。

二、顺序队列的实际应用

排队的时候，先买完东西的可以先走，后来的只需要排在队伍的后面，这就是顺序队列的实际应用

同时，也体现出队列的特点：先进先出

三、实现

#ifndef _SEQ_QUEUE_H_
#define _SEQ_QUEUE_H_

typedef int elem_type;

typedef struct SEQ_QUEUE
{


int head;
int tail;
int total;
int len;
elem_type *data;

}QUEUE;


QUEUE *init_SEQ_QUEUE(elem_type size);

bool destory(QUEUE *p);


bool is_empty(QUEUE *p);

bool is_full(QUEUE *p);

bool push(QUEUE *p,elem_type e);//尾删

bool pop(QUEUE *p,elem_type *e);//头出

int get_length(QUEUE *p);

bool clear(QUEUE *p);

#endif

  1 #include"SEQ_QUEUE.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 
  5 
  6 QUEUE *init_SEQ_QUEUE(elem_type size)
  7 {
  8     QUEUE *p = (QUEUE *)malloc(sizeof(QUEUE) * 1);
  9     if (p == NULL)
 10     {
 11         return false;
 12     }
 13 
 14     p->data  = (elem_type *)malloc(sizeof(elem_type) * size);
 15 
 16     p->head = 0;
 17     p->tail = 0;
 18     p->len = 0;
 19     p->total = size;
 20 
 21     return p;
 22 }
 23 
 24 bool destory(QUEUE *p)
 25 {
 26     if (p == NULL)
 27     {
 28         return false;
 29     }
 30 
 31     free(p->data);
 32     free(p);
 33 
 34     return true;
 35 }
 36 
 37 
 38 bool is_empty(QUEUE *p)
 39 {
 40     if (p == NULL)
 41     {
 42         return false;    
 43     }
 44     
 45     return p->len == 0;
 46 }
 47 
 48 bool is_full(QUEUE *p)
 49 {
 50     if (p == NULL)
 51     {
 52         return true;
 53     }
 54 
 55     return p->len == p->total ;
 56 }
 57 
 58 bool push(QUEUE *p,int e)//尾删
 59 {
 60     if (p == NULL)
 61     {
 62         return false;
 63     }
 64 
 65     p->data[p->tail] = e;
 66     p->tail++;
 67     p->len++;
 68     p->tail = p->tail%p->total;
 69     return true;
 70 }
 71 bool pop(QUEUE *p,int *e)//头出
 72 {
 73     if (p == NULL)
 74     {
 75         return  false;
 76     }
 77 
 78     p->data[p->head] = *e;
 79     p->head ++;
 80     p->len --;
 81     p->head = p->head % p->total;
 82 
 83     return true; 
 84 
 85 }
 86 int get_length(QUEUE *p)
 87 {
 88     return p->total;
 89 }
 90 
 91 bool clear(QUEUE *p)
 92 {
 93     if (p == NULL)
 94     {
 95         return false;
 96     }
 97 
 98     p->len = 0;
 99 
100     return true;
101 }

主要实现的功能：

QUEUE *init_SEQ_QUEUE(elem_type size)//队列的初始化

bool destory(QUEUE *p)//队列的销毁

bool is_empty(QUEUE *p)//队列的判空

bool is_full(QUEUE *p)//队列的判满

bool push(QUEUE *p,elem_type e);//尾删

bool pop(QUEUE *p,elem_type *e);//头出

int get_length(QUEUE *p)//求队列的长度

bool clear(QUEUE *p)//清除队列

四、队列的经典例题


	
用两个栈实现队列
	
	

	
用两个队列实现栈
	
 

 

 

问题描述 :

目的：使用C++模板设计顺序队列的抽象数据类型（ADT）。并在此基础上，使用顺序队列ADT的基本操作，设计并实现简单应用的算法设计。

内容：

（1）请参照顺序栈的ADT模板，设计顺序队列的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的顺序栈ADT原型文件，自行设计顺序队列的ADT。）

 

（2）ADT的简单应用：使用该ADT设计并实现若干应用顺序队列的算法设计。

 

应用1：要求设计一个算法，使用顺序队列，设计并实现打印输出杨辉三角形前N行元素的算法。

参考函数原型：

template<class ElemType>

void YangHuiTriangle(SqQueue<ElemType> &Q, int N);

 

顺序队列的ADT原型如下所示：

 

const int MAXLISTSIZE = 100;

 

template<class ElemType>

class SqQueue{

   private:

      ElemType *elem;   // 存储空间基址

      int front;   // 队头指针

      int rear;   // 队尾指针

      int maxSize;        // 允许的最大存储容量(以sizeof(ElemType)为单位

   public:

      //初始化顺序队列

      SqQueue(int ms = 20);

      //删除顺序队列

      ~SqQueue(){QueueDestroy();}

      //将顺序队列置为空

      bool QueueClear( );

      //设置顺序栈的长度

      //bool SetListLength(int len);

      //判断顺序队列是否为空

      bool QueueisEmpty() const{ return front == rear; }

      //判断顺序队列是否为满

      bool QueueFull() const;

      //用e返回队头元素

      bool GetFront(ElemType &e);

      //入队

      bool enQueue(const ElemType &e);

      //出队

      bool deQueue(ElemType &e);

      //销毁顺序队列

      bool QueueDestroy(); 

      //顺序队列最大存储空间加倍

      bool DoubleSpace();

};

输入说明 :

第一行：杨辉三角形的行数

输出说明 :

杨辉三角形（左对齐）

输入范例 :


8


输出范例 :


1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1


解题代码：

// queue.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <sstream>
#include <stack>
#include <map>
#include <ctime>
#include <set>
using namespace std;
int main()
{
    int n,last=0;
    int i, j;
    cin >> n;
    queue<int> num;
    num.push(1);
	for (i = 2; i <= n; i++)
	{
		num.push(1);
		for (j = 1; j <= i - 2; j++)
		{
			last = num.front();
			cout << last << " ";
			num.pop();
			num.push(last + num.front());
		}
		last = num.front();
		num.pop();
		cout << last;
		num.push(1);
		cout << endl;
	}
	while (!num.empty())
	{
		last = num.front();
		cout << last;
		if (num.size() != 1)
			cout << " ";
		else
			cout << endl;
		num.pop();
	}
    return 0;
}



 

顺序队列：先进先出的原则

定义front（队头）和rear（队尾），在队列中起到数组下标的作用。



计算队列长度：（rear - front + size）% size

判断队列是否队满 ：（rear + 1） %size == front

头文件





主函数



函数文件








使用顺序队列实现杨氏三角

队列
  队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
  队列中的数据元素称为队列元素。队列中没有元素时，称为空队列。队列只允许在一端插入，另一端删除，所以队列是一种先进先出的线性表。
1. 顺序队列
  顺序队列存储模式：一维数组。

  建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，连续的存储单元依次存放队列中的元素。然后设置队头指针(front)和队尾指针(rear)进行管理，队头指针指向第一个元素，队尾指针指向队尾元素的下一个位置。

  当队头指针和队尾指针相等时，队列为空。

  入队操作：将新元素插入rear所指位置，rear加1。

  出队操作：删去front所指的元素，front加1后返回被删元素。

具体如下图：



  由上图可知，随着插入和删除操作，队列元素个数不断变化，队列所占存储空间也在为顺序队列结构多分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外，队列无法再插入新元素，但这时往往有大量可用空间未被占用。
  顺序队列中的溢出现象：

1）、“下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。

2）、“真上溢”现象：当队列满时，继续往队列中插入元素，从而使数组越界产生程序代码崩坏。

3）、“假上溢”现象：入队和出队操作，头尾指针不断增加，致使被删元素的空间永远无法重新利用。所以，当队列中元素个数远远小于向量空间的规模，或队尾指针已超越向量空间而不能插入元素的现象称为“假上溢现象”。
2. 循环队列
  循环队列是无论插入或删除元素，一旦队头指针(front)或队尾指针(rear)增1时超出了所分配的队列空间，就让队头指针和队尾指针(rear)指向该连续空间的起始位置。此时，俩指针的值从**(MaxSize-1)变为0**,可以取余运算front%MaxSize和rear%MaeSize来实现。

  一般情况下，队尾指针指向的值为空。

  规定循环队列中至多能有MaxSize-1个队列元素（为了区分满队列和空队列），即当循环队列中只剩下一个空存储单元时，队列满。即循环队列为满条件：(rear+1)%MaxSize=front。

循环队列中空队列条件:front=rear。

  循环队列就是收尾相接的圆环的抽象。可以简单防止“假上溢”现象，充分利用向量空间，但队列大小是固定的。
  例1：有一个用数组 C[1…m]表示的环形队列，m 为数组的长度。假设 f 为队头元素在数组中的位置，r 为队尾元素的后一位置(按顺时针方向)。若队列非空，则计算队列中元素个数的公式应为？答案：（m+r-f） mod m

释：r-f是长度，为防止出现负数m，所以取余m。
3. 深度优先遍历和广度优先遍历
  例1：需要借助于一个队列来实现DFS算法(错)。

DFS是图的深度优先遍历算法。例如，图中A节点与B，C节点相连，B节点与D节点相连。从图的顶端A开始，依次访问B，D，C就是图的深度优先遍历。在访问节点D的时候需要保持B的兄弟节点C，需要用到栈。

  DFS：深度优先遍历，先进后出，借助栈实现。

  BFS：广度优先遍历，先进先出，借助队列实现。