Java数据结构学习之栈和队列

Java数据结构学习之栈和队列

一、栈

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 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 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 {

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 THllCJYaL 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 {

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）普通队列的应用场景是很有限的，一般在工程中用到的是阻HllCJYaL塞队列。

①阻塞队列(有一个队列, 大小一定)：常用于生产者-消费者模型中。

当队列满的时候，入队列就阻塞。

当队列空的时候，出队列就阻塞。

②利用队列实现 BFS:breadth first search 广度优先搜索/ 遍历 ()

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。