美文网首页
栈&队列

栈&队列

作者: 麦兜的夏天 | 来源:发表于2019-05-31 23:34 被阅读0次

后进先出,先进后出,这就是典型的“栈”结构。

当一个数据集合只涉及在一段插入和删除数据,并且满足后进先出、先进后出的特点,我们就应该首选“栈”这种数据结构。

用数组实现的栈,叫做顺序栈,用链表实现的栈。叫做链式栈

// 基于数组实现的顺序栈
public class ArrayStack {
  private String[] items;  // 数组
  private int count;       // 栈中元素个数
  private int n;           // 栈的大小

  // 初始化数组,申请一个大小为 n 的数组空间
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入栈操作
  public boolean push(String item) {
    // 数组空间不够了,直接返回 false,入栈失败。
    if (count == n) return false;
    // 将 item 放到下标为 count 的位置,并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出栈操作
  public String pop() {
    // 栈为空,则直接返回 null
    if (count == 0) return null;
    // 返回下标为 count-1 的数组元素,并且栈中元素个数 count 减一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

栈的经典应用场景就是函数调用栈。操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。

为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗?
其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。
从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
栗子:A调用B,B又调用C,那么就需要先把C执行完,结果赋值给B中的临时变量,B的执行结果再赋值给A的临时变量,嵌套越深的函数越需要被先执行,这样刚好符合栈的特点,因此每次遇到函数调用,只需要压栈,最后依次从栈顶弹出依次执行即可。


队列

先进先出,就是典型的“队列”。
用数组实现的队列叫做顺序队列,用链表实现的队列叫做链式队列

队列作为一种非常基础的数据结构,应用非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。他们在很多偏底层系统、框架、中间件的开发中,起着关键作用。比如高性能队列 Disruptor、Linux 环形缓存,都用到了循环并发队列;Java concurrent 并发包利.用 ArrayBlockingQueue 来实现公平锁等。

  • 顺序队列
public class ArrayQueue {
  // 数组:items,数组大小:n
  private String[] items;
  private int n = 0;
  // head 表示队头下标,tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    
    String ret = items[head];
    ++head;
    return ret;
  }
}

  // 入队(存在问题:当tail移动到最右边的时候,即使数组中有空闲空间,也无法继续添加数据)
  public boolean enqueue(String item) {
    // 如果 tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }
  
  //入队 (当tail在最右边,且数组中有空闲空间,通过数据搬移来解决上面的问题)
  
   // 入队操作,将 item 放入队尾
  public boolean enqueue(String item) {
    // tail == n 表示队列末尾没有空间了
    if (tail == n) {
      // tail ==n && head==0,表示整个队列都占满了
      if (head == 0) return false;
      // 数据搬移
      for (int i = head; i < tail; ++i) {
        items[i-head] = items[i];
      }
      // 搬移完之后重新更新 head 和 tail
      tail -= head;
      head = 0;
    }
    
    items[tail] = item;
    ++tail;
    return true;
  }

  • 循环队列
    顺序队列中,当 tail 移动到数组的最右端的时候,会有数据搬移操作,这样入队操作性能会受到影响。循环队列可以解决这个问题。


    当tail等于7的时候,再向里面添加元素,tail会变成0.png
public class CircularQueue {
  // 数组:items,数组大小:n
  private String[] items;
  private int n = 0;
  // head 表示队头下标,tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}
  • 阻塞队列其实就是在队列的基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会阻塞,直到队列中有空的位置后再插入数据,然后再返回。其实就是一个“生产者-消费者模型”。

  • 并发队列就是线程安全的队列。对简单的实现方式是直接在入队和出队的方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者说取操作。基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。
    在入队前,获取tail位置,入队时比较tail是否发生变化,如果否,则允许入队,反之,本次入队失败。出队则是获取head位置,进行 CAS 原子操作。

相关文章

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 栈和队列

    用栈定义队列(出入栈) 用队列定义栈(数据队列和辅助队列)

  • 数据结构——栈和队列

    用数组实现栈和队列 用栈实现队列 用队列实现栈 栈和队列的经典算法题最小间距栈宠物收养所 数组实现栈和队列 用数组...

  • Swift 队列&栈 相关操作

    栈 LIFO(后进先出) 队列 FIFO(先进先出) 队列与栈相互的实现 栈 - 队列实现 队列 - 栈实现 相关...

  • 栈和队列

    栈和队列 本质上是稍加限制的线性表 栈和队列定义 栈顺序栈定义 链栈结点定义 队列顺序队列 链队列链队类型定义 链...

  • 算法-栈和队列算法总结

    栈和队列算法总结 1 模拟 1.1 使用栈实现队列 1.2 使用队列实现栈 2 栈的应用 2.1 栈操作 2.2 ...

  • 栈&队列

    一、栈&队列总结 栈/队列的应用接雨水验证栈序列滑动窗口的最大值 栈/队列的特殊实现用两个栈实现队列用两个队列实现...

  • 算法分析 [BFS、Greedy贪心] 2019-02-18

    队列 和 栈 232. 用栈实现队列 Implement Queue using Stacks双栈,出队列时,将i...

  • 队列之-队列实现栈

    一、队列实现栈核心算法概述 之前已经描述过了用栈实现队列的功能,见栈系列之-实现队列,那么同样队列也可以用来实现栈...

  • 数据结构 | 其三 栈和队列

    栈 java中栈继承了Vector 队列 2.1 普通队列 2.2 循环队列 2.3 优先级队列 2.4 阻塞队列...

网友评论

      本文标题:栈&队列

      本文链接:https://www.haomeiwen.com/subject/zovntctx.html