C/C++顺序与链式队列详解(附代码)(一)

简介: C/C++顺序与链式队列详解(附代码)

前言

  队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表**。队列是一种先进先出(First Input First Ouput),的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。**

既然是线性表,那么就可以分为顺序存储结构和链式存储结构。
队列存储结构的实现有以下两种方式:
顺序队列:在顺序表的基础上实现的队列结构;
链队列:在链表的基础上实现的队列结构;

本文将在链队列的基础上实现队列子系统,题目如下:
1.设计一个选择式菜单。
2.设计一个整型数据元素的链队列。
3.编写入队、出队、读队首元素、显示队列中全部元素的程序。
4.编写求解报数问题的应用程序,要求给出他们的出列顺序。
注:所谓报数问题,设n个人站成一排,从左到右的编号分别为1~n,从左到右报数“1,2,3,1,2,3”,数到“1”和“2”的人出列,数到“3”的人立即站到队伍的最右端。报数过程反复进行,直到n个人都出列为止。
如:n=10时,初始序列为1 2 3 4 5 6 7 8 9 10,
出列顺序为1 2 4 5 7 8 10 3 9 6。

一、顺序队列

  由于顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且先进先出的要求,我们还需要定义两个指针(top 和 rear)分别用于指向顺序队列中的队头元素和队尾元素,如图所示

1:顺序队列入队

  由于顺序队列初始状态没有存储任何元素,因此 top 指针和 rear 指针重合,且由于顺序队列底层实现靠的是数组,因此 top 和 rear 实际上是两个变量,它的值分别是队头元素(首先出队数据的位置)和队尾(最后出队数据的后一个位置)元素所在数组位置的下标。
  在上图的基础上,当有数据元素进队列时,对应的实现操作是将其存储在指针 rear 指向的数组位置,然后 rear+1;当需要队头元素出队时,仅需做 top+1 操作。
例如,在上图的基础上将 {1,2,3,4} 用顺序队列存储的实现操作如下图所示:

在上图的基础上,我们知道出队其实就是top指针指向下一个数据,如下图所示:

  当然,如果接着插入数据5,6,那么假设这个数组只能容纳5个数据,那么数据6就溢出了,但是明明数组下标0,1,2的空间都还没存放元素,因此由于头铁而直接把数据插入在数组后面造成的溢出称为“假溢出”,因为我们可以把数据6放在a[0]位置,这样就解决了假溢出的问题,那么应该如何做到才可以解决这个问题呢,没错,让数组尾和数组头连接,也就是后面满了,再从头开始。这样的顺序存储结构称为循环队列。

紧接着入队a6,将它放置再下标为0处,此时rear指针指向下标为1处,如下图所示:

但是发现如果我们继续填充数据,那么就会出现下图的情况:

  但是rear=front的条件是队列为空时设定的,那么我们可以修改队列为满时的条件,我们可以保留一个元素空间,也就是说,队列满的时候,数组中还有一个空闲单元,如下图:

  由于rear可能比front大,也可能比front小,所以尽管他们只相差一个位置时就是满的情况,但也可能是相差整整一圈。所以若队列的最大尺寸为Size,那么队列满的条件就是(rear+1)%Size==front,(取模"%"的目的就是为了整合rear和front大小为一个问题)。比如上左图,(4+1)%5==0成立,如上右图,(1+1)%5==2成立,因此队列满,如果不符合这个条件,那么队列不满(可以自己实验)。
  另外,当rear>front时,此时队列长度为rear-front,但是如果rear<front,队列长度应该分为两段,一段是Size-front(据图可以计算处下标2到下标5是3个元素),另一段是rear-0(rear下标减去0下标,就可以知道rear到0有多少个元素了,如下图可以得出是1个),因此通用的计算队列长度的公式为:
(rear-front+Size)&Size。

  介绍完了基本概念以及基本写法,接下来就是如何写出顺序队列的代码。
  我们可以将顺序队列的代码分为几个实现:
  1:队列初始化  2:队列插入数据  3:队列删除数据  4:队列求长  
  5:返回队列头元素  6:显示队列全部元素

2:顺序队列出队

  出队较为简单,这是由于出队的一定是队首指向的元素,因此只需将队首指向的元素指向下一个要出队的元素即可。直接看代码中的DeQueue()函数即可

3:完整代码

