网站建设和管理中 经验,网站域名提交,衡水企业网站建设,附近学电脑培训班? 工欲善其事#xff0c;必先利其器。栈和队列 - Stack And Queue栈如何理解栈呢#xff1f;后进者先出#xff0c;先进者后出#xff0c;这就是典型的 栈 结构。04_栈和队列-栈结构从栈的操作特性上来看#xff0c;栈是一种“操作受限”的线性表#xff0c… ? 工欲善其事必先利其器。栈和队列 - Stack And Queue栈如何理解栈呢后进者先出先进者后出这就是典型的 栈 结构。04_栈和队列-栈结构从栈的操作特性上来看栈是一种“操作受限”的线性表只允许在一端插入和删除数据。事实上从功能上来说数组或者链表确实都可以替代栈但你要知道特定的数据结构是对特定场景的抽象而且数组或链表暴漏了太多的操作接口操作上的确灵活运用但同时使用时就变的不可控自然也就更容易出错。当某个数据集合只涉及在一端插入和删除数据并且满足后进先出、先进后出的特性就应该首选“栈”这种数据结构。实现栈既然数组或者链表可以替代栈那么同样的使用数组和链表可以实现栈。用数组实现的栈叫做顺序栈用链表实现的栈叫做链式栈。// 基于数组实现的顺序栈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; }}上面代码是拷贝网上的使用java的数组实现栈。了解了定义和基本操作那它的操作的时间、空间复杂度是多少呢不管是顺序栈还是链式栈存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中只需要一两个临时变量存储空间所以空间复杂度是 O(1)。注意这里存储数据需要一个大小为 n 的数组并不是说空间复杂度就是 O(n)。因为这 n 个空间是必须的无法省掉。所以我们说空间复杂度的时候是指除了原本的数据存储空间外算法运行还需要额外的存储空间。不管是顺序栈还是链式栈入栈、出栈只涉及栈顶个别数据的操作所以时间复杂度都是 O(1)。栈的应用 - 四则运算四则运算是编译器利用栈来实现的表达式求值。对于四则运算来说我们大脑可以很快的计算出来但是对于计算机而言理解四则运算本来就难。那么编译器如何通过栈来解决四则运算首先我们需要两个栈一个保存操作数一个保存运算符。从左向右遍历表达式当遇到数字我们就直接压入操作数栈当遇到运算符就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高就将当前运算符压入栈如果比运算符栈顶元素的优先级低或者相同从运算符栈中取栈顶运算符从操作数栈的栈顶取 2 个操作数然后进行计算再把计算完的结果压入操作数栈继续比较。04_栈和队列-四则运算队列栈是后进先出那有没有先进先出的呢当然有就是队列。先进先出这就是典型的“队列”栈只支持两个基本操作入栈 push()和出栈 pop()。队列跟栈非常相似支持的操作也很有限最基本的操作也是两个入队 enqueue()放一个数据到队列尾部出队 dequeue()从队列头部取一个元素。04_栈和队列-队列所以队列跟栈一样也是一种操作受限的线性表数据结构。队列的概念很好理解基本操作也很容易掌握。作为一种非常基础的数据结构队列的应用也非常广泛特别是一些具有某些额外特性的队列比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中起着关键性的作用。比如高性能队列 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 boolean enqueue(String item) { // 如果tail n 表示队列已经满了 if (tail n) return false; items[tail] item; tail; return true; } // 出队 public String dequeue() { // 如果head tail 表示队列为空 if (head tail) return null; // 为了让其他语言的同学看的更加明确把--操作放到单独一行来写了 String ret items[head]; head; return ret; }}对于栈来说我们只需要一个栈顶指针就可以了。但是队列需要两个指针一个是 head 指针指向队头一个是 tail 指针指向队尾。当 a、b、c、d 依次入队之后队列中的 head 指针指向下标为 0 的位置tail 指针指向下标为 4 的位置。当我们调用两次出队操作之后队列中 head 指针指向下标为 2 的位置tail 指针仍然指向下标为 4 的位置。04_栈和队列-队列运行随着不停地进行入队、出队操作head 和 tail 都会持续往后移动。当 tail 移动到最右边即使数组中还有空闲空间也无法继续往队列中添加数据了。在数组那一节我们也遇到过类似的问题就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎么解决的吗对用数据搬移!每次进行出队操作都相当于删除数组下标为 0 的数据要搬移整个队列中的数据这样出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。实际上我们在出队时可以不用搬移数据。如果没有空闲空间了我们只需要在入队时再集中触发一次数据的搬移操作。所以改造下上面的代码后 // 入队操作将item放入队尾 public boolean enqueue(String item) { // tail n表示队列末尾没有空间了 if (tail n) { // tail n head0表示整个队列都占满了 if (head 0) return false; // 数据搬移 for (int i head; i items[i-head] items[i]; } // 搬移完之后重新更新head和tail tail - head; head 0; } items[tail] item; tail; return true; }从代码中我们看到当队列的 tail 指针移动到数组的最右边后如果有新的数据入队我们可以将 head 到 tail 之间的数据整体搬移到数组中 0 到 tail-head 的位置。04_栈和队列-队列数据搬移出队操作的时间复杂度仍然是 O(1)但是入队操作时需要使用前面提到的时间复杂度中的摊还分析时间复杂度仍是 O(1) 。循环队列刚才用数组来实现队列的时候在 tailn 时会有数据搬移操作这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢我们来看看循环队列的解决思路。循环队列顾名思义它长得像一个环。原本数组是有头有尾的是一条直线。现在我们把首尾相连扳成了一个环。如下图所示04_栈和队列-循环队列队列应用队列这种数据结构很基础平时的业务开发不大可能从零实现一个队列甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛比如阻塞队列和并发队列。阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说就是在队列为空的时候从队头取数据会被阻塞。因为此时还没有数据可取直到队列中有了数据才能返回如果队列已经满了那么插入数据的操作就会被阻塞直到队列中有空闲位置后再插入数据然后再返回。线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁但是锁粒度大并发度会比较低同一时刻仅允许一个存或者取操作。实际上基于数组的循环队列利用 CAS 原子操作可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。历史系列文章算法与数据结构(四)- 链表算法与数据结构(三)- 数组算法与数据结构(二)- 算法分析算法与数据结构(一)- 概述
