Java栈和队列 Java数据结构学习之栈和队列
愿美梦成真 人气:0一、栈
1.1 概述
Java为什么要有集合类: 临时存储数据。
链表的本质: 对象间通过持有和引用关系互相关联起来。
线性表: 普通线性表, 操作受限线性表(某些操作受到限制 --> 某一个线性表它的增删改操作受到限制) --> 栈 & 队列
1.1.1 线性表的概念
(1)线性表:n个数据元素的有序序列。
①首先,线性表中元素的个数是有限的。
②其次,线性表中元素是有序的。
(2)那这个”序”指的是什么呢?
①除表头和表尾元素外,其它元素都有唯一前驱和唯一后继,其唯一前驱或唯一后继确定了该元素在线性表中的位置。
②因此,线性表中,每个数据元素都有一个确定的位序,这个确定的位序我们称之为索引。 表头元素有唯一后继,无前驱,表尾元素有唯一前驱,无后继。
1.1.2 栈的概念
栈是一种”操作受限”的线性表,体现在只能在一端插入和删除数据,符合FILO的特性。
FILO: 先进后出,
LIFO: 后进先出
1.1.3 栈的应用
线性表和哈希表在以后工作中会最常用。
栈在实际工作中不常用
应用场景:
1.函数调用栈
2.反序字符串: 实现reNumber(str)方法,反转字符串(附代码) 。
public class DemoStack1 { public static void main(String[] args) { String str = "123456789"; String reStr = reStr(str); System.out.println(reStr); } // 栈先进后出 public static String reStr(String str){ MyArrayStack<Character> stack = new MyArrayStack<>(); for (int i = 0; i < str.length(); i++) { stack.push(str.charAt(i)); } StringBuffer buffer = new StringBuffer(); // 1 2 3 4 5 6 7 8 9 while (!stack.isEmpty()){ Character pop = stack.pop(); buffer.append(pop); } return buffer.toString(); } }
3.括号匹配问题: 实现judgeBracket(str)方法来判断括号匹配 (附代码)。
public class DemoStack2 { public static void main(String[] args) { String str = "public class) DemoStack2 {public static void main(String[] args) {}}"; boolean bool = judgeBracket(str); System.out.println(bool); } public static boolean judgeBracket(String str){ MyArrayStack<Character> stack = new MyArrayStack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); // 判断c 是left括号, 然后入栈 if (c == '{'){ stack.push('}'); } else if (c == '['){ stack.push(']'); }else if (c == '('){ stack.push(')'); } else if (c == '}' || c == ')' || c == ']'){ Character pop = stack.pop(); if (c != pop){// 不匹配 return false; } } } return stack.isEmpty(); } }
4.编译器利用栈实现表达式求值
5.浏览器的前进后退功能
6. 利用栈实现 DFS: depth-first-search 深度优先遍历(树 图)
编译器利用栈实现表达式求值
中缀表达式: 2 + 3 * 2 给人看的 , 运算符放到中间
前缀表达式: + 2 * 3 2 运算符放到之前
后缀表达式: 2 3 2 * + 运算符放到后面
// 中缀表达式转化为后缀:
// 遍历中缀表达式
// 遇到操作数输出
// 遇到操作符, 出栈, 直到遇到更低优先级的操作符, 操作符入栈
// 遍历完成, 全部弹栈
// 中缀表达式转化为前缀:
// 遍历中缀表达式: 逆序遍历
// 遇到操作数输出: 头插法
// 遇到操作符, 出栈, 只弹出更高优先级的操作符, 操作符入栈
// 遍历完成, 全部弹栈
二、队列
2.1 队列的概念
队列也是一种”操作受限”的线性表,体现在一端插入数据在另一端删除数据,特性是FIFO。
2.2 队列的实现
实现一个集合类
集合类: 数据容器
底层: 数组 or 链表
数据结构表现: 队列
(1)用数组实现一个队列。
/** * 用数组实现一个队列 * 集合类角度: 数据容器 * 底层: 数组 * 表示: 队列 */ public class MyArrayQueue <T> { private final int MAX_CAPACITY = Integer.MAX_VALUE - 8; private final int INIT_CAPACITY = 16; private Object[] objs; private int size; private int head;// 头的下标 private int end;// 尾的下标 public MyArrayQueue(){ objs = new Object[INIT_CAPACITY]; } public MyArrayQueue(int initCapcity){ if (initCapcity <= 0 || initCapcity > MAX_CAPACITY) throw new IllegalArgumentException("" + initCapcity); objs = new Object[initCapcity]; } public boolean offer(T t){ // 如果数组满了 if (size == objs.length){ int newLen = getLen(); grow(newLen); } // 可以添加 if (isEmpty()){ // 没有任何元素存储: 新添加的元素就是唯一的元素 objs[head] = t; end = head; size++; return true; } else { // 原本存储就有内容 // 尾后移一位 end = (end + 1) % objs.length; objs[end] = t; size++; return true; } } private void grow(int newLen) { Object[] newArr = new Object[newLen]; for (int i = 0; i < objs.length; i++) { int index = (head + i) % objs.length; newArr[i] = objs[index]; } objs = newArr; head = 0; end = size - 1; } private int getLen() { int oldLen = objs.length; int newLen = oldLen << 1; // 判断新长度是否溢出 if (newLen <= 0 || newLen > MAX_CAPACITY){ newLen = MAX_CAPACITY; } // 如果新长度和旧长度一样 if (newLen == oldLen)throw new RuntimeException("stack can not add"); return newLen; } public T poll(){ if (isEmpty()) throw new RuntimeException("queue is empty"); if (size == 1){ // 原队列中只剩一个元素 T oldValue = (T)objs[head]; head = 0; end = 0; size--; return oldValue; } else { // 队列中超过一个元素 T oldValue = (T)objs[head]; head = (head + 1) % objs.length; size--; return oldValue; } } public T peek(){ if (isEmpty()) throw new RuntimeException("queue is empty"); return (T)objs[head]; } public int size() { return size; } public boolean isEmpty(){ return size == 0; } }
(2)用链表实现一个链表。
public class MyLinkedQueue <T> { private Node head;// 队头 private Node end; // 队尾 private int size; // 添加 offer // 删除 poll // 查看队头元素 peek public boolean offer(T t){ // 如果原队列为空 if (isEmpty()){// 原队列空 // 让头尾都指向这个新加的结点 head = new Node(t, null); end = head; size++; return true; } // 原队列不空 // 把这个元素添加到队尾 end.next = new Node(t, null); end = end.next;// end后移 size++; return true; } public T poll(){ if (isEmpty()) throw new RuntimeException("queue is empty"); if (size == 1){ // 代表着, 链表中只有一个元素 T oldVlaue = head.value; head = null; end = null; size--; return oldVlaue; }else { T oldVlaue = head.value; head = head.next; size--; return oldVlaue; } } public T peek(){ if (isEmpty()) throw new RuntimeException("queue is empty"); return head.value; } public boolean isEmpty(){ return size == 0; } public int size(){ return size; } class Node{ T value; Node next; public Node(T value, Node next) { this.value = value; this.next = next; } } }
2.3 队列的应用
(1)队列更不常用(自己写代码使用不常用):
(2)常见, 很多jdk源码, 中间件的源码上 很多地方使用了队列
Eg:
①生产者消费者问题
生产者 – 消费者
生产者: 厨师
消费者: 吃面包的人
桌子: 放面包的地方
②线程池
线程池: 任务
生产者: 产生任务
消费者: 线程
桌子: 队列
③生态环境:
第三方轮子: 要看懂
Maven
④消息队列和缓存。
(3)普通队列的应用场景是很有限的,一般在工程中用到的是阻塞队列。
①阻塞队列(有一个队列, 大小一定):常用于生产者-消费者模型中。
当队列满的时候,入队列就阻塞。
当队列空的时候,出队列就阻塞。
②利用队列实现 BFS:breadth first search 广度优先搜索/ 遍历 ()
加载全部内容