队列和栈

见贤思齐

队列和栈 411 一、定义和概念顺序队列队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列特点：先进先出三种溢出现象：（1）下溢：队列为空，出队，正常。可用作条件逻辑判断（2）真上溢：队列满，入队，异常，需要避免（3）假上溢：队列实际不满，但由于对头指针只增不减，空间无法重复利用，导致虚满，无法正常入队，可通过循环队列解决循环队列循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。在循环队列中，当队列为空时，有 front=rear，而当所有队列空间全占满时，也有 front=rear。为了区别这两种情况，规定循环队列最多只能有 MaxSize-1 个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是 front=rear，而队列判满的条件是 front = (rear+1)%MaxSize（1）a,b,c,d,e 入队（2）a,b 出队，对头指针指向 c（3）假设队列 maxSize=6，插入 e 之后就出现假上溢，这时候 f 要入队，由于 a，b 元素已经出队位置空闲，所以 f 插入存储空间的第一个位置，将 f 设置为队尾。依次循环能避免假上溢的情况出现，从而将队列循环装满。空对接判断条件：front = rear满队列判断条件：(rear + 1) % MAXSIZE = front为什么判断队列是否满的条件是 front = (rear+1)%MaxSize？（1）正常情况判满条件是 rear+1=front（2）有一种特殊情况，队列满了之后 rear+1=0，所以当队列满足了一个 maxSize 的轮回的时候会就归 0，所以此处需要根据 maxSize 取余，即 (rear+1)%MaxSize = front栈栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为出栈/退栈（POP）。栈也称为先进后出表。栈空的条件：因为指针从 0 开始，所以栈满的条件为 top == -1栈满的条件：因为指针从 0 开始，所以栈满的条件为 top==maxsize-1溢出现象：（1）下溢：栈为空，出栈，正常。可用作条件逻辑判断（2）真上溢：栈满，入队，异常，需要避免，不存在跟队列类似的假上溢的情况。堆栈的基本特点：（1）先入后出，后入先出。（2）除头尾节点之外，每个元素有一个前驱，一个后继。二、算法实现循环队列定义数组存储元素，定义队头指针和队尾指针1、数组大小定义为元素个数 +12、队列判空：front == rear3、队列判满：front == (rear + 1) % maxSize4、入队：当前队尾指针指向的空间存储元素，队尾指针 +15、出队：返回当前队头元素，队头指针 +1import java.util.Arrays;import java.util.stream.Collectors;public class CircleQueue {  /**   * 数组长度   */  private int maxSize;  /**   * 队头指针   */  private int front;  /**   * 队尾指针   */  private int rear;  private String[] queue;  /**   * 初始化循环队列   * @param objSize 元素个数   */  public CircleQueue(int objSize) {    // 循环队列为了区分空队列和满队列，所以多预留一个空元素空间，这里的maxSize比元素个数多1    this.maxSize = objSize + 1;    this.front = 0;    this.rear = 0;    this.queue = new String[this.maxSize];  }  /**   * 队列是否空   * @return   */  public boolean isEmpty() {    return front == rear;  }  /**   * 队列是否满   * @return   */  public boolean isFull() {    return front == (rear+1) % maxSize;  }  /**   * 入队   * @param a 入队元素   */  public void add(String a) {    if (isFull()) {      System.out.println("队列满");      return;    }    queue[rear%maxSize] = a;    rear = (rear+1)%maxSize;  }  /**   * 出队   * @return 出队元素   */  public String remove() {    if (isEmpty()) {      System.out.println("队列空");      return null;    }    String a = queue[front%maxSize];    queue[front%maxSize] = null;    front = (front+1)%maxSize;    return a;  }  public static void main(String[] args) {    // 模拟一个4个元素大小队列的入队出队情况    // a,b,c入队；【正常，元素a,b,c，front=0，rear=3】    // a出队；【正常，元素b,c，front=1，rear=3】    // d,e入队；【正常，元素b,c,d,e front=1，rear=0】// 循环队列    // f入队；【异常，队列满】    // b,c,d,e出队【正常，队列空 front=0，rear=0】    CircleQueue circleQueue = new CircleQueue(4);    System.out.print("a,b,c入队:");    circleQueue.add("a");    circleQueue.add("b");    circleQueue.add("c");    System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "front=" + circleQueue.front + "；rear" + circleQueue.rear);    System.out.print("a出队:");    String remove1 = circleQueue.remove();    System.out.println(remove1 + "；" + Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "front=" + circleQueue.front + "；rear" + circleQueue.rear);    System.out.print("d,e入队:");    circleQueue.add("d");    circleQueue.add("e");    System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "front=" + circleQueue.front + "；rear" + circleQueue.rear);    System.out.print("f入队:");    circleQueue.add("f");    System.out.println(Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "front=" + circleQueue.front + "；rear" + circleQueue.rear);    System.out.print("b,c,d,e出队:");    String remove2 = circleQueue.remove();    String remove3 = circleQueue.remove();    String remove4 = circleQueue.remove();    String remove5 = circleQueue.remove();    System.out.println(remove2+","+remove3+","+remove4+","+remove5+","+"；" + Arrays.stream(circleQueue.queue).collect(Collectors.toList()) + "front=" + circleQueue.front + "rear" + circleQueue.rear);  }}执行结果：顺序栈定义数组存储元素，定义栈顶指针1、数组大小定义为元素个数2、栈判空：top == -13、栈判满：top == maxSize -14、入栈：当前栈顶指针 +1，栈顶指针指向的空间存储元素5、出栈：返回当前栈顶指针指向的元素，栈顶指针 -1package cn.gov.zcy.announcement;import java.util.Arrays;import java.util.stream.Collectors;public class Stack {  // 数组长度  private int maxSize;  /**   * 栈顶指针   */  private int top;  private String[] stack;  /**   * 初始化栈   * @param objSize 元素个数   */  public Stack(int objSize) {    maxSize = objSize;    top = -1;    stack = new String[maxSize];  }  /**   * 判断栈是否空   * @return   */  public boolean isEmpty() {    return top == -1;  }  /**   * 判断栈是否满   * @return   */  public boolean isFull() {    return top == maxSize-1;  }  /**   * 入栈   * @param a 入栈元素   */  public void push(String a) {    if (isFull()) {      System.out.println("栈满");      return;    }    top = top + 1;    stack[top] = a;  }  /**   * 出栈   * @return 出栈元素   */  public String pop() {    if (isEmpty()) {      System.out.println("栈空");      return null;    }    String a = stack[top];    top = top - 1;    return a;  }  public static void main(String[] args) {    // 模拟一个4个元素大小栈的入栈和出栈的情况    // a,b,c,d入栈【正常，元素a,b,c,d，top=3】    // e入栈【异常，栈满】    // d,c,b,a出栈【正常，出栈顺序d,c,b,a，top=-1】    // 出栈【异常，栈空】    Stack test = new Stack(4);    System.out.print("a,b,c,d入栈：");    test.push("a");    test.push("b");    test.push("c");    test.push("d");    System.out.println(Arrays.stream(test.stack).collect(Collectors.toList()) + "；top=" + test.top);    System.out.print("e入栈：");    test.push("e");    System.out.println(Arrays.stream(test.stack).collect(Collectors.toList()) + "；top=" + test.top);    System.out.print("d,c,b,a出栈：");    String pop1 = test.pop();    String pop2 = test.pop();    String pop3 = test.pop();    String pop4 = test.pop();    System.out.println(pop1 + "," + pop2 + "," + pop3 + "," + pop4 + "," + "；top=" + test.top);    System.out.print("空栈出栈：");    String pop5 = test.pop();    System.out.println(pop5 + "；top=" + test.top);}}执行结果：队列思想应用实践应用背景一批已经发布的公告数据需要推送，且推送时间点需要满足发布后 10 分钟队列实现介质：数据库表队列实现先进先出：按照修改时间正序排序入队：插入数据库表出队：删除数据库表重新入队：更新修改时间，通过重新入队可以解决已经被处理过并且处理异常的数据可以轮到后续的定时任务中处理总结队列和栈的定义和概念都比较简单，但队列和栈的思想都经过包装了各种介质被广泛应用。参考文献1.《百度百科》