精华内容
下载资源
问答
  • 给定一个大小为 n≤106 的数组。 有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子: 该数组为 [1 3 -1 -3 5 3 6 7],k ...

    题目来源AcWing第154题

    题目

    给定一个大小为 n≤106 的数组。
    有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。
    你只能在窗口中看到 k 个数字。
    每次滑动窗口向右移动一个位置。
    以下是一个例子:
    该数组为 [1 3 -1 -3 5 3 6 7],k 为 3。

    数组最大值最小值
    [1 3 -1] -3 5 3 6 7-13
    1 [3 -1 -3] 5 3 6 7-33
    1 3 [-1 -3 5] 3 6 7-35
    1 3 -1 [-3 5 3] 6 7-35
    1 3 -1 -3 [5 3 6] 736
    1 3 -1 -3 5 [3 6 7]37

    你的任务是确定滑动窗口位于每个位置时,窗口中的最大值最小值。

    输入格式

    输入包含两行。
    第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。
    第二行有 n 个整数,代表数组的具体数值。
    同行数据之间用空格隔开。

    输出格式

    输出包含两个。
    第一行输出,从左至右,每个位置滑动窗口中的最小值。
    第二行输出,从左至右,每个位置滑动窗口中的最大值。

    输入样例:

    8 3
    1 3 -1 -3 5 3 6 7

    输出样例:

    -1 -3 -3 -3 3 3
    3 3 5 5 6 7

    解题思路

    首先根据滑动窗口数据进出的特殊性我们很容易想到用队列来最这题。然后题目要求求最值,则想到了单调队列。滑动窗口(队列)在数组中滑动,然后队头出队,再数据入队列前判定队头是否比当前数大(或者小),是的话就出队。数据入队后输出队头就是要求的最值。

    代码

    #include <iostream>
    using namespace std;
    
    const int N = 100010;
    int a[N], queue[N]; //a[N]为数组长度,queue[N]为队列
    int n, k; //n为数组总长度,k为队列长度
    
    int main(){
        scanf("%d%d", &n,&k);
        for(int i = 0;i < n; i++) scanf("%d", &a[i]); 
    
        int head = 0, tail = -1; //head为队列头指针,tail为队列尾指针,队列初始化
        for(int i = 0; i < n; ++ i ){
            //队列不为空,且滑动窗口还没走到最后,队首走出窗口
            if(head <= tail && queue[head] < i - k +1) head ++;
            //队列不为空,且队头元素比当前数大,出队
            while(head <= tail && a[queue[head]] >= a[i]) tail --;
            queue[++ tail] = i; //当前数从队尾入队
            //从第一个窗口开始,数组已经遍历到第k个数的时候,输出队头元素(此时队头元素就是最小值)
            if(i >= k - 1) printf("%d ", a[queue[head]]); 
        }
        printf("\n");
        //求最大值也是相同道理,head为队列头指针,tail为队列尾指针,队列初始化
        head = 0, tail = -1;
        for(int i = 0; i < n; ++ i ){
            if(head <= tail && queue[head] < i - k +1) head ++;
            while(head <= tail && a[queue[head]] <= a[i]) tail --;
            queue[++ tail] = i; 
            if(i >= k - 1) printf("%d ", a[queue[head]]); 
        }
    
        return 0;
    }
    
    
    展开全文
  • C语言之对队列、结构体、指针、数组的理解附测试例子#include #include #define QueueSize 100typedef unsigned char datatype;//队列的数据元素typedef struct {int front;int rear;int count; //用于计数datatype ...

    C语言之对队列、结构体、指针、数组的理解

    附测试例子

    #include

    #include

    #define QueueSize 100

    typedef unsigned char datatype;

    //队列的数据元素

    typedef struct {

    int front;

    int rear;

    int count; //用于计数

    datatype data[QueueSize];  //用于缓存数组

    }cirqueue;

    cirqueue QUEUE;

    //置空队

    void InitQueue(cirqueue *q)

    {

    q->front = q->rear = 0;

    q->count = 0;

    }

    //判断队满

    int QueueFull(cirqueue *q)

    {

    return (q->count == QueueSize);

    }

    //判断队空

    int QueueEmpty(cirqueue *q)

    {

    return (q->count==0);

    }

    //入队

    void EnQueue(cirqueue *q,datatype x)

    {

    assert(QueueFull(q) == 0);//q满 终止程序

    q->count++;

    q->data[q->rear] = x;

    q->rear = (q->rear + 1)%QueueSize;//循环队列设计 防止内存浪费

    }

    //出队

    datatype DeQueue(cirqueue *q)

    {

    datatype temp;

    assert(QueueEmpty(q)==0); //q空,则终止程序,打印错误信息

    temp=q->data[q->front];

    q->count--;

    q->front = (q->front +1)%QueueSize;

    return temp;

    }

    void main()

    {

    datatype aa[8]={0x12,0x33,0x88,0};

    datatype dat[8]={0};

    datatype byte1,byte2,byte3,byte4;

    datatype *point,*point2=aa;

    int a=0x12345678;

    int b=0;

    EnQueue(&QUEUE,aa[0]);

    EnQueue(&QUEUE,aa[1]);

    EnQueue(&QUEUE,aa[2]);

    EnQueue(&QUEUE,aa[3]);

    //assert( 表达式 ); //若表达式为假(为0),则向stderr 打印一条出错信息,然后调用abort来终止程序

    //assert主要用于调试程序

    printf("0x%x\n",QUEUE.count);

    dat[0] = DeQueue(&QUEUE);

    dat[1] = DeQueue(&QUEUE);

    dat[2] = DeQueue(&QUEUE);

    dat[3] = DeQueue(&QUEUE);

    printf("0x%x\n",dat[0]);

    printf("0x%x\n",dat[1]);

    printf("0x%x\n",dat[2]);

    printf("0x%x\n",dat[3]);

    /*测试32位数据的拆分*/

    byte1=a&0xff;

    byte2=(a>>8)&0xff;

    byte3=(a>>16)&0xff;

    byte4=(a>>24)&0xff;

    printf("0x%x\n",byte1);

    printf("0x%x\n",byte2);

    printf("0x%x\n",byte3);

    printf("0x%x\n",byte4);

    /*测试32位数据的合并*/

    b = byte1 | (byte2<<8) | (byte3<<16) | (byte4<<24);

    printf("0x%x\n",b);

    printf("%d\n",b);

    /*用于测试指针与数组的关系*/

    point = aa;// 此时 point 和 aa 是同一地址

    printf("0x%x\n",*point);

    printf("0x%x\n",*(point+1));

    printf("0x%x\n",*(point+2));

    printf("0x%x\n",*(point+3));

    printf("0x%x\n",&aa);

    printf("0x%x\n",&(*point));

    printf("0x%x\n",&a);

    printf("0x%x\n",&b);

    //

    printf("0x%x\n",*point2);

    printf("0x%x\n",*(point2+1));

    for(;;)

    {

    }

    }

    展开全文
  • /*** 简单的线程池与任务队列**/public class WorkQueue {private final int nThreads;// 线程池的大小private final PoolWorker[] threads;// 用数组实现线程池private final LinkedList queue;// 任务队列public ...

    [java]代码库import java.util.*;

    /**

    * 简单的线程池与任务队列

    *

    */

    public class WorkQueue {

    private final int nThreads;// 线程池的大小

    private final PoolWorker[] threads;// 用数组实现线程池

    private final LinkedList queue;// 任务队列

    public WorkQueue(int nThreads) {

    this.nThreads = nThreads;

    queue = new LinkedList();

    threads = new PoolWorker[nThreads];

    for (int i = 0; i < nThreads; i++) {

    threads[i] = new PoolWorker();

    threads[i].start();// 启动所有工作线程

    }

    }

    public void execute(Runnable r) {// 执行任务

    synchronized (queue) {

    queue.addLast(r);

    queue.notify();

    }

    }

    private class PoolWorker extends Thread {// 工作线程类

    public void run() {

    Runnable r;

    while (true) {

    synchronized (queue) {

    while (queue.isEmpty()) {// 如果任务队列中没有任务,等待

    try {

    queue.wait();

    } catch (InterruptedException ignored) {

    }

    }

    r = (Runnable) queue.removeFirst();// 有任务时,取出任务

    }

    try {

    r.run();// 执行任务

    } catch (Exception e) {

    // TODO: handle exception

    }

    }

    }

    }

    public static void main(String args[]) {

    WorkQueue wq = new WorkQueue(10);// 10个工作线程

    Mytask r[] = new Mytask[20];// 20个任务

    for (int i = 0; i < 20; i++) {

    r[i] = new Mytask();

    wq.execute(r[i]);

    }

    }

    }

    class Mytask implements Runnable {// 任务接口

    public void run() {

    String name = Thread.currentThread().getName();

    try {

    Thread.sleep(100);// 模拟任务执行的时间

    } catch (Exception e) {

    // TODO: handle exception

    }

    System.out.println(name + " executed OK");

    }

    }

    694748ed64b9390909c0d88230893790.png

    展开全文
  • 一、数组 数组是应用最广泛的一种数据结构,常常被植入到编程语言中,作为基本数据类型使用,因此,在一些教材中,数组并没有被当做一种数据结构单独拿出来讲解(其实数组就是一段连续的内存,即使在物理内存中不是...

    一、数组

        数组是应用最广泛的一种数据结构,常常被植入到编程语言中,作为基本数据类型使用,因此,在一些教材中,数组并没有被当做一种数据结构单独拿出来讲解(其实数组就是一段连续的内存,即使在物理内存中不是连续的,在逻辑上肯定是连续的)。其实没必要在概念上做纠缠,数组可以当做学习数据结构的敲门砖,以此为基础,了解数据结构的基本概念以及构建方法

    数据结构不仅是数据的容器,还要提供对数据的操作方法,比如检索、插入、删除、排序等

    1、无序数组

    下面我们建立一个类,对数组的检索、插入、删除、打印操作进行封装,简便起见,我们假设数组中没有重复值(实际上数组可以包含重复值)

    无序数组的优点:插入快,如果知道下标,可以很快的存取

    无序数组的缺点:查找慢,删除慢,大小固定。

    public class Array {
         
          private String [] strArray;
          private int length = 0;       //数组元素个数
                
          //构造方法,传入数组最大长度
          public Array(int max){
                 strArray = new String [max];
          }
         
          //检测数组是否包含某个元素,如果存在返回其下标,不存在则返回-1
          public int contains(String target){
                 int index = -1;
                 for(int i=0;i<length;i++){
                        if(strArray[i].equals(target)){
                               index = i;
                               break;
                        }
                 }
                 return index;
          }
         
          //插入
          public void insert(String elem) {
                 strArray[length] = elem;
                 length++;
          }
         
          //删除某个指定的元素值,删除成功则返回true,否则返回false
          public boolean delete(String target){
                 int index = -1;
                 if((index = contains(target)) !=-1){
                        for(int i=index;i<length-1;i++){
                               //删除元素之后的所有元素前移一位
                               strArray[i] =strArray[i+1]; 
                        }
                        length--;
                        return true;
                 }else{
                        return false;
                 }
          }
         
          //列出所有元素
          public void display(){
                 for(int i=0;i<length;i++){
                        System.out.print(strArray[i]+"\t");
                 }
          }
         
    }

    2、有序数组

        所谓的有序数组就是指数组中的元素是按一定规则排列的,其好处就是在根据元素值查找时可以是使用二分查找,查找效率要比无序数组高很多,在数据量很大时更加明显。当然缺点也显而易见,当插入一个元素时,首先要判断该元素应该插入的下标,然后对该下标之后的所有元素后移一位,才能进行插入,这无疑增加了很大的开销。

    因此,有序数组适用于查找频繁,而插入、删除操作较少的情况

    有序数组的封装类如下,为了方便,我们依然假设数组中是没有重复值的,并且数据是按照由小到大的顺序排列的 

    有序数组最大的优势就是可以提高查找元素的效率,在上例中,find方法使用了二分查找法,该算法的示意图如下:


    这个方法在一开始设置变量lowerBound和upperBound指向数组的第一个和最后一个非空数据项。通过设置这些变量可以确定查找的范围。然后再while循环中,当前的下标curIn被设置为这个范围的中间值

    如果curIn就是我们要找的数据项,则返回下标,如果不是,就要分两种情况来考虑:如果curIn指向的数据项比我们要找的数据小,则证明该元素只可能在curIn和upperBound之间,即数组后一半中(数组是从小到大排列的),下轮要从后半段检索;如果curIn指向的数据项比我们要找的数据大,则证明该元素只可能在lowerBound和curIn之间,下一轮要在前半段中检索

    按照上面的方法迭代检索,直到结束

    有序数组的优点:查找效率高

    有序数组的缺点:删除和插入慢,大小固定

    public class OrderArray {
    	private int[] intArray;
    	private int length = 0; // 数组元素个数
    
    	// 构造方法,传入数组最大长度
    	public OrderArray(int max) {
    		intArray = new int[max];
    	}
    
    	// 用二分查找法定位某个元素,如果存在返回其下标,不存在则返回-1
    	public int find(int target) {
    		int lowerBound = 0; // 搜索段最小元素的小标
    		int upperBound = length - 1; // 搜索段最大元素的下标
    		int curIn; // 当前检测元素的下标
    
    		if (upperBound < 0) { // 如果数组为空,直接返回-1
    			return -1;
    		}
    
    		while (true) {
    			curIn = (lowerBound + upperBound) / 2;
    
    			if (target == intArray[curIn]) {
    				return curIn;
    			} else if (curIn == lowerBound) { // 在当前下标与搜索段的最小下标重合时,代表搜索段中只包含1个或2个元素
    				// 既然走到该分支,证明上一个if分支不满足,即目标元素不等于低位元素
    				if (target == intArray[upperBound]) { // 等于高位元素,返回
    					return upperBound;
    				} else { // 高位元素也不等于目标元素,证明数组中没有该元素,搜索结束
    					return -1;
    				}
    			} else {// 搜索段中的元素至少有三个,且当前元素不等于目标元素
    				if (intArray[curIn] < target) {
    					// 如果当前元素小于目标元素,则将下一个搜索段的最小下标置为当前元素的下标
    					lowerBound = curIn;
    				} else {
    					// 如果当前元素大于目标元素,则将下一个搜索段的最大下标置为当前元素的下标
    					upperBound = curIn;
    				}
    			}
    		}
    	}
    
    	// 插入
    	public void insert(int elem) {
    		int location = 0;
    
    		// 判断应插入位置的下标
    		for (; location < length; location++) {
    			if (intArray[location] > elem)
    				break;
    		}
    		// System.out.println(location);
    		// 将插入下标之后的所有元素后移一位
    		for (int i = length; i > location; i--) {
    			intArray[i] = intArray[i - 1];
    		}
    
    		// 插入元素
    		intArray[location] = elem;
    
    		length++;
    	}
    
    	// 删除某个指定的元素值,删除成功则返回true,否则返回false
    	public boolean delete(int target) {
    		int index = -1;
    		if ((index = find(target)) != -1) {
    			for (int i = index; i < length - 1; i++) {
    				// 删除元素之后的所有元素前移一位
    				intArray[i] = intArray[i + 1];
    			}
    			length--;
    			return true;
    		} else {
    			return false;
    		}
    	}
    
    	// 列出所有元素
    	public void display() {
    		for (int i = 0; i < length; i++) {
    			System.out.print(intArray[i] + "\t");
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		OrderArray orderArray = new OrderArray(4);
    
    		orderArray.insert(3);
    		orderArray.insert(4);
    		orderArray.insert(6);
    		orderArray.insert(8);
    
    		int i = orderArray.find(8);
    		System.out.println("在队列中的位置是" + i);
    	}
    }

    二、栈

        数组、链表、树等数据结构适用于存储数据库应用中的数据记录,它们常常用于记录那些现实世界的对象和活动的数据,便与数据的访问:插入、删除和查找特定数据项

    而栈和队列更多的是作为程序员的工具来使用。他们主要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短很多。在程序操作执行期间它们才被创建,通常它们去执行某项特殊的任务,当任务完成后就被销毁

    栈和队列的访问是受限制的,即在特定时刻只有一个数据项可以被读取或删除

    栈和队列是比数组和其他数据结构更加抽象的结构,是站在更高的层面对数据进行组织和维护

    栈的主要机制可用数组来实现,也可以用链表来实现。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

     

    先来了解栈的概念和实例,然后分别深入理解队列和优先级队列

    栈只允许访问一个数据项:即最后插入的数据。移除这个数据项后才能访问倒数第二个插入的数据项。它是一种“后进先出”的数据结构。

    栈最基本的操作是出栈(Pop)、入栈(Push),还有其他扩展操作,如查看栈顶元素,判断栈是否为空、是否已满,读取栈的大小等

    下面我们就用数组来写一个栈操作的封装类

    public class Stack {
          private int size;                 //栈的大小
          private int top;                  //栈顶元素的下标
          private int [] stackArray;   //栈的容器
         
          //构造函数
          public Stack(int size){
                 stackArray = new int [size];
                 top = -1; //初始化栈的时候,栈内无元素,栈顶下标设为-1
                 this.size = size;
          }
         
          //入栈,同时,栈顶元素的下标加一
          public void push(int elem){
                 stackArray[++top] = elem; //插入栈顶
          }
         
          //出栈,删除栈顶元素,同时,栈顶元素的下标减一
          public int pop(){
                 return stackArray[top--];
          }
         
          //查看栈顶元素,但不删除
          public int peek(){
                 return stackArray[top];
          }
         
          //判空
          public boolean isEmpty(){
                 return (top == -1);
          }
         
          //判满
          public boolean isFull(){
                 return (top == size-1);
          }
         
    }

    上例中,没有对可能的异常进行处理,需要由编程人员保证程序的正确性,比如,才出栈前需要应该保证栈中有元素,在入栈前应保证栈没有满

                                                                                入栈操作示意图


     

                                                                                                               出栈操作示意图

     

    栈通常用于解析某种类型的文本串。通常,文本串是用计算机语言写的代码行,而解析它们的程序就是编译器

    下面我们来用栈来实现一个经典的应用:分隔符匹配。想一下在Eclipse编程时,如果我们写的代码中如果多了一个“{”,后者少了一个“}”,或者括号的顺序错乱,都会报错。接下来我们就用栈来模拟这种分隔符匹配

    分隔符匹配程序从字符串中不断地读取程序,每次读取一个字符,若发现它是左分隔符({、[、(),将它压入栈中。当读到一个右分隔符时()、]、}),弹出栈顶元素,并且查看它是否和该右分隔符匹配。如果它们不匹配,则程序报错。如果到最后一直存在着没有被匹配的分隔符,程序也报错

    我们来看下面这个正确的字符串,在栈中的变化过程:

    a{b(c[d]e)f}

     

    所读字符                  栈中内容

          a                                 空

          {                                  {

          b                                 {

          (                                  {(

          c                                 {(

          [                                  {([

          d                                 {([

          ]                                  {(

          e                                 {(

          )                                  {

          f                                  {

          }                                  空

    最后出现的左分隔符需要被最先匹配,这符合栈“后进先出”的规则

    在本例中,要处理的是字符,所以需要对上面的Stack类进行修改,需要将存放元素的数组改为char类型,并把相关方法的参数类型改为char类型,其余不变

    public class Stack {
          private int size;                 //栈的大小
          private int top;                  //栈顶元素的下标
          private char [] stackArray;       //栈的容器
         
          //构造函数
          public Stack(int size){
                 stackArray = new char [size];
                 top = -1; //初始化栈的时候,栈内无元素,栈顶下标设为-1
                 this.size = size;
          }
         
          //入栈,同时,栈顶元素的下标加一
          public void push(char elem){
                 stackArray[++top] = elem; //插入栈顶
          }
         
          //出栈,删除栈顶元素,同时,栈顶元素的下标减一
          public char pop(){
                 return stackArray[top--];
          }
         
          //查看栈顶元素,但不删除
          public char peek(){
                 return stackArray[top];
          }
         
          //判空
          public boolean isEmpty(){
                 return (top == -1);
          }
         
          //判满
          public boolean isFull(){
                 return (top == size-1);
          }
         
    }
    然后写一个类来封装分隔符匹配的操作:
    public class BrecketChecker {
         
          private String input;  //存储待检查的字符串
         
          //构造方法,接受待检查的字符串
          public BrecketChecker(String in){
                 this.input = in;
          }
         
          //检查分隔符匹配的方法
          public void check(){
                 int strLength = input.length();
                 Stack stack = new Stack(strLength);
                
                 for(int i=0;i<strLength;i++){
                       
                        char ch =input.charAt(i);  //一次获取串中的单个字符
                       
                        switch(ch){
                               case '{' :
                               case '[' :
                               case '(' :
                                       //如果为左分隔符,压入栈
                                      stack.push(ch);
                                      break;
                               case '}' :
                               case ']' :
                               case ')' :
                                      //如果为右分隔符,与栈顶元素进行匹配
                                      if(!stack.isEmpty()){
                                             char ch = stack.pop();
                                            
                                             if((ch== '{' && chx != '}')||
                                                (ch == '(' && chx != ')')||
                                                (ch == '[' && chx != ']')
                                             ){
                                                    System.out.println("匹配出错!字符:"+ch+",下标:"+i);
                                             }
                                      }else{
                                             System.out.println("匹配出错!字符:"+ch+",下标:"+i);
                                      }
                                     
                               default :
                                      break;
                        }
                       
                 }
                
                 if(!stack.isEmpty()){
                        //匹配结束时如果栈中还有元素,证明右分隔符缺失
                        System.out.println("有括号没有关闭!");
                 }
          }
         
    }
    测试类
    public static void main(String[] args) {
                
                 System.out.println("输入需要检测的字符串:");
                 String str = getString();
                 BrecketChecker checker = newBrecketChecker(str);
                 checker.check();
          }
         
          public static String getString(){
                 String str = "";
                 try{
                        InputStreamReader reader =new InputStreamReader(System.in);
                        BufferedReader bReader = new BufferedReader(reader);
                        str = bReader.readLine();
                 }catch(IOException e){
                        e.printStackTrace();
                 }
                 return str;
          }
     

    三、队列

        栈是“后进先出”(LIFO,Last InFirst Out)的数据结构,与之相反,队列是“先进先出”(FIFO,First InFirst Out)的数据结构

    队列的作用就像售票口前的人们站成的一排一样:第一个进入队列的人将最先买到票,最后排队的人最后才能买到票

    在计算机操作系统或网路中,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当敲击键盘时,也有一个存储键盘键入内容的队列,如果我们敲击了一个键,而计算机又暂时在做其他事情,敲击的内容不会丢失,它会排在队列中等待,直到计算机有时间来读取它,利用队列保证了键入内容在处理时其顺序不会改变

    栈的插入和删除数据项的命名方法很标准,成为push和pop,队列的方法至今也没有一个标准化的方法,插入可以称作put、add或enque等,删除可以叫作delete、get、remove或deque等

    下面我们依然使用数组作为底层容器来实现一个队列的操作封装,与栈不同的是,队列的数据项并不都是从数组的第一个下标开始,因为数据项在数组的下标越小代表其在队列中的排列越靠前,移除数据项只能从队头移除,然后队头指针后移,这样数组的前几个位置就会空出来如下图所示:


    这与我们的直观感觉相反,因为我们排队买票时,队列总是向前移动,当前面的人买完票离开后,其他人都向前移动,而在我们的设计中,队列并没有向前移动,因为那样做会使效率大打折扣,我们只需要使用指针来标记队头和队尾,队列发生变化时,移动指针就可以,而数据项的位置不变

    但是,这样的设计还存在着一个问题,随着队头元素不断地移除,数组前面空出的位置会越来越多,当队尾指针移到最后的位置时,即使队列没有满,我们也不能再插入新的数据项了


    解决这种缺点的方法是环绕式处理,即让队尾指针回到数组的第一个位置:


    这就是循环队列(也成为缓冲环)。虽然在存储上是线形的,但是在逻辑上它是一个首尾衔接的环形


    public class Queue {
         
          private int [] queArray;
          private int maxSize;
          public int front;   //存储队头元素的下标
          public int rear;    //存储队尾元素的下标
          private int length; //队列长度
         
          //构造方法,初始化队列
          public Queue(int maxSize){
                 this.maxSize = maxSize;
                 queArray = new int [maxSize];
                 front = 0;
                 rear = -1;
                 length = 0;
          }
         
          //插入
          public void insert(int elem) throws Exception{
                 if(isFull()){
                        throw new Exception("队列已满,不能进行插入操作!");
                 }
                 //如果队尾指针已到达数组的末端,插入到数组的第一个位置
                 if(rear == maxSize-1){
                        rear = -1;
                 }
                 queArray[++rear] = elem;
                 length++;
          }
         
          //移除
          public int remove() throws Exception{
                 if(isEmpty()){
                        throw new Exception("队列为空,不能进行移除操作!");
                 }
                 int elem = queArray[front++];
                 //如果队头指针已到达数组末端,则移到数组第一个位置
                 if(front == maxSize){
                        front = 0;
                 }
                 length--;
                 returnelem;
          }
         
          //查看队头元素
          public int peek() throws Exception{
                 if(isEmpty()){
                        throw new Exception("队列内没有元素!");
                 }
                 return queArray[front];
          }
         
          //获取队列长度
          public int size(){
                 return length;
          }
         
          //判空
          public boolean isEmpty(){
                 return (length == 0);
          }
         
          //判满
          public boolean isFull(){
                 return (length == maxSize);
          }
         
    }

    还有一种称为双端队列的数据结构,队列的每一端都可以进行插入和移除操作。

    其实双端队列是队列和栈的综合体。如果限制双端队列的一段只能插入,而另一端只能移除,就变成了平常意义上的队列;如果限制双端队列只能在一端进行插入和移除,就变成了栈

    优先级队列

    像普通队列一样,优先级队列有一个队头和一个队尾,并且也是从队头移除数据,从队尾插入数据,不同的是,在优先级队列中,数据项按关键字的值排序,数据项插入的时候会按照顺序插入到合适的位置

    除了可以快速访问优先级最高的数据项,优先级队列还应该可以实现相当快的插入,因此,优先级队列通常使用一种称为堆的数据结构来实现。在下例中,简便起见,我们仍然使用数组来实现

    在数据项个数比较少,或不太关心速度的情况下,用数组实现优先级队列还可以满足要求,如果数据项很多,或对速度要求很高,采用堆是更好的选择

    优先级队列的实现跟上面普通队列的实现有很大的区别。

    优先级队列的插入本来就需要移动元素来找到应该插入的位置,所以循环队列那种不需要移动元素的优势就不太明显了。在下例中,没有设置队头和队尾指针,而是使数组的第一个元素永远是队尾,数组的最后一个元素永远是队头,为什么不是相反的呢?因为队头有移除操作,所以将队头放在数组的末端,便于移除,如果放在首段,每次移除队头都需要将队列向前移动

                                                                                      插入元素示意图

     

                                                                                                 

                                                                                                    移除元素示意图


    在下例中,我们设置了一个基准点,认为元素到里基准点的距离越近则优先级越高,如设置的基准点为2,3到2的距离就是|3-2|=1,而-1到2的距离是|-1-2|=3,所以2的优先级就比-1要高

    public class PriorityQueue {
         
          private int [] queArray;
          private int maxSize;
          private int length; //队列长度
          private int referencePoint;  //基准点
         
          //构造方法,初始化队列
          public PriorityQueue(int maxSize,intreferencePoint){
                 this.maxSize= maxSize;
                 this.referencePoint =referencePoint;
                 queArray = new int [maxSize];
                 length = 0;
          }
         
          //插入
          public void insert(int elem) throws Exception{
                 if(isFull()){
                        throw new Exception("队列已满,不能进行插入操作!");
                 }
                
                 //如果队列为空,插入到数组的第一个位置
                 if(length == 0){
                        queArray[length++] = elem;
                 }else{
                        int i;
                        for(i=length;i>0;i--){
                              
                               int dis =Math.abs(elem-referencePoint);  //待插入元素的距离
                               int curDis =Math.abs(queArray[i-1]-referencePoint); //当前元素的距离
                              
                               //将比插入元素优先级高的元素后移一位
                               if(dis>= curDis){
                                      queArray[i] =queArray[i-1];
                               }else{
                                      break;
                               }
                        }
                        queArray[i] = elem;
                        length++;
                 }
          }
         
          //移除
          public int remove() throws Exception{
                 if(isEmpty()){
                        throw new Exception("队列为空,不能进行移除操作!");
                 }
                 int elem = queArray[--length];
                 return elem;
          }
         
          //查看队头元素
          public int peek() throws Exception{
                 if(isEmpty()){
                        throw new Exception("队列内没有元素!");
                 }
                 return queArray[length-1];
          }
         
          //返回队列长度
          public int size(){
                 return length;
          }
         
          //判空
          public boolean isEmpty(){
                 return (length == 0);
          }
         
          //判满
          public boolean isFull(){
                 return (length == maxSize);
          }
         
    }
    转载: https://blog.csdn.net/column/details/datastructureinjava.html
    展开全文
  • 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 ...
  • 事件循环 JavaScript 语言的一大特点就是单线程,也就是说,同一个时间只能做一件事。为了协调事件、用户交互、脚本、UI 渲染和网络处理等行为,防止主线程的不阻塞,Event Loop 的方案应用而生。...任务队列
  • YTask -- Go 异步任务队列

    千次阅读 2019-09-06 10:26:41
    YTask 是 Go 的异步任务队列,比起其他框架更方便快捷。 架构图: 特性: 支持几乎所有类型,包括基本类型(int, floalt, string),数组切片,结构体以及复杂的结构体嵌套。 注册任务,调用任务一行代码完成...
  • Spark程序任务队列

    千次阅读 2019-10-24 09:54:38
    一、当前Spark程序所有分析任务的信息获取 1、打开swagger-ui随机点选五个分析(我在原Hadoop项目加了几个单词统计分析做实验,这里使用单词统计分析主要考虑不需要连接HBase可直接本地IDEA运行,Jar包集群环境跑...
  • linux c消息队列实现

    2019-04-02 14:06:53
    如果要改代码,只要把键值改一下,结构体储存要发送的消息的那个数组对应改成自己想发送的值,就可以很好的实现功能。接收端同样按环境变量设置的键值读取指定消息队列,接收消息。 两个程序都能在linux下 跑通,要...
  • 队列队列算法实现:使用数组队列队列算法实现:使用链表队列 队列算法实现:使用数组队列 队列是一种受限的线性表 队列算法实现:使用链表队列
  • 数据结构与算法(java版)之队列一(数组模拟队列) 1 队列 队列是一个有序的列表,可以使用数组或者链表来实现,遵循先入先出的原则。即先存入数据先去取出来,后存入数据后取出来 2 数组模拟队列 2.1思路分析 1)...
  • 任务队列简单实现

    千次阅读 2019-03-27 19:18:02
    实用场景: 例子1: 例子2: 生产者-----消费者 之间 C/C++ .h #ifndef __TASK_QUEUE_H__ #define __TASK_QUEUE_H__ ... // 任务处理函数 void* param; // 附加参数 }Task_t; ty...
  • 此篇文章讲解一下Netty中的任务队列.这里说的任务队列是Netty中的IO线程对应的任务队列. 在Netty中NioEventLoopGroup这个类相当于线程池,而由它创建的每个NioEventLoop相当于池中的线程,因为每个NioEventLoop都是和...
  • BlockingQueue只是一个接口,它所表达的是当队列为空或者已满的时候,需要阻塞以等待生产者/消费者协同操作并唤醒线程。其有很多不同的具体实现类,各有特点。有的可以规定队列的长度,也有一些则
  • 异步任务队列的两种处理方法

    千次阅读 2017-10-09 13:34:53
    针对这种要异步处理(等待)的任务队列管理模式,个人理解有两种处理方法。 第一种:  也是最常规的一种,定义一个队列,创建任务,然后push到队列里面去,每个任务创建之后,(或接到开启命令)启动等
  • c++数组实现循环队列

    千次阅读 2016-05-23 19:01:54
    像栈一样,队列(queue)也是表。然而,使用队列时插入在一端进行而删除则在另一端进行,也就是先进先出(FIFO)。...同样,队列也可以由链表或数组实现,特点分析如下:(时空矛盾) 链表:不需要设定
  • ThreadPoolExecutor参数解析 之前学习线程池,发现线程池大致有四种创建方法: ...newScheduledThreadPool 创建一个可周期性调度任务的线程池 public static ExecutorService newFixedThreadPool(int nThreads
  • 队列中的最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我 们需要在这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要把这个任务队列中移除。...
  • 数组队列和链表队列

    2013-04-20 12:08:11
    无论使用数组还使用链表来实现队列,都是要实现几个基本的任务,例如添加,取出,删除和插入等。他们的区别在于使用的形式不同。 用数组实现队列的关键是创建两个数组,在实现类的内部,还是使用数组保存装入的...
  • Redis2:任务队列,用于暂存Redis中没有summary,需要进行处理获取summary, 队列用的Redis的list结构 两个进程: 1、 进程1:服务进程 接收请求,划内链词,然后从Redis1中去获取词的summary, 如果获取失败,...
  • 线程池原理--任务队列BlockingQueue

    千次阅读 2018-10-15 09:18:50
    文章目录线程池原理--任务队列BlockingQueue 线程池原理–总索引 线程池原理–任务队列BlockingQueue
  • 任务队列适用在什么场景下? 高并发 日常情况中,如果并发数超过一定数量,会导致数据出错,系统奔溃,如果一台破电脑同时要执行10W个复杂同步或异步函数会怎样,同样是运行10W个函数如果用队列控制并发运行数,...
  • 题目 直接上代码洛 #include <stdio.h> #include <stdlib.h> #include <string.h> # define LEN 10000 ...//结构体数组 int head,tail,n; void enqueue(p x){ Q[tail] = x; tail = (tail+1)%
  • 用Kotlin语言实现队列的先入先出 fun main() { // 创建一个队列 val mq = MyQueue() // 入队 mq.add(1) mq.add(2) mq.add(3) mq.add(4) // 打印队列 mq.show() // 出队 println(mq.poll()) mq.show() } ...
  • 可以保证当任务被取消时,立刻从任务队列移除。 * <p>Successive executions of a task scheduled via * {@code scheduleAtFixedRate} or * {@code scheduleWithFixedDelay} do not overlap. While different * ...
  • Redis实现任务队列

    2017-03-28 15:52:37
    实现任务队列之前,我们先了解一下使用任务队列有哪些好处:  1. 松耦合。生产者和消费者无需知道彼此的实现细节,只需要约定好任务的描述格式。这使得生产者和消费者可以由不同的团队使用不同的编程语言编写。  ...
  • 分布式后台任务队列模拟(Golang)

    千次阅读 2015-03-24 14:12:50
    fmt.Println("分布式后台任务队列模拟(一)...") //Job Server js := jobserver.NewJobServer() //模拟Worker端注册 js.RegisterWorkerClass("mail", mailWorker) js.RegisterWorkerClass("log", ...
  • 栈、队列等其他数据结构均由数组演变而来。下图是一个包含元素(1,2,3和4)的简单数组数组长度为4。 每个数据元素都关联一个正数值,我们称之为索引,它表明数组中每个元素所在的位置。大部分语言将初始索引...
  • 数组 数组(Array)是一种很常见的数据结构。它是由相同类型的元素(element)的集合所组成,并且被分配一块连续的内存来存储(与链表对比)。利用元素的索引(index)可以计算出该元素对应的存储地址。它的特点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 112,869
精华内容 45,147
关键字:

任务队列数组