数据结构学习
| english | chinese |
|---|---|
| basics | 基础 |
| require | 需要 |
| query | 查询 |
| illegal | 非法的 |
| contain | 包含 |
| heneric | 泛型 |
| structures | 结构 |
| loop | 环 |
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
百度百科的解释。
第一次接触的人肯定会看得头大。我用大白话来解释一下栈。
就跟手枪压子弹，发射子弹一样。
出栈
入栈
如上图，子弹只能从弹夹上边一次压进去，同时也只能从弹夹上边出来。最先进去的子弹，被压在最底下。最后进去的子弹，在最上边。射出时，最上边（最后进去的）的先出去，最下边的（最先进去的）后出来。
类似这种操作，放到计算机上，就是栈。
对一个数组，操作时，放元素，只放在最后，取元素，只取最后一个。就是栈。（运算受限的线性表）
栈的用处：
用电脑写文档或者文字的时候，就是把文字压到栈里边（入栈），然后可以进行撤销操作，（出栈）
例题：
力扣-题号-20-https://leetcode-cn.com/problems/valid-parentheses/
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
class Solution {
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
char c ;
char a;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') st.push(c);
else {
if (st.isEmpty()) return false;
a = st.pop();
if((c == ')' && a != '(') ||(c == ']' && a != '[') ||(c == '}' && a != '{')) return false;
}
}
return st.isEmpty();
}
}补充：Java栈的使用
// 声明
Stack<type> stack = new Stack<>();方法摘要：
| 方法摘要 | |
|---|---|
boolean |
empty() 测试堆栈是否为空。 |
E |
peek() 查看堆栈顶部的对象，但不从堆栈中移除它。 |
E |
pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象。 |
E |
push(E item) 把项压入堆栈顶部。 |
int |
search(Object o) 返回对象在堆栈中的位置，以 1 为基数。 |
队列的理解
视频原地址：https://v.qq.com/x/page/b0541ueiuen.html
看到上边的gif了吧，队列整体，就相当与一个管子，而每一个元素就是貂，
入队就是钻进去，出队就是钻出来，而且只能是先进的先出。
队列的基本功能
队列的具体实现是对数组进行操作，所以 基本队列可以分为：
- 普通数组队列
- 链表数组队列
队列的特性
由以上可总结出一些队列的特性：
- 队列是线性结构
- 队列的操作是数组操作的子集
- 只能从对尾添加元素，只能从队首取出元素
解释高级队列前，先来看普通队列出队：
出队之后，后边所有的元素都要往前移，时间复杂度为O(n)级别，那么，如果我们能避免往前移这个操作，时间复杂度不久是O(1)了吗？
由此设计出了一个更高级的队列：
第一个元素被移除后，把二个元素当作队首，第二个元素被移除后，把三个元素当作队首，这样就避免了所有元素往前移的操作，但是这样前边的位置就空了，空间有浪费。
如果，后边存满，我们往前边空的位置存，这样就可以解决空间浪费问题了。这就是循环队列
怎么实现呢？
我们只需要标识一下队首和队尾不就可以实现了！
看一下图示：
入队操作
出队操作
再入队：
重点来了，后边存满了，咱们该往前边空的地方存了！
但是具体到代码实现上，你会发现我们始终都多申请了一个位置，这个位置就是用来判满的。
这样我们只需要判断 (tail + 1) % data.length == front就可以知道是否存满。
如果不留，判空、调整数组大小会变得比较复杂。感兴趣的可以自行百度。这里只讲简单实现。