一堆栈
1.1 概念
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。
栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
图片来源于《算法面试通过 40 讲》
1.2 实例
Talk is cheap, show you the code.
/** * @program: Algorithm * @description: 数据结构-堆栈练习之基于数组实现的顺序栈。代码来自《数据结构与算法之美》 * @author: NickCheng * @create: 2021-02-21 21:16 **/
public class StackTest { private String[] arrays; private int count = 0;//栈元素个数 private int n = 0;//栈的大小
public StackTest(int n ){ this.arrays = new String[n]; this.n = n; this.count = 0; }
//入栈 public boolean push(String item){ // 数组空间不够了，直接返回false，入栈失败。 if (count == n) return false; // 将item放到下标为count的位置，并且count加一 arrays[count] = item; ++count; return true; }
//出栈 public String pop(){ // 栈为空，则直接返回null if (count == 0) return null; // 返回下标为count-1的数组元素，并且栈中元素个数count减一 String tmp = arrays[count-1]; --count; return tmp; }}
复制代码
二队列
2.1 概念
队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
图片来源于《算法面试通过 40 讲》
2.2 实例
/** * @program: Algorithm * @description: 用数组实现的顺序队列。代码来自《数据结构与算法之美》 * @author: NickCheng * @create: 2021-02-21 21:32 **/
public class ArrayQueue { // 数组：items，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0;
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; }
}
复制代码
评论