#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 5
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;
int status = 0;//全局状态标志位 如果执行了销毁队列操作则置1
typedef struct queue
{
  ElemType data[MAXSIZE];
  int front;
  int rear;
}Queue;
void menu(void)
{
  cout << "********************" << endl;
  cout << "*1 ……入队        *" << endl;
  cout << "*2 ……出队        *" << endl;
  cout << "*3 ……读队首元素  *" << endl;
  cout << "*4 ……显示        *" << endl;
  cout << "*5 ……销毁队列    *" << endl;
  cout << "*0 ……退出        *" << endl;
  cout << "********************" << endl;
}
Queue* InitQueue(Queue* q) //队列初始化
{
  q->front = 0;
  q->rear = 0;
  return q;
}
Status DestoryQueue(Queue* q)//销毁队列
{
  if (q)
  {
    free(q);
    cout << "删除成功" << endl;
    status = 1;
    return OK;
  }
  else
  {
    cout << "队列未创建" << endl;
    return ERROR;
  }
}
Queue* ClearQueue(Queue* q) //清空队列
{
  if (q)
  {
    free(q);
    cout << "清空成功" << endl;
    Queue* head = (Queue*)malloc(sizeof(Queue));
    return head;
  }
  else
  {
    cout << "未存在队列" << endl;
    cout << "请先创建一个队列" << endl;
    exit(0);
  }
}
Status GetHead(const Queue* q, ElemType* e)//返回队列头
{
  if ((q) && (q->front != q->rear))//队列非空
  {
    cout << "队头元素是" << q->data[q->front] << endl;
    *e = q->data[q->front];
    return OK;
  }
  else
  {
    cout << "队列为空或队列不存在" << endl;
    return ERROR;
  }
}
Status EndQueue(Queue* q, ElemType e)//队尾插入元素 最多能插入MAXSIZE-1个数据
{
  if ((q->rear + 1) % MAXSIZE == q->front)//队列满
  {
    cout << "队列已满" << endl;
    return ERROR;
  }
  q->data[q->rear] = e;
  q->rear = (q->rear + 1) % MAXSIZE;//指针后移
  cout << "插入成功" << endl;
  return OK;
}
Status DeQueue(Queue* q, ElemType* e)//删除队头元素
{
  if (q && (q->front == q->rear))
  {
    cout << "队列为空" << endl;
    return ERROR;
  }
  *e = q->data[q->front];
  cout << "队头元素为" << *e << endl;
  q->front = (q->front + 1) % MAXSIZE; //头指向下一个数据
  return OK;
}
int QueueLength(const Queue q)//获得队列长
{
  return (MAXSIZE - q.front + q.rear) % MAXSIZE;
  cout << "长度为" << (MAXSIZE - q.front + q.rear) % MAXSIZE << endl;
}
void ShowQueue(Queue q)//显示所有数据
{
  if (status==0)//还未执行销毁操作
  {
    int i = 0;
    cout << "长度" << (MAXSIZE - q.front + q.rear) % MAXSIZE << endl;
    while ((q.front) % MAXSIZE != q.rear)
    {
      cout << "第" << i++ << "个数据是" << q.data[q.front++] << endl;
    }
  }
  else
  {
    cout << "队列不存在" << endl;
    exit(-1);
  }
}
int main()
{
  int choose;
  ElemType e;
  menu();
  Queue* head = (Queue*)malloc(sizeof(Queue));
  InitQueue(head);
  while (1)
  {
    cout << "请选择功能" << endl;
    cin >> choose;
    switch (choose)
    {
    case 1:
    {
      cout << "输入要入队的数据" << endl;
      cin >> e;
      EndQueue(head, e);
      break;
    }
    case 2:
    {
      DeQueue(head, &e);
      break;
    }
    case 3:
    {
      GetHead(head, &e);
      break;
    }
    case 4:
    {
      ShowQueue(*head);
      break;
    }
    case 5:
    {
      DestoryQueue(head);
      break;
    }
    case 0:
    {
      cout << "感谢使用,bye!" << endl;
      exit(0);
      break;
    }
    default:
      break;
    }
  }
}

4:运行结果


相关文章
|
存储 C语言 C++
C/C++顺序与链式队列详解(附代码)(二)
C/C++顺序与链式队列详解(附代码)
437 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
738 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
410 16
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
435 0
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
642 0
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
1190 6
|
编译器 C++
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
|
存储 编译器 C++
类和对象(上)(C++)
本篇内容主要讲解了C++中类的相关知识,包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符(public、protected、private)的使用规则,以及class与struct的区别。同时分析了类实例化的概念,对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制,解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。