java中关于堆Stack和队列的用法以及实践

一：什么是堆和队列

栈（Stack） 是一种 后进先出（LIFO：Last In First Out） 的数据结构。

队列（Queue) 是先进先出 (First In First Out, FIFO) 的数据结构，是最先进队列的元素一定最早出队列。

LIFO是最后进Stack的元素一定最早出Stack。如何做到这一点呢？只需要把队列的一端封死：

因此，Stack是这样一种数据结构：只能不断地往 Stack中压入（push） 元素，最后进去的必须最早弹出（pop） 来。

二：堆（Stack)的一些用法

Stack只有入栈和出栈的操作：

• 把元素压栈：push(E)；
• 把栈顶的元素“弹出”：pop()；
• 取栈顶元素但不弹出：peek()。

java中堆有如下用法

1：初始化

Stack stack=new Stack();

2：判断栈是否为空

isEmpty()

3：添加元素

push(E item)

4：获取栈顶值,元素不出栈(栈为空时抛异常)

peek();

5：是否存在Object obj

search(Object obj);

6:移除栈顶

pop();

7:其他方法

//获取stack长度
size()
//下标处添加
add(int index, E element)
//添加集合
addAll(Collection<? extends E> c)
//移除对象
remove(Object obj)
//根据下标移除对象
remove(int index)
//清空
clear()

三：队列的一些用法

      队列是一种特殊的线性表，遵循先入先出、后入后出的基本原则，一般来说，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，但是java的某些队列运行在任何地方插入删除；比如我们常用的 LinkedList 集合，它实现了Queue 接口，因此，我们可以理解为 LinkedList 就是一个队列；

队列主要分为阻塞和非阻塞，有界和无界、单向链表和双向链表之分；

阻塞和非阻塞
阻塞队列
          入列(添加元素)时，如果元素数量超过队列总数，会进行等待（阻塞），待队列的中的元素出列后，元素数量未超过队列总数时，就会解除阻塞状态，进而可以继续入列；
          出列(删除元素)时，如果队列为空的情况下，也会进行等待（阻塞），待队列有值的时候即会解除阻塞状态，进而继续出列；
          阻塞队列的好处是可以防止队列容器溢出；只要满了就会进行阻塞等待；也就不存在溢出的情况；
          只要是阻塞队列，都是线程安全的；
          

非阻塞队列
          不管出列还是入列，都不会进行阻塞，
          入列时，如果元素数量超过队列总数，则会抛出异常，
          出列时，如果队列为空，则取出空值；

一般情况下，非阻塞式队列使用的比较少，一般都用阻塞式的对象比较多；阻塞和非阻塞队列在使用上的最大区别就是阻塞队列提供了以下2个方法：

    出队阻塞方法 ： take()
    入队阻塞方法 ： put()
 

java队列接口继承图

 

队列常用方法
　　

     add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
　　remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
　　element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
　　offer       添加一个元素并返回true       如果队列已满，则返回false
　　poll         移除并返问队列头部的元素    如果队列为空，则返回null
　　peek       返回队列头部的元素             如果队列为空，则返回null
　　put         添加一个元素                      如果队列满，则阻塞
　　take        移除并返回队列头部的元素     如果队列为空，则阻塞
   drainTo(list)   一次性取出队列所有元素

知识点： remove、element、offer 、poll、peek 其实是属于Queue接口
 

四：栈和队列的实践（深度优先算法（Stack）和广度优先算法(Qqeue)）

深度优先遍历：深度优先遍历是图论中的经典算法。其利用了深度优先搜索算法可以产生目标图的相应拓扑排序表，采用拓扑排序表可以解决很多相关的图论问题，如最大路径问题等等。

广度优先遍历：广度优先遍历是连通图的一种遍历策略，因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域故得名。广度优先遍历是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止

​​​​​​​
 

 

深度优先搜索的步骤为：

（1）、首先节点 1 进栈，节点1在栈顶；
 
（2）、然后节点1出栈，访问节点1，节点1的孩子节点3进栈，节点2进栈；
 
（3）、节点2在栈顶，然后节点2出栈，访问节点2
 
（4）、节点2的孩子节点5进栈，节点4进栈
 
（5）、节点4在栈顶，节点4出栈，访问节点4，
 
（6）、节点4左右孩子为空，然后节点5在栈顶，节点5出栈，访问节点5；
 
（7）、节点5左右孩子为空，然后节点3在站顶，节点3出栈，访问节点3；
 
（8）、节点3的孩子节点7进栈，节点6进栈
 
（9）、节点6在栈顶，节点6出栈，访问节点6；
 
（10）、节点6的孩子为空，这个时候节点7在栈顶，节点7出栈，访问节点7
 
（11）、节点7的左右孩子为空，此时栈为空，遍历结束。

广度优先搜索的步骤为：

（1）、节点1进队，节点1出队，访问节点1
 
（2）、节点1的孩子节点2进队，节点3进队。
 
（3）、节点2出队，访问节点2，节点2的孩子节点4进队，节点5进队；
 
（4）、节点3出队，访问节点3，节点3的孩子节点6进队，节点7进队；
 
（5）、节点4出队，访问节点4，节点4没有孩子节点。
 
（6）、节点5出队，访问节点5，节点5没有孩子节点。
 
（7）、节点6出队，访问节点6，节点6没有孩子节点。
 
（8）、节点7出队，访问节点7，节点7没有孩子节点，结束。

代码如下：

/**
 * 二叉树节点的数据结构
 */
public class TreeNode {
	int data;
	TreeNode leftNode;
	TreeNode rightNode;
	public TreeNode() {
		
	}
	public TreeNode(int d) {
		data=d;
	}
	
	public TreeNode(TreeNode left,TreeNode right,int d) {
		leftNode=left;
		rightNode=right;
		data=d;
	}
	
 
}

广度和深度算法实现如下：

import java.util.*;
 
public class AI {
    public static void main(String[] args) {
        TreeNode head=new TreeNode(1);
        TreeNode second=new TreeNode(2);
        TreeNode three=new TreeNode(3);
        TreeNode four=new TreeNode(4);
        TreeNode five=new TreeNode(5);
        TreeNode six=new TreeNode(6);
        TreeNode seven=new TreeNode(7);
        head.rightNode=three;
        head.leftNode=second;
        second.rightNode=five;
        second.leftNode=four;
        three.rightNode=seven;
        three.leftNode=six;
        System.out.print("广度优先遍历结果：");
        new AI().BroadFirstSearch(head);
 
        System.out.println();
        System.out.print("深度优先遍历结果：");
        new AI().depthFirstSearch(head);
    }
 
    private void depthFirstSearch(TreeNode head) {
        if(head==null)
            return;
 
        Stack<TreeNode> myStack=new Stack<>();
        myStack.add(head);
        while(!myStack.isEmpty()) {
            TreeNode node=myStack.pop();    //弹出栈顶元素
            System.out.print(node.data+" ");
            if(node.rightNode!=null) {
                myStack.push(node.rightNode);    //深度优先遍历，先遍历左边，后遍历右边,栈先进后出
            }
            if(node.leftNode!=null) {
                myStack.push(node.leftNode);
            }
        }
    }
 
    private void BroadFirstSearch(TreeNode head) {
        if (head == null)
            return;
 
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(head);
 
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.data + " ");
            if (null != node.leftNode)
                queue.add(node.leftNode);
            if (null != node.rightNode)
                queue.add(node.rightNode);
        }
    }