精华内容
下载资源
问答
  • 二维数组的值是默认值 0 ,记录了很没有意义数据,可以将其转为稀疏数组进行存储。 1.2 稀疏数组应用实例 原始数组转换成稀疏数组(代码) //测试代码 class Demo{ public static void main(String[] ...

    1 稀疏数组

    1.1 实际需求

    二维数组的很多值是默认值 0 ,记录了很多没有意义的数据,可以将其转为稀疏数组进行存储。
    在这里插入图片描述

    在这里插入图片描述

    1.2 稀疏数组应用实例

    在这里插入图片描述

    • 原始数组转换成稀疏数组(代码)
    //测试代码
    class Demo{
    	public static void main(String[] args){
    		//创建一个11*11的二维数组
    		// 0: 表示没有棋子, 1 表示 黑子 2 表蓝子
    		int[][] array = new int[11][11];
    		array[1][2] = 1;//黑子位置
    		array[2][3] = 2;//蓝子位置
    		
    		System.out.println("打印原始数组:");
    		PrintArray.printArray(array);
    		
    		//调用转换成稀疏数组的方法
    		int[][] arr = SparseArray.sparseArray(array);
    		//打印稀疏数组
    		System.out.println("打印稀疏数组:");
    		PrintArray.printArray(arr);
    		
    		//调用还原成原始数组的方法
    		int[][] yArr = FanSparseArray.fanSparseArray(arr);
    		//打印稀疏数组
    		System.out.println("打印原始数组:");
    		PrintArray.printArray(yArr);
    	}
    }
    
    class SparseArray{
    	//将原始数组转换成稀疏数组
    	public static int[][] sparseArray(int[][] arr){
    		//1.先遍历原始数组,得到有效数据个数
    		int sum = 0;
    		for(int i = 0; i < arr.length; i++){
    			for(int j = 0; j < arr[i].length; j++){
    				if(arr[i][j] != 0){
    					sum++;
    				}
    			}
    		}
    		
    		//2.根据有效数据个数创建稀疏数组
    		int[][] sparseArr = new int[sum+1][3];
    		
    		//3.将原始数组中的有效数据存入稀疏数组
    		//稀疏数组第一行存放原始数组行数,列数,有效数据个数
    		sparseArr[0][0] = arr.length;
    		sparseArr[0][1] = arr[0].length;
    		sparseArr[0][2] = sum;
    		//稀疏数组从第二行开始存放:有效数据的行数,列数,数值
    		int count = 0;//定义有效数据的个数
    		for(int i = 0; i < arr.length; i++){
    			for(int j = 0; j < arr[i].length; j++){
    				if(arr[i][j] != 0){
    					count++;
    					sparseArr[count][0] = i;
    					sparseArr[count][1] = j;
    					sparseArr[count][2] = arr[i][j];
    				}
    			}
    		}
    		return sparseArr;
    	}
    }
    
    class FanSparseArray{
    	//将稀疏数组还原成原始数组
    	public static int[][] fanSparseArray(int[][] arr){
    	//1.先读取稀疏数组的第一行,创建原始数组
    	int[][] yArray = new int[arr[0][0]][arr[0][1]];
    	
    	//2.读取稀疏数组后n行数据,赋值给原始二维数组
    	for(int i =1; i <= arr[0][2]; i++){
    			int row = arr[i][0];
    			int col = arr[i][1];
    			yArray[row][col] = arr[i][2];
    		}
    	return yArray;
    	}
    }
    
    //打印二维数组(循环嵌套)
    class PrintArray{
    	public static void printArray(int[][] arr){
    		for(int i = 0; i < arr.length; i++){
    			for(int j = 0; j < arr[i].length; j++){
    				System.out.print(arr[i][j]+"\t");
    			}
    
    			System.out.println();
    		}
    	}
    }
    
    • 结果截图

    在这里插入图片描述

    2 队列(Queue)

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    2.1 概述

    • 队列是一种特殊的线性表,可以用数组或者链表实现。尾部添加,头部删除,FIFO
      在这里插入图片描述

    2.2 数组模拟队列

    • 队列容量:maxSize
    • 队列判空:front == rear
    • 队列判满:rear == (maxsize - 1)
    • 队列元素个数:rear - front
    • 元素入队列条件:队列没满
    • 元素出队列条件:队列没空

    代码实现

    package com.tony.queue;
    
    public class ArrayQueue {
    	private int maxSize;// 表示数组的最大容量
    	private int front; // 表示队列头
    	private int rear; // 表示队列尾
    	private int[] arr; // 该数组用于存放数据,模拟队列
    
    	// 队列的构造函数
    	public ArrayQueue(int maxSize) {
    		this.maxSize = maxSize;
    		arr = new int[maxSize];
    		front = -1;
    		rear = -1;
    	}
    	
    	// 判断队列是否满
    	public boolean isFull() {
    		return rear == maxSize - 1;
    	}
    
    	// 判断队列是否为空
    	public boolean isEmpty() {
    		return rear == front;
    	}
    	
    	// 添加数据到队列
    	public void addQueue(int n) {
    		// 判断队列是否满
    		if (isFull()) {
    			System.out.println("队列满,不能加入数据~");
    			return;
    		}
    		rear++; // 让rear后移
    		arr[rear] = n;
    	}
    	
    	// 获取队列的数据, 出队列
    	public int getQueue(){
    		//判断队列是否为空
    		if(isEmpty()){
    			//通过抛出异常
    			throw new RuntimeException("队列空 ,不能取数据");
    		}
    		front++;
    		return arr[front];
    	}
    	
    	// 显示队列的所有数据
    	public void showQueue(){
    		//判空
    		if (isEmpty()) {
    			System.out.println("队列空的,没有数据~~");
    			return;
    		}
    		//遍历
    		for(int i = front + 1; i <= rear; i++){
    			System.out.println("arr["+i+"]="+arr[i]);
    		}
    	}
    	
    	// 显示队列的头数据, 注意不是取出数据
    	public int headQueue(){
    		//判空
    		if(isEmpty()){
    			System.out.println("队列为空,没有数据");
    		}
    		return arr[front + 1];
    	}
    }
    
    
    import java.util.Scanner;
    class ArrayQueueDemo{
    	public static void main(String[] args){
    		//创建一个队列
    		ArrayQueue queue = new ArrayQueue(3);
    		String key = "";
    		//键盘输入
    		Scanner sc = new Scanner(System.in);
    		//循环标志
    		boolean loop = true;
    		
    		while(loop){
    			System.out.println("show: 显示队列");
    			System.out.println("exit: 退出程序");
    			System.out.println("add: 添加数据到队列");
    			System.out.println("get: 从队列取出数据");
    			System.out.println("head: 查看队列头的数据");
    			key = sc.nextLine();	//接收一个字符串
    			
    			switch(key){
    				case"show":
    					queue.showQueue();
    					break;
    				case"add":
    					System.out.println("请输入一个数:");
    					int value = sc.nextInt();
    					queue.addQueue(value);
    					break;
    				case"get":
    					try{
    						int res = queue.getQueue();
    						System.out.println("取出的数据是"+res);
    					}catch(Exception e){
    						System.out.println(e.getMessage());
    					}
    					break;
    				case "head":
    					try{
    						int res = queue.headQueue();
    						System.out.println("队列头的数据是"+res);
    					}catch(Exception e){
    						System.out.println(e.getMessage());
    					}
    					break;
    				case "exit":
    					sc.close();
    					loop = false;
    					break;
    				default:
    					break;
    			}
    		}
    		System.out.println("程序退出~~");
    	}
    }
    

    在这里插入图片描述

    • 目前数组只能使用一次,没有达到复用的效果,造成了空间的浪费。

    2.3 数组模拟环形队列

    1. front指向队列头的位置,即arr[front]是队列的第一个元素,front初始值为0
    2. rear指向队列尾的后一个位置。rear初始值为0
    3. 队列满的条件:(rear + 1)%maxSize == front
    4. 队列空的条件:rear == front
    5. 队列中有效数据个数:(rear + maxSize - front)%maxSize
    6. 队列容量:maxSize - 1
    • 队列判满:
        为何要在 rear 之后,front 之前空出一个元素的空间?因为如果不空出一个元素,队列判空条件为:front == rear ,队列判满的条件也是:front == rear ,有歧义!
        队列容量:因为空出了一个元素,所以队列容量就变成了 (maxSize - 1)
        当空出一个元素的空间,如何判满?当还剩一个元素时,队列就已经满了,所以判断条件为 (rear + 1) % maxSize == front
    • 队列元数个数:
        计算公式:(rear + maxSize - front) % maxSize ,这样来思考:
        当 rear 比 front 大时,即 (rear -front) > 0 ,这时还没有形成环形结构,(rear -front) 即是队列元素个数
        当 rear 比 front 小时,即 (rear -front) < 0 ,这时已经形成了环形结构,(rear -front) 表示数组还差多少个元素存满(负数),(rear + maxSize - front) 即是队列元素个数
        综上:(rear + maxSize - front) % maxSize
    • 队列入队:
        首先,队列不满才能入队
        由于 rear 指向队列尾部元素的后一个元素,所以直接设置即可: arr[rear] = value
        接下来,rear 应该向后移动一个位置:rear = (rear + 1) % maxSize
        取模是为了防止数组越界,让指针从新回到数组第一个元素
    • 队列出队:
        首先,队列不空才能出队
        由于 front 直接指向队列头部元素,所以直接返回该元素即可:int value = arr[front ]
        接下来,front 应该向后移动一个位置:front = (front + 1) % maxSize
        取模是为了防止数组越界,让指针从新回到数组第一个元素
    class CircleArray{
    	private int maxSize; // 表示数组的最大容量
    	// front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    	// front 的初始值 = 0
    	private int front;
    	// rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    	// rear 的初始值 = 0
    	private int rear; // 队列尾
    	private int[] arr; // 该数据用于存放数据, 模拟队列
    	
    	//构造方法
    	public CircleArray(int maxSize) {
    		this.maxSize = maxSize;
    		arr = new int[maxSize];
    	}
    	
    	// 判断队列是否满
    	public boolean isFull(){
    		return (rear + 1)%maxSize == front;
    	}
    	
    	// 判断队列是否为空
    	public boolean isEmpty(){
    		return rear == front;
    	}
    	
    	// 添加数据到队列
    	public void addQueue(int n) {
    		// 判断队列是否满
    		if (isFull()) {
    			System.out.println("队列满,不能加入数据~");
    			return;
    		}
    		// 直接将数据加入
    		arr[rear] = n;
    		// 将 rear 后移, 这里必须考虑取模
    		rear = (rear + 1) % maxSize;
    	}
    	
    	// 获取队列的数据, 出队列
    	public int getQueue() {
    		// 判断队列是否空
    		if (isEmpty()) {
    			// 通过抛出异常
    			throw new RuntimeException("队列空,不能取数据");
    		}
    		// 这里需要分析出 front是指向队列的第一个元素
    		// 1. 先把 front 对应的值保留到一个临时变量
    		// 2. 将 front 后移, 考虑取模
    		// 3. 将临时保存的变量返回
    		int temp = arr[front];
    		front = (front + 1) % maxSize;
    		return temp;
    	}
    	
    	// 显示队列的所有数据
    	public void showQueue(){
    		// 遍历
    		if (isEmpty()){
    			System.out.println("队列空的,没有数据~~");
    			return;
    		}
    		// 思路:从front开始遍历,front + size()次
    		for (int i = front; i < front + size(); i++) {
    			System.out.println("arr["+i%maxSize+"]="+arr[i % maxSize]);
    		}
    	}
    	
    	// 求出当前队列有效数据的个数
    	public int size(){
    		return (rear + maxSize - front) % maxSize;
    	}
    	
    	// 显示队列的头数据, 注意不是取出数据
    	public int headQueue() {
    		// 判断
    		if (isEmpty()) {
    			throw new RuntimeException("队列空的,没有数据~~");
    		}
    		return arr[front];
    	}
    }
    
    import java.util.Scanner;
    public class CircleArrayQueueDemo {
    	public static void main(String[] args) {
    		//测试一下
    		System.out.println("测试数组模拟环形队列的案例~~~");
    		
    		// 创建一个环形队列
    		CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
    		String key = ""; // 接收用户输入
    		Scanner scanner = new Scanner(System.in);//
    		boolean loop = true;
    		// 输出一个菜单
    		while (loop) {
    			System.out.println("show: 显示队列");
    			System.out.println("exit: 退出程序");
    			System.out.println("add: 添加数据到队列");
    			System.out.println("get: 从队列取出数据");
    			System.out.println("head: 查看队列头的数据");
    			key = scanner.nextLine();		// 接收一个字符
    			switch (key) {
    			case "show":
    				queue.showQueue();
    				break;
    			case "add":
    				System.out.println("输出一个数");
    				int value = scanner.nextInt();
    				queue.addQueue(value);
    				break;
    			case "get": // 取出数据
    				try {
    					int res = queue.getQueue();
    					System.out.printf("取出的数据是%d\n", res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case "head": // 查看队列头的数据
    				try {
    					int res = queue.headQueue();
    					System.out.printf("队列头的数据是%d\n", res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case "exit": // 退出
    				scanner.close();
    				loop = false;
    				break;
    			default:
    				break;
    			}
    		}
    		System.out.println("程序退出~~");
    	}
    }
    

    在这里插入图片描述

    展开全文
  • 队列的数组实现 C

    2019-05-02 11:46:28
    队列的实现有很种,但是只要我们保证函数调用的效果相同那么怎么实现都无所谓。 front和rear指针指向的问题 队列有两指针,头指针front和尾指针rear。 使用数组实现队列的时候 可以让front指向队列的第一...

    参考:数据结构与算法分析 --C语言描述
    队列的实现有很多种,但是只要我们保证函数调用的效果相同那么怎么实现都无所谓。

    front和rear指针指向的问题

    在这里插入图片描述
    队列有两个指针,头指针front和尾指针rear。

    使用数组实现队列的时候

    1. 可以让front指向队列的第一个元素,rear指向队列的最后一个元素的下一个位置;
    2. 也可以让front指向第一个位置的前一个位置,rear指向最后一个位置;
    3. 也可以让front指向第一个位置,rear指向最后一个位置

    使用前两种方法可以使用front == rear确定队列是否为空,第三种可以使用rear + 1 = front 的来确定队列为空

    使用循环队列

    从上面的图可以看到,出队时front向后移动,那么前面空出的数组空间就无法得到利用,所以我们要使rear指针可以回到数组的开始位置。
    在这里插入图片描述

    如何判断队列的空,满

    我使用的front和rear指向是第三种。那么当队列为空时有front == (rear+1)%Maxsize,队列为满时这个条件同时成立,怎么判断队列的空,满呢?
    有三种方法:

    1. 添加变量size标识队列的大小
    2. 使用tag标签,当入队时tag设置为1,出队时设为0,所以队满时tag总是为1
    3. 在数组中预留一个空间,如果使用front指向第一个位置,rear指向最后一个位置,那么队空:front == (rear+1)%Maxsize, 队满时front ==(rear+2)%Maxsize。

    针对第三种情况,当front指向第一个位置,rear指向最后一个位置的下一个位置时,盗用网上的一张图来理解:
    在这里插入图片描述

    代码

    本次使用循环队列,front指向第一个位置,rear指向最后一个位置,通过size来判断队列的空满。

    queue.h

    #ifndef QUEUE_H_INCLUDED
    #define QUEUE_H_INCLUDED
    
    typedef int ElementType;
    
    struct QueueRecord;
    typedef struct QueueRecord *Queue;
    
    int IsEmpty(Queue Q);
    int IsFull(Queue Q);
    Queue CreateQueue(int MaxElements);
    void DisposeQueue(Queue Q);		//销毁队列
    void MakeEmpty(Queue Q);	//使队列为空
    void Enqueue(Queue Q,ElementType X);
    void Dequeue(Queue Q);
    ElementType Front(Queue Q);		//返回队列的队首元素
    ElementType FrontAndDequeue(Queue Q);	//返回队首元素并出队
    
    #endif // QUEUE_H_INCLUDED
    
    

    queue.c

    #include"..\fatal.h"
    #include"queue.h"
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MinQueueSize (5)
    
    
    struct QueueRecord{
        int Capacity;		//容量
        int Front;
        int Rear;
        int Size;
        ElementType *Array;
    };
    
    int IsEmpty(Queue Q){
        return Q->Size == 0;
    }
    
    int IsFull(Queue Q){
        return Q->Size == Q->Capacity;
    }
    
    Queue CreateQueue(int MaxElements){
        Queue Q;
    
        if(MaxElements < MinQueueSize)
            Error("Queue size is too small");
    
        Q = malloc(sizeof(struct QueueRecord));
        if(Q == NULL)
            FatalError("Out of space!!");
    
        Q->Array = malloc(sizeof(ElementType) * MaxElements);
        if(Q->Array == NULL)
            FatalError("Out of space!!");
    
        Q->Capacity = MaxElements;
        MakeEmpty(Q);
    
        return Q;
    }
    
    void MakeEmpty(Queue Q){
        Q->Size = 0;
        Q->Front = 1;
        Q->Rear = 0;
    }
    
    void DisposeQueue(Queue Q){
        if(Q != NULL){
            free(Q->Array);
            free(Q);
        }
    }
    
    static int Succ(int value, Queue Q){
        if( ++value == Q->Capacity)
            value = 0;
        return value;
    }
    
    void Enqueue(Queue Q, ElementType X){
        if(IsFull(Q))
            Error("Full queue");
        else{
            Q->Size++;
            Q->Rear = Succ(Q->Rear, Q);
            Q->Array[Q->Rear] = X;
        }
    }
    
    ElementType Front(Queue Q){
        if(IsEmpty(Q))
            Error("Empty queue");
        else
            return Q->Array[Q->Front];
    }
    
    void Dequeue(Queue Q){
        if(IsEmpty(Q))
            Error("Empty queue");
        else{
            Q->Front = Succ(Q->Front, Q);
            Q->Size --;
        }
    }
    
    ElementType FrontAndDequeue(Queue Q){
        ElementType X;
        if(IsEmpty(Q))
            Error("Empty queue");
        else{
            X = Q->Array[Q->Front];
            Q->Front = Succ(Q->Front, Q);
            Q->Size --;
        }
        return X;
    }
    
    int main(){
    
        Queue Q;
    
        Q = CreateQueue(10);
        Enqueue(Q, 1);
        Enqueue(Q, 2);
        Dequeue(Q);
        printf("%d\n",Front(Q));
        printf("%d\n",FrontAndDequeue(Q));
        printf("%d",IsEmpty(Q));
        DisposeQueue(Q);
    
        return 0;
    
    }
    
    
    展开全文
  • 队列——数组实现

    千次阅读 2018-08-14 00:07:31
    关于队列的定义就不叙述了,百度比我讲的详尽的,在这里说一下用数组实现队列的思想,并附上代码。 我们身边的与队列相关实例很,火车站排队买票或是买饭是排队,都是队列。因此我们很容易想到,队列是有一头...

    队列是一种先进先出的思想。(First In First Out)

    关于队列的定义就不叙述了,百度比我讲的详尽的多,在这里说一下用数组实现队列的思想,并附上代码。

    我们身边的与队列相关实例很多,火车站排队买票或是买饭是排队,都是队列。因此我们很容易想到,队列是有一个头一个尾的,新来的总是在尾,最先来的总是最先买票或是吃饭,当然,像插队一类的我们不做考虑,相信我们都不会喜欢这些的。

    队列的成员的进出我们已经知道了,总是队头出、队尾进,观看我们身边的实例,我们可以看到,排队时,卖饭的阿姨或是卖票的售票员都是不会移动的,移动的都是成员,那么在代码中,我们也需要这样做吗?每出队一位就让剩下的全体成员集体前移一位,未免太累了。因此我们可以很自然的想到,让卖饭阿姨或是售票员来移动,成员们保持不动,已经买到饭或是买到票的成员就直接离开。可是我们又有一个疑问,在空间有限的情况下(即队列长度有限),当卖饭阿姨移动到队尾给最后一个成员打完饭,队列是不是就没有位置了呢?联系实际我们可以很自然的想到,前面的成员离开了,那么前面的位置就空出来了啊,再有成员进入队列就可以去前面的位置啊,只需要让阿姨在回到最前面重新打饭就可以了啊。这就是队列的思想。

    将上述思想化为代码就简单多了。

    首先,在有五个位置的队列中,当没有成员进入队列时,队头和队尾显然都在第一个位置。

    然后,当有成员进入队列时,阿姨还没有开始打饭,队头显然还是在第一个位置,而第一个进入队列后,下一个成员进入队列应该到哪个位置呢?显然是第二个位置,因此,当队列有一个成员时,队尾在第一个成员的后面,也就是说,队尾总是在最后一个成员的后面。

    接着,很快队列就满了,五个位置都有了成员,显然不能有成员再进队列了,这时阿姨开始打饭,给第一个成员打完饭,阿姨就走向第二个成员,也就是说,当第一个成员出去后,队头就到了第二个成员,因此,队头总是在队列的第一个成员。

    当阿姨给三个人打完饭后,只有第四第五个位置有人了,又有新的成员想进队打饭,这时他们就会自然而然地走向前面的位置,因为他们知道阿姨打完饭后就会回到第一个位置给他们打饭,这是队尾依然是最后一个进队的成员的后面,只不过这个成员的位置编号在队头前面。

    同理,阿姨在给第五个位置的成员打完饭就会回到第一个位置给同学打饭。

    队列的思想就是这些了,在用数组实现时,有以下几个地方需要注意:

    1、队列的长度就是数组的长度

    2、没有成员时,队头队尾都指向第一个位置,即下标为0

    3、队头始终指向队列中最先进队的成员,队尾始终指向队列中最后进队的成员的后面下一个位置

    3、当队头与队尾的下标相同时,队列为空,因此队尾在指向第四个位置即下标为3时,就应该算队满,否则当队头下标为0时,最后一个位置即第五个位置也有成员,此时队尾下标为0,按照上面的思想应该算队列为空,与实际不符。因此队列的实际容量始终为数组容量减一。

    4、按照上面的思想,队头和队尾下标表示应该为(当前下标+1)%数组容量,在第一圈为0,1,2,3,4,第二圈时继续自加明显不合适,因为下标因该为0,因此在自加后对数组容量取余

    代码如下:

    #include<iostream>
    using namespace std;
    #define MAXSIZE 10
    class queue
    {
    public:
            queue();
            bool IsFull();
            bool IsEmpty();
            bool EnQueue(int);
            bool DeQueue(int&);
    private:
            int buf[MAXSIZE];
            int rear;
            int front;
    };
    queue::queue()
    {
            this->rear=0;
            this->front=0;
    }
    bool queue::IsEmpty()
    {
            if(this->rear==this->front)
                    return true;
            else
                    return false;
    }
    bool queue::IsFull()
    {
            if((this->rear+1)%MAXSIZE==this->front)
                    return true;
            else
                    return false;
    }
    bool queue::EnQueue(int data)
    {
            if(IsFull())
                    return false;
            this->buf[this->rear]=data;
            this->rear=(this->rear+1)%MAXSIZE;
            return true;
    }
    bool queue::DeQueue(int& data)
    {
            if(IsEmpty())
                    return false;
            data=this->buf[this->front];
            this->front=(this->front+1)%MAXSIZE;
    }
    int main()
    {
            queue q;
            int i=0;
            while(i<20)
            {
                    if(q.EnQueue(i))
                            cout<<"success "<<i<<endl;
                    else
                            cout<<"fail "<<i<<endl;
                    i++;
            }
            while(q.DeQueue(i))
                    cout<<i<<" ";
            cout<<endl;
            return 0;
    }
    

     

    展开全文
  • 由于顺序存储的队列会产生“假溢出的情况”,我们可以将队列的存储结构臆想为一闭合的环状结构,这便是我们所说的循环队列,如下图所示。 循环队列的逻辑结构 但是循环队列中,判断队空和堆满的条件都是Q.rear = Q...

    理论知识

    由于顺序存储的队列会产生“假溢出的情况”,我们可以将队列的存储结构臆想为一个闭合的环状结构,这便是我们所说的循环队列,如下图所示。
    假溢出图示循环队列的逻辑结构
    在这里插入图片描述但是循环队列中,判断队空和堆满的条件都是Q.rear = Q.front,这给我们的编程实现带来了很多麻烦,这样我们会有三种处理方法,
    1.牺牲一个存储单元,入队的时候将队头指针在队尾指针的下一位置最为队列满的条件
    这是判断队空的条件仍然是:Q.rear = Q.front
    但是判断队满的条件变为:(Q.rear+1)%MAXSIZE = Q.front
    队列中元素的个数为:(Q.rear-Q.front+MAXSIZE)%MAXSIZE
    2.在结构体的定义中增加表示元素个数的成员
    队空:Q.size = 0
    队满:Q.size = MAXSIZE
    队列元素个数:Q.size
    3.第一种情况牺牲的存储空间利用起来,当flag = 0时,因为删除发生了Q.rear = Q.front 则表示队空,当flag = 1时,因为增加导致了Q.rear = Q.front 则表示队满

    以下使用第一种方法进行代码实现

    存储结构

    typedef struct {
    	int data[MAXSIZE];
    	int front,rear;
    }Quene;
    

    初始化

    //初始化
    void initQuene(Quene &Q){
    	Q.rear = Q.front = 0;
    }
    

    判空

    bool isEmpty(Quene &Q){
    	if((Q.rear+1)%MAXSIZE == Q.front){
    		cout<<"队列已满"<<endl;
    		return true;
    	}
    	return false;
    }
    

    入队

    //入队
    bool push(Quene &Q,int e){
    	if(!isEmpty(Q)){
    		Q.data[Q.rear] = e;
    		Q.rear = (Q.rear+1) % MAXSIZE;
    		return true; 
    	}
    	return false;
    }
    

    出队

    //出队
    bool pop(Quene &Q){
    	if(Q.rear == Q.front){
    		return false;
    	}else{
    		Q.data[Q.front] = -1;
    		Q.front = (Q.front+1)%MAXSIZE;
    		return true;
    	}
    }
    

    整合测试

    #include<iostream>
    using namespace std;
    #define MAXSIZE 4
    typedef struct {
    	int data[MAXSIZE];
    	int front,rear;
    }Quene;
    //初始化
    void initQuene(Quene &Q){
    	Q.rear = Q.front = 0;
    }
    //判空 
    bool isEmpty(Quene &Q){
    	if((Q.rear+1)%MAXSIZE == Q.front){
    		cout<<"队列已满"<<endl;
    		return true;
    	}
    	return false;
    }
    //入队
    bool push(Quene &Q,int e){
    	if(!isEmpty(Q)){
    		Q.data[Q.rear] = e;
    		Q.rear = (Q.rear+1) % MAXSIZE;
    		return true; 
    	}
    	return false;
    }
    //出队
    bool pop(Quene &Q){
    	if(Q.rear == Q.front){
    		return false;
    	}else{
    		Q.data[Q.front] = -1;
    		Q.front = (Q.front+1)%MAXSIZE;
    		return true;
    	}
    }
    int main()
    {
    	Quene Q;
    	initQuene(Q);
    	push(Q,1);
    	cout << Q.data[Q.rear-1] << endl;
    	push(Q,2);
    	cout << Q.data[Q.rear-1] << endl;
    	push(Q,3);
    	cout << Q.data[Q.rear-1] << endl;
    	push(Q,4);
    	cout << Q.data[Q.front] << endl;
    	pop(Q);
    	cout << Q.data[Q.front] << endl;
    	pop(Q);
    	cout << Q.data[Q.front] << endl;
    	return 0;
     } 
    
    展开全文
  • 循环队列(数组实现)

    2020-11-01 22:25:52
    循环队列(数组实现) 文章目录前言官方解析原题+代码解决了我心中的的疑惑小结 前言 今天,我又下定决心准备在来到LeetCode来看看算法。...首先,在写队列的时候我不清楚队列需要哪些属性 第二,对于进队和.
  • PHP的数组处理函数还可以将数组实现队列,堆栈是“先进后出”。...入栈主要是利用array_push()函数向第一个参数的数组尾部添加一个或多个元素,然后返回新数组的长度,示例如下:而PHP中,将数组当作是...
  • 数据对象集:一个有0个或多个元素有穷线性表。 操作集:长度为MaxSize的队列Q  Queue,队列元素item  ElementType 1、Queue CreatQueue( int MaxSize ):生成长度为MaxSize队列; 2、int IsFullQ( Queue Q...
  • 例如,你可能有一台能同时运行多个应用电脑或手机。这是通过为每个应用程序时间分配一个优先级,并总是处理下一个优先级高事件来实现。 在这种情况下,一个合适数据结构应该支持两种操作:删除最大元素和...
  • 1、 栈:先进后出,后进先出 2、 队列:先进先出,后进后出 3、 数组:查询快,增加删除慢 ...4、 链表:由一个链子把多个结点连起来组成数据  a) 结点:数据域和地址域组成  b) 查询慢,增加删除快 ...
  • 优先队列是0个或多个元素集合,每个元素都有一个优先权或值,对优先队列执行操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小元素,删除操作用来删除...
  • 个队列每一个环节只有一个数据,而且每个环节数据类型都是相同,然而链表每一个环节之中可以包含多个数据,相当于每一个环节都是一个结构体,即链表是建立在结构体与指针之上(C语言之中)...
  • 概念:通过一个链子把多个结点(元素)连接起来,由数据和地址组成一个元素, 节点本身必须有一个地址值(就是下一个元素地址值) 特点:增删快,查询慢 分类: 单向链表:数据+下一个元素地址 双向链表...
  • 链表:通过一个链子把多个结点(元素)连接起来,由数据和地址组成一个元素, 节点本身必须有一个地址值(就是下一个元素地址值) 特点:查询慢,增删快 链表与数组刚好相反,对于数组
  • 数据结构实际上和算法关系很密切,很算法实现都配合数据结构来实现,但是这不是这次内容,本次仅仅讲述各种数据结构使用,至于实现,一篇文章根本不够讲。 栈使用 栈在vb.net中用stack类封装,里面还有...
  • 现在允许你最多砍断m连接处, 砍完后n根木棍被分成了很段,要求满足总长度最大一段长度最小, 并且输出有多少种砍方法使得总长度最大一段长度最小. 并将结果mod 10007 输入格式 第一行有2数n,m. 接...
  • 数组中一个或多个连续元素可以组成一个子数组,其中存在这样数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效方法帮忙找出所有连续子数组最大值(如果数组元素全部为负数...
  • 数组队列

    2014-03-12 20:46:43
     前今天我们学习了如何定义和使用java中的数组,虽然说数组在储存数据的时候很方便,定义也很简单并且查找速度很快,但是它的局限性也是非常明显的。比如,我们早定义数组时候就...简单的说数组队列是由多个数组...
  • 数组数组队列

    千次阅读 2016-08-11 15:06:24
    一维数组在内存中存储方式是一整块连续空间,多维数组在内存中存储方式是块连续存储空间,这些块不一定连在一起。  数组定义方式有:  1、数据类型 [] 数组名 = new 数据类型[长度];
  • 数组:存储同一种类型的多个元素容器;查询快,增删慢; 链表:有一个链子把多个节点连接起来组成数据;节点有地址(指针域)和数据(数据域);查询慢,增删快; 单项链表,双向链表,单项循环链表,双向循环链表; ...
  • 基于数组实现队列

    2020-01-10 22:45:18
    数组实现队列数据结构-队列基于数组实现栈定义一个队列接口话不说,上代码 数据结构-队列 与栈后进先出不同,队列是一种先进先出的数据结构,FIFO(First In First Out)。 基于数组实现栈 队列的操作也是数组操作的...
  • 优先级队列与普通的队列相比,区别在于他的数据项按关键字的值...优先级队列通常使用堆来实现,下列代码是基于数组的一简单优先级队列的实现。 import java.io.*; class PriorityQueue{ private int maxSize; pr
  • 数组队列总结

    2015-06-26 14:43:12
    数组队列总结 数组这东西是一开始就在被...这次做的是一学生信息管理系统,这并不复杂,创建一学生类,然后添加各种属性即可,而在主程序中用的数组是object数组,由于object是很类的父类,所以他可以储存...
  • 利用JavaScript的数组方法实现队列 相关方法 push()方法: push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。 参数:一个或多个被添加到数组末尾的参数 返回值:数组的新长度 shift()方法 ...
  • 属性:最大容量maxsize,队列头front,队列尾rear,模拟队列的数组arr[]; 构造器, 类的方法:判断队列是否满,队列是否空,添加数据到队列,获取队列的数据,显示队列所有数据。 front:初始值为0,指向队列的第一...
  • 在开始今天内容之前,先来一小玩具,一条用来删除文件bat语句。我发现questasim跟vim同时对文本进行修改时候,同目录下会产生很多的中间文件,所以很久不用bat又要搬出来了。语法非常简单,几秒钟...
  • 【栈和队列】一个数组实现两

    千次阅读 2016-09-17 12:31:53
    学习了栈和队列的基本知识后,我们要利用这些基本知识实现出更情况的栈和队列,下面通过一些面试题使我们更灵活的设计和使用栈和队列。 1.利用一个数组实现两栈 思路: 我们已经学过了栈和数组,数组是一块...
  • ArrayBlockingQueue数组队列的实现原理: 1、对一个数组进行添加和取出数据操作。 2、其中的put和get用同一把lock锁进行互斥操作,控制线程并发情况。 3、当put方法中,数组满时,通过lock下的conditionA 调用...
  • 数组的长度必须是固定的一旦定义之后就无法动态的更改,这就会造成这样的问题,如果数组已满,就无法继续添加数据(当然你可以定义一“足够大的数组”,但问题是大才是足够大呢?太小不够,太大浪费内存空间)。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,772
精华内容 1,108
关键字:

多个队列的数组