精华内容
下载资源
问答
  • 顺序存储数组)和链式存储(链表),此博文描述的是数组的实现(后续更新链表实现)  代码实现 初始化队列:初始化一个size长度的队列队列的值都为0 判断队列是否已满:队列满,不可插入队列 判断队列是否为空...
  • 数据结构之数组存储循环队列(C++实现) 本实验程序用于验证循环队列的基本操作算法,包括:入队、出队、取队头元素、取队尾元素、判队空或满、显示队列元素等。为了用户了解循环队列的循环特性,基本操作中,...

    数据结构之数组存储循环队列(C++实现)

      本实验程序用于验证循环队列的基本操作算法,包括:入队、出队、取队头元素、取队尾元素、判队空或满、显示队列元素等。为了用户了解循环队列的循环特性,在基本操作中,增加了显示队尾或对头指针内容的功能。

    附循环队列逻辑结构图


        循环队列的定义及操作(CirQueue.h)如下:

    #pragma once
    template<class T>
    class CirQueue
    {
    private:
    	T *base;                             //储存空间基址
    	int front;                           //对头指针
    	int rear;                            //队尾指针
    	int queuesize;                        //队列容量
    public:
    	CirQueue(int m);                     //构造空队列
    	~CirQueue();                         //析构函数,释放链队各节点存储空间
    	void EnQueue(T x);
    	T DeQueue();
    	T GetHead();
    	T GetLast();
    	int QueueEmpty();
    	int QueueFull();
    	void ClearQueue();
    	void Pointer();
    	void QueueTranverse();
    };
    
    template<class T>
    inline CirQueue<T>::CirQueue(int m)
    {
    	base = new T[m];
    	if (base == NULL)
    	{
    		cout << "队列创建失败,退出!";
    		exit(1);
    	}
    	front = rear = 0;
    	queuesize = m;
    }
    
    template<class T>
    inline CirQueue<T>::~CirQueue()
    {
    	delete[] base;
    	rear = 0;
    	front = 0;
    	queuesize = 0;
    
    }
    
    template<class T>
    inline void CirQueue<T>::EnQueue(T x)
    {
    	if ((rear + 1) % queuesize == front) throw"上溢,无法入队!";
    	base[rear] = x;
    	rear = (rear + 1) % queuesize;
    }
    
    template<class T>
    inline T CirQueue<T>::DeQueue()
    {
    	T x;
    	if (front == rear) throw"下溢,无法出队!";
    	x = base[front];
    	front = (front + 1) % queuesize;
    	return x;
    }
    
    template<class T>
    inline T CirQueue<T>::GetHead()
    {
    	T x;
    	if (front == rear)throw"队空!";
    	x = base[front];
    	return x;
    }
    
    template<class T>
    inline T CirQueue<T>::GetLast()
    {
    	T x;
    	if (front == rear)throw"队空!";
    	x = base[rear-1];
    	return x;
    }
    
    template<class T>
    inline int CirQueue<T>::QueueEmpty()
    {
    	if (front == rear)
    		return 1;
    	else
    		return 0;
    }
    
    template<class T>
    inline int CirQueue<T>::QueueFull()
    {
    	if ((rear + 1) % queuesize == front)
    		return 1;
    	else
    		return 0;
    }
    
    template<class T>
    inline void CirQueue<T>::ClearQueue()
    {
    	front = rear = 0;
    }
    
    template<class T>
    inline void CirQueue<T>::Pointer()
    {
    	cout << "队首front=" << front << endl;
    	cout << "队尾rare=" << rear << endl;
    
    }
    
    template<class T>
    inline void CirQueue<T>::QueueTranverse()
    {
    	int i = front;
    	while (i != rear)
    	{
    		cout << base[i] << '\t';
    		i = (i + 1) % queuesize;
    	}
    	cout << endl;
    }
    程序结构图如下:

    CirQueue_main主调程序


    // CirQueue.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    
    
    #include<iostream>
    #include<process.h>
    #include<stdio.h>
    #include"CirQueue.h"
    using namespace std;
    char pause;
    int main()
    {
    	int e;
    	CirQueue<int>q(10);
    	system("cls");
    	int choice;
    	do
    	{
    		cout << "1-元素入队\n";
    		cout << "2-元素出队\n";
    		cout << "3-取队头元素\n";
    		cout << "4-取队尾元素\n";
    		cout << "5-置队空\n";
    		cout << "6-测队空\n";
    		cout << "7-测队满\n";
    		cout << "8-显示首尾位置\n";
    		cout << "9-输出队元素\n";
    		cout << "10-退出\n";
    		cout <<"Enter Choice:";
    		cin >> choice;
    		switch (choice)
    		{
    		case 1:
    			cout << "请输入要插入的元素值:";
    			cin >> e;
    			cout << endl;
    			q.EnQueue(e);
    			cout << e << "如对成功!" << endl;
    			cin.get(pause);
    			system("pause");
    			break;
    		case 2:
    			try {
    				e = q.DeQueue();
    				cout << "出队元素为:" << e << endl;
    			}
    			catch (char *eer)
    			{
    				cout << eer << endl;
    			}
    			cin.get(pause);
    			system("pause");
    			break;
    		case 3:
    			try {
    				e = q.GetHead();
    				cout << "队头元素为<<e<<endl";
    			}
    			catch (char*eer)
    			{
    				cout << eer << endl;
    			}
    			cin.get(pause);
    			system("pause");
    			break;
    		case 4:
    			try {
    				e = q.GetLast();
    				cout << "队尾元素为<<e<<endl";
    			}
    			catch (char*eer)
    			{
    				cout << eer << endl;
    			}
    			cin.get(pause);
    			system("pause");
    			break;
    		case 5:
    			q.ClearQueue();
    			cin.get(pause);
    			system("pause");
    			break;
    		case 6:
    			if (q.QueueEmpty())
    				cout << "队空!" << endl;
    			else
    				cout << "队不空!" << endl;
    			cin.get(pause);
    			system("pause");
    			break;
    		case 7:
    			if (q.QueueFull())
    				cout << "队满!" << endl;
    			else
    				cout << "队不满!" << endl;
    			cin.get(pause);
    			system("pause");
    			break;
    		case 8:
    			q.Pointer();
    			cin.get(pause);
    			system("pause");
    			break;
    		case 9:
    			q.QueueTranverse();
    			cin.get(pause);
    			system("pause");
    			break;
    		case 10:
    			break;
    		default:
    			cout << "选择不合理!";
    			break;
    		}
    	} while (choice != 10);
    	return 0;
    }
    编译环境:windows 7;VisualStdio2015



    展开全文
  • 数组可为静态数组或动态数组,顺序队列通常必须为循环队列。 注意: 循环队列是解决顺序队列内存空间利用率最大化的一种解决方案。 顺序队列 循环队列 三、队列类型定义 #define QUEUE_ZISE ...

    一、队列

    队列是一种先进先出操作受限的线性表结构。它只允许从队尾插入,也叫入队;只允许从队首删除,也叫出队。

    二、队列分类

    链式队列 —— 用链表实现的队列
    顺序队列 —— 用数组实现的队列。数组可为静态数组或动态数组,顺序队列通常必须为循环队列。

    注意:
    循环队列是解决顺序队列内存空间利用率最大化的一种解决方案。

    顺序队列

    顺序队列

    循环队列

    循环队列

    三、队列类型定义

    #define QUEUE_ZISE				6//队列长度
    
    typedef struct Queue
    {
    	int qFront;//队首
    	int qRear;//队尾
    	int BasicArr[QUEUE_ZISE];//队列数据
    }Queue, * pQueue;
    //Queue  等效于 struct Queue 
    //pQueue 等效于 struct Queue *
    

    四、循环队列初始化

    队首和队尾相等且为零,则已为循环队列初始阿虎。
    如下图所示:
    队列初始化

    //初始化队列
    void InitQueue(pQueue queue)
    {
    	queue->qFront = 0;
    	queue->qRear  = 0;
    
    	printf("队列初始化成功......\r\n");
    	printf("队列总长度 : %d\r\n", (QUEUE_ZISE - 1));
    	printf("队首 : %d\r\n", queue->qFront);
    	printf("队尾 : %d\r\n", queue->qRear);
    }
    

    五、判断队列是否为空

    若队首和队尾相等,则表示队列为空。当队列为空时出队无效。
    如下图所示:
    队列为空

    //队列是否为空
    bool IsEmptyQueue(pQueue queue)
    {
    	if (queue->qFront == queue->qRear)//队首等于队尾
    		return true;
    	else
    		return false;
    }
    

    六、判断队列是否已满

    若队尾下一个数据为队首数据,则说明队列已满,当队列已满时入队无效。

    注意:
    队列真正使用长度为队列长度减一,这使得顺序队列内存空间利用率最大化。

    如下图所示:
    队列已满

    //队列是否为满
    bool IsFullQueue(pQueue queue)
    {
    	//队尾下个数据为队首
    	if (((queue->qRear + 1) % QUEUE_ZISE) == queue->qFront)
    		return true;
    	else
    		return false;
    }
    

    七、循环队列数据入队

    将数据存入对队尾代表的存储空间,然后队尾指向下个存储空间。

    注意:
    1.只允许从队尾入队(队列未满)。
    2.循环队列计算下个入队存储空间为:(队尾 + 1 ) % 队列长度

    如下图所示:
    数据入队

    //入队
    void EnterQueue(pQueue queue, int vale)
    {
    	if (IsFullQueue(queue))
    	{
    		printf("队列已满,入队失败......\r\n");
    		return;
    	}
    
    	//从队尾入队
    	queue->BasicArr[queue->qRear] = vale;//入队数据
    	queue->qRear = (queue->qRear + 1) % QUEUE_ZISE;//队尾移向下个位置
    
    	printf("入队成功!入队值为:%d   ---->    ", vale);
    	printf("队首: %d   队尾: %d\r\n", queue->qFront, queue->qRear);
    }
    

    八、循环队列数据出队

    将队首代表的存储空间数据输出,然后队首指向下一个存储空间。

    注意:
    1.只允许从队首出队(队列非空)。
    2.循环队列计算下个出队存储空间为:(队出 + 1 ) % 队列长度

    如下图所示:
    数据出队

    //出队
    int OutQueue(pQueue queue)
    {
    	int out = 0;
    
    	if (IsEmptyQueue(queue))
    	{
    		printf("队列已空,出队失败......\r\n");
    		return out;
    	}
    
    	out = queue->BasicArr[queue->qFront];//出队值
    	queue->qFront = (queue->qFront + 1) % QUEUE_ZISE;//指向下一个出队值
    
    	printf("出队成功!出队值为:%d   ---->    ", out);
    	printf("队首: %d   队尾: %d\r\n", queue->qFront, queue->qRear);
    
    	return  out;
    }
    

    九、显示队列数据

    输出显示队列中所有数据。从队首开始直到队尾结束的所有数据。

    //显示队列数据
    void ShowQueue(pQueue queue)
    {
    	int cur = 0;
    
    	if (IsEmptyQueue(queue))
    	{
    		printf("队列为空,显示失败......\r\n");
    		return;
    	}
    
    	printf("队列数据: ");
    	cur = queue->qFront;
    	while (cur != queue->qRear)
    	{
    		printf("%d  ", queue->BasicArr[cur]);
    		cur = (cur + 1) % QUEUE_ZISE;
    	}
    	printf("\r\n");
    }
    

    十、获取队列使用空间

    从队首到队尾的所有数据个数为队列使用空间数。

    //队列使用空间
    int CountQueue(pQueue queue)
    {
    	int cur = 0;
    	int len = 0;
    
    	cur = queue->qFront;
    	while (cur != queue->qRear)
    	{
    		len++;
    		cur = (cur + 1) % QUEUE_ZISE;
    	}
    
    	printf("队列使用空间 : %d\r\n", len);
    	return len;
    }
    

    十一、获取队列剩余空间

    队列长度减一,再减去队列使用空间数,就等于列剩余空间 。即:
    队列剩余空间 = 队列长度 - 1 - 队列使用空间

    //队列剩余空间
    int ResidueQueue(pQueue queue)
    {
    	int len = 0;
    	int cur = 0;
    	int res = 0;
    
    	cur = queue->qFront;
    	while (cur != queue->qRear)
    	{
    		len++;
    		cur = (cur + 1) % QUEUE_ZISE;
    	}
    
    	res = QUEUE_ZISE - 1 - len;
    	printf("队列剩余空间 : %d\r\n", res);
    	return res;
    }
    

    十二、代码验证演示

    void main(void)
    {
    	Queue queue;
    
    	InitQueue(&queue);//初始化队列
    	printf("\r\n");
    	
    	EnterQueue(&queue, 10);//入队
    	EnterQueue(&queue, 20);
    	EnterQueue(&queue, 30);
    	EnterQueue(&queue, 40);
    	EnterQueue(&queue, 50);
    	CountQueue(&queue);//队列使用空间
    	ResidueQueue(&queue);//队列剩余空间
    	ShowQueue(&queue);//显示队列数据
    	printf("\r\n");
    
    	OutQueue(&queue);//出队
    	OutQueue(&queue);
    	OutQueue(&queue);
    	CountQueue(&queue);//队列使用空间
    	ResidueQueue(&queue);//队列剩余空间
    	ShowQueue(&queue);//显示队列数据
    	printf("\r\n");
    
    	while (1);
    }
    

    十三、运行结果

    队列初始化成功......
    队列总长度 : 5
    队首 : 0
    队尾 : 0
    
    入队成功!入队值为:10   ---->    队首: 0   队尾: 1
    入队成功!入队值为:20   ---->    队首: 0   队尾: 2
    入队成功!入队值为:30   ---->    队首: 0   队尾: 3
    入队成功!入队值为:40   ---->    队首: 0   队尾: 4
    入队成功!入队值为:50   ---->    队首: 0   队尾: 5
    队列使用空间 : 5
    队列剩余空间 : 0
    队列数据: 10  20  30  40  50
    
    出队成功!出队值为:10   ---->    队首: 1   队尾: 5
    出队成功!出队值为:20   ---->    队首: 2   队尾: 5
    出队成功!出队值为:30   ---->    队首: 3   队尾: 5
    队列使用空间 : 2
    队列剩余空间 : 3
    队列数据: 40  50
    

    运行结果1

    运行结果2

    运行结果3

    运行结果4

    运行结果5

    展开全文
  • 循环队列 (顺序存储)

    2021-10-21 12:23:13
    队列是一种操作受限的线性表。队列只能表的一端进行插入操作另一端进行删除操作。其中,允许插入的一端叫...循环队列是对队列的一种改进,主要是为了解决队尾溢出而实际上数组仍有空余空间这种“假溢出” 问题

    数组链表是最基本的数据结构,栈、队列、树、图等复杂数据结构都是基于数组或链表方式存储



    队列(Queue)特征:

    • 循环队列的顺序存储是基于数组来实现的

    • 队列是一种操作受限的线性表。队列只能在表的一端进行插入操作,在另一端进行删除操作。其中,允许插入的一端叫队尾,允许删除的一端叫队头。【遵守: 先进先出(First In First Out,FIFO) 规则,例如元素A、B、C、D依次入队,则出队顺序也必须是A、B、C、D

    注意咯:很多初学者都容易将 队头 和 队尾 搞混,以为元素是在队头插入在队尾删除。


    循环队列特征:

    • 循环队列是对队列的一种改进,主要是为了解决队尾溢出而实际上数组仍有空余空间这种“假溢出”(如图一)问题

    • 循环队列的rear和front到达队尾端点,能折回数组开始处。相当于将数组首尾相连,想象 成环状(如图二)。

    cd4356



    头指针Front 和 尾指针Rear:

    • 循环队列中,一般头指针front指向队头元素,尾指针rear指向队尾元素的下一个元素;或者 头指针front指向队头元素的下一个元素,尾指针rear指向队尾元素。 这样的目的是满足front == rear判空条件

    cd4356


    循环队列 - 结构体

    #define MAX_SIZE 255 //循环队列的最大容量
    
    typedef struct C_Queue {
    	int data[MAX_SIZE];  //指定循环队列大小
    	int front;       //循环队列头指针
    	int rear;	//循环队列尾指针
    } *Queue;
    
    
    注意:结构体后面的*Queue是指向C_Queue的结构体指针,
    如果不加*,使用结构体指针需要Queue *q这样,
    加了*,使用结构体指针,只需Queue q即可;
    

    循环队列 - 创建

    • 通过malloc()函数动态创建一个循环队列
    Queue queue_create() {
    	Queue q = (Queue)malloc(sizeof(C_Queue)); //给循环队列分配内存空间
    	q->front = q->rear = 0;  //初始状态下,头指针和尾指针 均指向0(下标)
    
    	return q;
    }
    

    循环队列 - 判空

    boolean queue_empty(Queue q) {
    	if (q->front == q->rear) {  //当front和rear相等时,队列为空
    		return TRUE;
    	} else {
    		return FALSE;
    	}
    }
    

    循环队列 - 判满

    • rear 和 front的值相等时(图一和图二),队列可能出现队空或队满两种情况,从而无法判别队满还是队空。

    • 针对这一问题,解决方法有两种:

        1. 定义一个变量size来记录当前队列的元素个数【队尾插入一个元素,size+1; 队头删除一个元素,size-1

        2. 牺牲一个存储单元(如图三),在队尾指针rear+1就能赶上队头指针front时,我们就认为队满了。【即:循环队列最大实际长度 = MAX_SIZE - 1】,这种方法的队满条件是:(q->rear+1)%MAX_SIZE == q->front 【记得%MAX_SIZE取模 ,否则可能会超出数组最大下标】,下面用的就是这种方法。
    cd4356

    boolean queue_full(Queue q) {
    	if ((q->rear + 1) % MAX_SIZE == q->front) {
    		return TRUE;
    	} else {
    		return FALSE;
    	}
    }
    

    循环队列 - 求长度

    • 由图可知:MAX_SIZE = 8,q->rear = 1,q->front = 3,队列长度length = 6

    • 验证一下:(q->rear - q->front + MAX_SIZE) % MAX_SIZE; 是不是可以求队列长度。(length = (1 - 3 + 8) % 8 = 6,没毛病)
      cd4356

    int queue_length(Queue q) {
    	return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
    }
    

    循环队列 - 入队

    • 队尾插入元素,入队前要先判断循环队列是否已满

    • 先将待入队的元素,插入尾指针原本指向的位置

    • 尾指针rear + 1,并%MAX_SIZE取模。【模MAX_SIZE后,当尾指针指向数组下标最大值时,可以让尾指针折回数组开始处

    cd4356

    boolean queue_rear_insert(Queue q, int x) {
    	if (queue_full(q)) { //判断队满
    		printf("队列已满!\n");
    		return FALSE;
    	} else {
    		q->data[q->rear] = x; //先将元素插入尾指针原本指向的位置
    		q->rear = (q->rear + 1) % MAX_SIZE; //尾指针+1
    		return TRUE;
    	}
    }
    

    循环队列 - 出队

    • 队头删除元素,出对前要先判断循环队列是否为空

    • 用x记录,要出队元素的值,作为函数的返回值

    • 头指针front + 1,并%MAX_SIZE取模。【模MAX_SIZE后,当头指针指向数组下标最大值时,可以让头指针折回数组开始处

    cd4356

    int queue_front_delete(Queue q) {
    	int x;
    	if (queue_empty(q)) {
    		printf("队列无元素可删除!\n");
    		return 0;
    	} else {
    		x = q->data[q->front];  //用x记录头指针指向的元素值
    		q->front = (q->front + 1) % MAX_SIZE;  //头指针front + 1,并%MAX_SIZE取模
    		return x;
    	}
    }
    

    循环队列 - 获取队头元素

    int queue_get_front(Queue q) {
    	if (!queue_empty(q)) {
    		return q->data[q->front];
    	}
    	return 0;
    }
    

    循环队列 - 迭代

    • 将循环队列中所有元素出队,并输出
    void queue_items_printf(Queue q) {
    	while (!(q->front == q->rear)) {
    		printf("%d ", q->data[q->front]);  //输出头指针front指向元素的值
    		q->front = (q->front + 1) % MAX_SIZE;  //头指针front + 1
    	}
    }
    

    整个程序代码

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef enum {FALSE, TRUE} boolean;
    
    #define MAX_SIZE 8 //循环队列的最大长度
    
    //结构体
    typedef struct C_Queue {
    	int data[MAX_SIZE];  //指定循环队列大小
    	int front;       //循环队列头指针
    	int rear;	//循环队列尾指针
    } *Queue;
    
    //创建队列
    Queue queue_create() {
    	Queue q = (Queue)malloc(sizeof(C_Queue)); //给循环队列分配内存空间
    	q->front = q->rear = 0;  //初始状态下,头指针和尾指针 均指向0(下标)
    	if (q == NULL) { //内存分配失败
    		return NULL;
    	}
    	return q;
    }
    
    //队列判空
    boolean queue_empty(Queue q) {
    	if (q->front == q->rear) {  //当front和rear相等时,队列为空
    		return TRUE;
    	} else {
    		return FALSE;
    	}
    }
    
    //队列判满
    boolean queue_full(Queue q) {
    	if ((q->rear + 1) % MAX_SIZE == q->front) {
    		return TRUE;
    	} else {
    		return FALSE;
    	}
    }
    
    //队列长度
    int queue_length(Queue q) {
    	return (q->rear - q->front + MAX_SIZE) % MAX_SIZE;
    }
    
    //队尾插入元素
    boolean queue_rear_insert(Queue q, int x) {
    	if (queue_full(q)) {
    		printf("队列已满!\n");
    		return FALSE;
    	} else {
    		q->data[q->rear] = x;
    		q->rear = (q->rear + 1) % MAX_SIZE;
    		return TRUE;
    	}
    }
    
    //队头删除元素
    int queue_front_delete(Queue q) {
    	int x;
    	if (queue_empty(q)) {
    		printf("队列无元素可删除!\n");
    		return 0;
    	} else {
    		x = q->data[q->front];
    		q->front = (q->front + 1) % MAX_SIZE;
    		return x;
    	}
    }
    
    //获取队头元素
    int queue_get_front(Queue q) {
    	if (!queue_empty(q)) {
    		return q->data[q->front];
    	}
    	return 0;
    }
    
    
    //将队列所有元素出队
    void queue_items_printf(Queue q) {
    	while (!(q->front == q->rear)) {
    		printf("%d ", q->data[q->front]);
    		q->front = (q->front + 1) % MAX_SIZE;
    	}
    }
    
    
    int main() {
    	/* 创建一个循环队列 */
    	Queue q = queue_create();
    	int A[8], i;
    
    	if (NULL == q) {
    		printf("队列创建失败!\n");
    		return -1;
    	}
    
    	printf("当前队列长度为:%d\n", queue_length(q));
    
    	printf("输入要入队的元素: ");
    	for (i = 0; i < 8; i++) {
    		scanf("%d", &A[i]);
    	}
    	//将数组中的元素按顺序插入循环队列
    	for (i = 0; i < 8 ; i++) {
    		queue_rear_insert(q, A[i]);
    	}
    	printf("当前队头元素为:%d\n", queue_get_front(q));
    	printf("\n当前队列长度为:%d\n", queue_length(q));
    
    
    	printf("\n队列元素出队顺序:");
    	//将循环队列所有元素出队,并输出
    	queue_items_printf(q);
    	printf("\n当前队列长度为:%d\n", queue_length(q));
    
    	return 0;
    }
    



    循环队列总结:


    1. 循环队列的两个状态

    • 队空状态:q->front = q->rear

    • 队满状态:(q->rear + 1) % MAX_SIZE = q->front


    2. 循环队列的三个操作

    • 求队列长度:length = (q->rear - q->front + MAX_SIZE) % MAX_SIZE

    • 元素 x 入队:q->data[q->rear] = x ;   q->rear = (q->rear + 1) % MAX_SIZE ;

    • 元素 x 出队:x = q->data[q->front] ;   q->front = (q->front + 1) % MAX_SIZE ;



    来几道题目巩固下


    1. 循环队列存储在数组A[0…n]中,则入队时的操作为:__ rear = (rear+1) mod (n+1) __

    • 解析:因为数组下标是从0开始的,所以数组的最大容量为n+1,即循环队列的MAX_SIZE = n+1,入队操作为:(q->rear + 1) % MAX_SIZE = (rear + 1) mod (n + 1) 【mod是%的意思,N mod M = N % M


    2. 已知循环队列的存储空间为数组A[21],front指向队头元素的前一个位置,rear指向队尾元素,假设当前front和rear的值分别为8和3,则该队列的长度为:__ 16 __

    • 解析:length = (q->rear - q->front + MAX_SIZE) % MAX_SIZE = (3 - 8 + 21) % 21 = 16



    循环队列JAVA语言实现

    展开全文
  • 目录 一、概述 1、队列ADT 2、队列的基本操作 3、队列的实现方式 ...二、队列数组实现 ...队列(Queue)是只允许一端进行插入操作,而另一端进行删除操作的线性表。 队列是一种先进先出(Firs...

    目录

     

    一、概述

    1、队列ADT

    2、队列的基本操作

    3、队列的实现方式

    二、队列的数组实现

    1、队列的结构

    2、清空队列

    3、创建一个初始化队列 

    4、判断队列是否满

    5、入队

    6、判断队列是否为空

    7、出队操作

     

     


    一、概述

    1、队列ADT

    队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

    队列是一种先进先出(First In First Out)的线性表。

    允许插入的一端称为队尾,插入数据的操作称为入队

    允许删除的一端称为队头,删除数据的操作称为出队

    这里写图片描述

     

    2、队列的基本操作

    CreatQueue()    ——初始化队列
    MakeQueueEmpty   ——清空队列
    EnQueue()        ——进队列
    DeQueue()        ——出队列
    IsQueueEmpty()   ——判断队列是否为空
    IsQueueFull()    ——判断队列是否已满
    

    3、队列的实现方式

    队列可以由数组链表两种形式实现队列操作。分别称为顺序队列链队列

    且顺序队列还可以实现循环,已增加空间的利用。

    下面均讨论顺序循环队列

    二、队列的数组实现

    1、队列的结构

    typedef struct QueueRecord {
        int Capacity; //队列容积
        int Front;  //队头下标
        int Rear;  //队尾下标
        int *array;  //数据域
    } *Queue, queue;
    

    2、清空队列

    这个很重要,为了方便起见,默认队列为空时,队头在0,队尾在-1

    每个人习惯不同,可以不一样(有的人会将初始队尾设置为0),但是后面的操作也要对应改变。

     

    每当插入新的队列尾元素时,“尾指针增1”

    每当删除队列头元素时,“头指针增1”。

    因此,非空队列中,队头始终指向队列头元素队尾始终指向队列尾元素另:队尾指向队列末尾元素的下一个

    void MakeQueueEmpty(Queue Q) {
        Q->Front = 0;
        Q->Rear = -1;
    }

    3、创建一个初始化队列 

    Queue CreatQueue (int MaxElement) {
        Queue Q = (Queue)malloc(sizeof(queue));
        Q->array = (int *)malloc(sizeof(int)*MaxElement);
        Q->Capacity = MaxElement;
        MakeQueueEmpty(Q);   //初始化清空队列
        return Q;
    }

     

    4、判断队列是否满

    如何判断一个循环队列是否满的? 不如这样理解:

    假设我们在军训中排队,每个人报数。一个队列只能站10个人,从1报到10,队就满了。后来呢,队头的两个人出队了,然后又补充了两个新队员,那么这时候的报数是3到12。这时队列也是满的。

    两种情况下判断队满的条件分别为:

    (10 + 1) % 10 = 1
    (12 + 1) % 10 = 3

    所以很容易发现队列满的条件就是 :

    (rear+1) % Capacity == front 

    int QueueIsFull(Queue Q) {
        return (Q->Rear + 1) % Q->Capacity == Q->Front;
    }

    5、入队

     先要判断是否队列已满。

    入队:队尾后移出一位并赋值。

    需要注意的是,这里实现的时循环队列,所以当队尾移至超出数组下标界限时,要将其移至数组的开始,以实现循环储存

    void Enqueue(int x, Queue Q){
    
        if (QueueIsFull(Q))  //队列已满
            return;
    
        if(++ Q->Rear == Q->Capacity)  //队尾后移一位,若到数组末端,至于最前
            Q->Rear = 0;
        Q->array[Q->Rear] = x;  //入队
    }

    6、判断队列是否为空

    int QueueIsEmpty(Queue Q) {
        return Q->Rear + 1 == Q->Front;
    }

    7、出队操作

    注意不要对空队列进行出队操作,先要判断队列是否为空。

    void Dequeue(Queue Q) {
        if(QueueIsEmpty(Q))
            return;
        if (++Q->Front == Q->Capacity) //队首后移一位(相当于删除队首)
            Q->Front = 0;
    }

     



    End

    欢迎关注个人公众号“鸡翅编程”,这里是认真且乖巧的码农一枚,旨在用心写好每一篇文章,平常会把笔记汇总成推送更新~

     

    展开全文
  • 如果用一个循环数组表示队列,并且只设队列头指针Front,不设尾指针Rear,而是另设Count记录队列中元素个数。请编写算法实现队列入队和出队操作。 函数接口定义: bool AddQ( Queue Q, ElementType X ); Element...
  • 数组循环队列

    2017-12-13 23:25:14
    此处我们将要介绍的循环队列其实是队列的一种具体实现,由于一般的数组实现的队列结构频繁出队的情况下,会产生假溢出现象,导致数组使用效率降低,所以引入循环队列这种结构。本文将从以下两个大角度介绍循环队列...
  • #include<iostream>using namespace std;#define Maxsize 100class Qune{public: int data[Maxsize]; int front; int rear;};void Qinsert(Qune&... //入队int Qdelete(Qune&A); //出队int...
  • 循环队列的理解

    2021-07-06 22:17:45
    循环队列存储在数组A[0…n-1],其头尾指针分别为f和r,头指针f总是指向队头元素,尾指针r总是指向队尾元素的下一个位置,则元素e入队时的操作为(B )。 A.A[r]=e; r=r+1 B.A[r]=e; r=(r+1)%n C.A[r]=e;r=(r+1)%(n...
  • 存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来实际编程应用来实现。循环队列的问题循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和...
  • 1 循环队列的概念
  • 实现循环队列的入队,出队等基本操作循环队列的基本操作??一、实验目的 1. 理解并掌握队列的逻辑结构和顺序存储结构,了解循环队列的特点;... 循环队列存储结构描述 #define MAXSIZE 100 //最大...
  • 一、基于数组实现的队列 #include<stdio.h> #include<stdlib.h> #define size 10 // 宏定义一个大小为10的队列 // 基于数组实现的队列称为顺序队列 // 定义一个队列数组结构体 typedef struct queue...
  • 数组实现循环队列

    2021-01-28 20:15:28
    这里我用数组来模拟队列,并达到循环队列的效果 思路分析 首先定义一个数组,来存储数据。随后定义一个头指针front,指向队列的头元素;定义一个尾指针rear,指向待插入的位置,也就是队尾元素的后一个位置。 当头尾...
  • 数据结构(C语言)-循环队列基本操作

    千次阅读 2020-10-19 23:52:58
    文章首发于 2020-10-15 知乎文章:数据结构(C语言)-循环队列基本操作 作者:落雨湿红尘(也是我o) 01.队列介绍 队列是一种先进先出(first in first out,FIFO)的线性表,是一种常用的数据结构。 它只允许表的...
  • 1. 基于数组实现循环队列 package com.feifei.demo.queue; import java.io.Serializable; import java.util.Objects; import java.util.stream.Stream; /** * 自定义循环队列 * 1. 单队列会出现假溢出的情况,...
  • 队列是一种特殊的线性表,特殊之处在于它只允许表的前端(front)进行删除操作,而表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队...
  • //定义队列结构 typedef struct Queue { int *data; int rear; int front; }squeue; //初始化100个数字的队列 void Initqueue(squeue *q) { q->data=(int *)malloc(MAX*sizeof(int)); q->fr
  • Java数组实现循环队列的两种方法

    万次阅读 2018-08-28 20:49:35
    版权声明:本文为博主原创文章,未经博主允许不得转载。... 用java实现循环队列的方法: 1、增加一个属性size用来记录目前的元素个数。目的是当head=rear的时候,通过size=0还是size=...2、数组中存储数组大小-1个元...
  • 循环队列基本操作及遍历 C语言实现(数组)循环队列基本操作及遍历 C语言实现(数组)与栈不同 队列基本原则:先入先出 后入后出约定一个下标(rear)指向当前入队元素要插入的下标 即最后一个入队元素下标的下一位即 如果...
  • 队列:只允许一端进行插入操作另一端进行产出操作的线性表。 队列是一种先进先出的线性表(简称FIFO)。其中允许插入操作的一端称为队尾,允许删除操作的一端称为队头。例如队列a=(a1,a2,a3,...,an),其中a1是...
  • 数组存放循环队列

    千次阅读 2019-07-11 18:55:54
    /*以数组存放循环队列,tag=0或1区分rear和front相等时 队空或者队满,编写相应的入队和出队算法。 */ #ifndef PCH_H #define PCH_H #include<stdio.h> #include<iostream> #include<malloc.h> #...
  • 但是循环队列中,判断队空和堆满的条件都是Q.rear = Q.front,这给我们的编程实现带来了很多麻烦,这样我们会有三种处理方法, 1.牺牲一个存储单元,入队的时候将队头指针队尾指针的下一位置最为队列满的条件 这是...
  • 循环队列分析及源码 1. 概述 队列:是“先进先出”的数据结构,从队尾入队,从队头出队。 队列使用的Array,参考“数据结构–手写动态数组”。 2. 数组队列源码 public interface Queue<T> { int get...
  • Java数组实现循环队列

    千次阅读 2018-10-29 20:55:01
    Java数组实现循环队列 上一节(Java实现队列——顺序队列、链式队列)我们使用数组实现了顺序队列,但是tail == n时会有数据搬移操作,...数组实现的非循环队列中,队满的判断条件是tail == n,队空的判断条件...
  • 该代码可VC6.0平台直接编译运行,经...用数组实现了循环队列操作,包括入队,出队,队列是否为空,队列是否为满,以及队列的遍历输出功能,各个子函数有详细的说明……希望对正在学习数据结构的同志有所帮组……
  • 静态数组队列(循环队列)基本操作

    千次阅读 2017-04-28 23:54:42
    /*静态数组队列(循环队列):C语言实现版*/ /*特点:队列大小固定,可以防止伪溢出发生*/ #include #include /*定义队列*/ #define MAX_Q_SIZE 5 /*最大队列长度+1 ,实际长度为4*/ typedef struct { int *base ; ...
  • 循环队列中最重要的的两个操作就是判断是否为空和是否已满。当head==tail时,表示队列为空。当(tail+1)%MAX_SIZE == head,表示队列已满。我判断队满的方法:牺牲一个单元来区分对空和队满,入队时少...
  • 此处我们将要介绍的循环队列其实是队列的一种具体实现,由于一般的数组实现的队列结构频繁出队的情况下,会产生假溢出现象,导致数组使用效率降低,所以引入循环队列这种结构。本文将从以下两个大角度介绍循环队列...
  • 数组存储结构队列(Queue)两端允许操作的类型不一样:可以进行删除的一端称为队头,这种操作也叫出队dequeue可以进行插入的一端称为队尾,这种操作也叫入队enqueue总的来说,队头(front)只能出队,队尾(rear)只能...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 18,157
精华内容 7,262
关键字:

循环队列存储在数组中入队的操作