栈

栈是一种只能在一端进行插入和删除的线性数据结构。主要有进栈(Push)和出栈(POP)两个操作。

- 栈的存储结构

栈一般使用一段连续的空间进行存储，通常预先分配一个长度，可以简单地使用数组去实现，具体的存储结构如下图所示：

- 栈的特点

只能在一端进行操作，在遵循先进后出(FILO,First In Last Out)或后进先出(LIFO,Last In First Out)的原则.

栈的代码实现

应考虑到扩容与异常的情况

package edu.xatu1;

import java.util.Arrays;

public class Stack {
    private int size = 0;
    private int[] array;

    public Stack(){
        this(10);
    }

    public Stack(int i) {
        if(i <= 0){
            i = 10;
        }
        array = new int[i];
    }
    /**
     * 入栈
     * @param item入栈的值
     */
    public void push(int item){
        if(size == array.length){
            array = Arrays.copyOf(array, size*2);  //扩容
        }
        array[size++] = item;
    }
    /**
     * 获取栈顶元素，但不出栈
     * @return
     */
    public int peek(){
        if(size == 0){
            throw new  IndexOutOfBoundsException("栈已为空"); //异常情况
        }
        return array[size - 1];
    }
    /**
     * 出栈，同时获取栈顶元素
     * @return
     */
    public int pop(){
        int i = peek();
        size--;//直接使元素个数减1，不需要真的清除元素，下次入栈会覆盖旧元素的值
        return i;
    }
    /**
     * 栈是否已满
     * @return
     */
    public boolean isFull(){
        return size == array.length;
    }
    /**
     * 栈是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }
}

测试代码：

package edu.xatu1;

public class StackTest {
    public static void main(String[] args) {
        Stack stack = new Stack(1);//设定初始长度为1
        stack.push(1);
        stack.push(2);
        System.out.println("栈内的元素个数(当前数组长度为2)：  "+stack.size());
        stack.push(3);
        System.out.println("栈内的元素个数(当前数组长度为4)：   "+stack.size());
        System.out.println("获取的栈顶元素："+stack.peek());
        System.out.println("获取栈顶元素后的栈内的元素个数(仅获取未出战)：    "+stack.size());

        System.out.println("出栈元素：    "+stack.pop());
        System.out.println("出栈元素：    "+stack.pop());
        System.out.println("出栈后的元素个数：     "+stack.size());
    }

}

运行结果：

---

队列

队列就是一个队伍。队列和栈一样，由一段连续的存储空间组成，是一个具有自身特殊规则的数据结构。我们将没有元素的队列称为空队。队列主要有数组和链表两种实现方式。用数组实现队列有两种方式，一种是顺序队列，一种循环队列。

- 队列的存储结构

顺序队列有两个标记：队头位置(head)和队尾位置(tail),开始两者都指向数组下标为0的位置。

在插入元素之后，tail标记将会增加，比如入队A,B,C三个元素，当前存储情况如图所示：

出队操作：出队一个元素时，head指向的位置则加1.如图所示：

在顺序队列中:

①队列中的元素个数=tail - head；

②当head = tail时，队列为空队；

③当tail达到数组长度，即队列存储之外的位置时，说明这个队列已经无法容纳其他元素入队了。空间是否都满了？没有，由于两个标记都只增不减，所以两个标记最终都会到数组的最后一个元素之外，这时数组时空，但也无法再往队列里加入元素了。

当队列五大加入元素时，我们称之为“上溢”；当顺序队还有空间却无法入队时，称为“假上溢”；如果空间真满了，称为“真上溢”；如果队列没有元素，依然在执行出队操作，则不能出队，称为“下溢”。

如何解决顺序队列的“假上溢”？ 采用循环队列

顺序队列出现的“假上溢”，即说明数组前端仍有空间。此时，我们可以吧指向数组外的标记，让它重新指向开始处即可。如下图示例：


循环队列中出现的情况：无论是队列没有元素还是队列已满，head都等于tail。
如何区分这两种状态？ 规定循环队列中队列的长度为数组长度为1，即有一个位置不放元素。因此：

①当head = tail 时，队列为空；

②当head = (tail + 1) % length 时，队满。

队列的特点

先进先出(FIFO),出队的一端是队头，入队的一端是队尾。

顺序队列的代码实现

package edu.xatu1;

import java.awt.ItemSelectable;

public class ArrayQueue {
    private final Object[] items;
    private int head = 0;
    private int tail = 0;

    /**
     * 初始化队列
     * 
     * @param capacity队列的长度
     */
    public ArrayQueue(int capacity) {
        this.items = new Object[capacity];
    }

    /**
     * 入队
     * 
     * @param item
     * @return
     */
    public boolean put(Object item) {
        if (head == (tail + 1) % items.length) {
            // 说明队满
            return false;
        }
        items[tail] = item;
        tail = (tail + 1) % items.length;// tail标记向后移动一位
        return true;
    }

    /**
     * 获取队头元素，不出队
     * 
     * @return
     */
    public Object peek() {
        if (head == tail) {
            // 队列为空
            return null;
        }
        return items[head];
    }

    /**
     * 出队
     * 
     * @return
     */
    public Object poll() {
        if (head == tail) {
            return null;
        }

    Object item = items[head];
    items[head]=null; //把没用的元素赋值空值

    head = (head+1)%items.length;//head标记向后移一位
    return item;
    }

    public boolean isFull(){
        return head ==(tail +1)% items.length;
    }
    public boolean isEmpty(){
        return head == tail;
    }

    public int size(){
        if(tail >= head){
            return tail - head;
        }else {
            return tail + items.length - head;
        }
    }
}

今天的你有收获了吗？想知道队列如何实现的吗？自己写个测试代码测试一下吧！：）