堆栈和队列|帕拉帕拉博客园

堆栈只有一个开口，最先进入的将在底部，随后进入的将在前面. 如果要取出，则必须从开口端取出.

所以先入先出，后进先出.

数据结构:

java实现堆栈（基于数组）:

/**
 * 栈只有一个开口,先进去的就到最底下,后进来的就在前面,要是拿出去的话,肯定是从开口端拿出去,
 * 所以说先进后出，后进先出。
 */
public class MyStack {
    //底层实现是一个数组
    private long[] arr;
    /**
     * 最上层的一个指针 栈顶
     */
    private int top;
    /**
     * 默认的构造方法
     */
    public MyStack(){
        arr = new long[10];
        top=-1;
    }
    /**
     * 增加数据 先把指针加一
     * 然后指针指向最新的数据
     */
    public void push(int value){
        //top++是top先不自加，在语句完后自加。| ++top先自加 然后使用top的值
        arr[++top] = value;
    }
    
    /**
     * 移除数据 先把最顶层指针执行的数据return 然后指针减一
     */
    public long pop(){
        //--top 是先执行top=top-1,然后再使用top的值 | top-- 是先使用top的值 然后 在执行top=top-1
        return arr[top--];
    }
    
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.pop());
    }
}

在main（）方法中，3是要进入的最后一个push（）. 它是第一个出现的pop（），第一个到最后一个，最后一个到第一个.

队列有一个开头和结尾. 数据从队列末尾进入队列，然后退出队列. 队列的开头指向队列中的第一个数据栈和队列，队列的末尾指向队列. 最后的数据.

队列的数据结构

java实现队列（基于数组）

package javaee.net.cn.tree.ch10;
public class MyQueue {
    //底层使用数组
    private long[] arr;
    //队头
    private int front;
    //队尾
    private int end;
    
    /**
     * 默认构造方法
     */
    public MyQueue(){
        arr = new long[10];
        front=0;
        end = -1;
    }
    /**
     * 添加数据 从队尾插入
     */
    public void insert(long value){
        arr[++end] = value;
    }
    /**
     * 删除数据，从队头删除
     */
    public long remove(){
        return arr[front++];
    }
    
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.insert(1L);
        myQueue.insert(2L);
        System.out.println(myQueue.remove());
    }
}

main（）方法中的1是先插入（），然后先去除（），所以先入先出.

JDK中的LinkedList（底层实现是一个链表）

上面的队列是由一个数组模拟的（相对简单）. JDK API中的Queue队列的底层是由链表实现的.

LinkedList类实现Deque（双端队列）接口，并且具有

addFirst（）addLast（）getFirst（）getLast（）removeFirst（）removeLast（）方法

使LinkList可以用作堆栈队列和双向队列

关于LinkedList的实现原理，我在这里不再赘述. 您可以参考API.

链接列表

以上堆栈和队列被实现为数组模拟，但是JDK中的LinkedList被实现为链接列表. 现在，我们来看看什么是链表.

链接列表由节点组成. 节点分为两部分. 第一部分（数据）存储或显示有关该节点的信息，另一部分存储下一个节点的地址.

链表中最后一个节点的存储地址部分指向空值.

节点:

/**
 * 连接点 相当于是车厢
 */
public class Node {
    //数据域 保存数据
    public long data;
    
    //指针域 保存下一个节点的引用
    public Node next;
    
    public Node(long value){
        this.data=value;
    }
}

插入节点. 对于单向链接列表，我们仅在链接列表的开头提供插入. 只需指向原始头节点旁边栈和队列，然后将当前插入的节点设置为头节点即可.

    /**
     * 插入一个节点，在头结点进行插入
     */
    public void insertFirst(long value){
        Node node = new Node(value);
        node.next=first;
        first=node;
    }

要删除一个节点，我们在该节点的上一个节点旁边指向该节点的下一个节点.

如果删除的头是头节点，则将头节点的下一个节点直接分配给头节点

    /**
     * 删除方法 根据数据域进行删除
     */
    public Node delete(long value){
        Node current = first;
        Node pre = null;
        while(current.data!=value){
            if(current.next==null){
                return null;
            }
            pre = current;
            current= current.next;
        }
        if(current == first){
            first = first.next;
        }else{
            pre.next=current.next;
        }
        return current;
    }

公共队列不考虑线程之间的同步. 当多个线程操作同一队列时，将导致并发问题.

BlockingQueue接口继承了Queue接口. BlockingQueue接口为多个线程提供了四种处理方案，以使多个线程操作同一队列（用于无法立即满足但将来可能会满足的操作）

抛出异常

特殊值

不可用

不可用

第一个和第二个方案来自Queue接口，第三和第四个方案新添加到BlockingQueue接口.

例如，线程阻塞:

通过put（e）方法将元素添加到队列的末尾时，如果队列已满，则当前线程进入阻塞状态，并且直到队列具有添加元素的剩余能力时才退出阻塞.

通过take（）方法从队列的开头删除元素并返回元素时，如果队列为空，则当前线程进入阻塞状态，直到元素成功从队列中删除并返回为止.

java.util.concurrent包中的BlockingQueue接口主要具有以下实现类

LinkedBlockingQueue

ArrayBlockingQueue

PriorityBlockingQueue

DelayQueue

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-148434-1.html