栈和队列的实现（Java篇）

---

一、栈的概念

栈： 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶

出栈：栈的删除操作叫做出栈。出数据在栈顶

二、栈的实现

栈是一个特殊的顺序表,所以采用链表和数组的方式都可实现,但是,一般采用数组的方式实现

创建一个类：

	public class MyStack {
	//创建一个数组
    public int[] elem;
    //存放的元素个数
    public int usedSize;
    //默认的容量
    public static final int DEFAULT_CAPACITY = 5;
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
}    

2.1压栈(push)

在入栈之前我们要判断栈是否满了，如果满了就要进行扩容

public boolean isFull() {
    return usedSize == elem.length;
}    

public void push(int val) {
    //判断
    if(isFull()) {
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    elem[usedSize] = val;
    usedSize++;
}  

2.2出栈(pop)

同样在出栈的时候我们也要判断栈是否为空，为空就抛一个异常

public int pop() {
    //判断
    if(isEmpty()) {
        throw new EmptyStackException("栈为空");
    }
    int ret = elem[usedSize-1];
    usedSize--;
    return ret;
}    

2.3获取栈顶元素(peek)

在获取栈顶元素时也要判断栈是否为空

public int peek() {
    //判断
    if (isEmpty()) {
        throw new EmptyStackException("栈为空");
    }
    return elem[usedSize-1];
}    

2.4判断栈是否为空(isEmpty)

public boolean isEmpty() {
    return usedSize == 0;
}    

栈的实现测试

public class Test {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(12);
        myStack.push(23);
        myStack.push(34);
        myStack.push(45);//压栈
        int ret = myStack.pop();//出栈
        System.out.println(ret);
        System.out.println("*****");
        int num = myStack.peek();//获取栈顶元素
        System.out.println(num);
        System.out.println("*****");
        System.out.println(myStack.isEmpty());//判断栈是否为空
    }
}

三、队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

四、队列的实现

要想实现一个队列,可以采用链表和数组两种存储数据的方式,那么到底应该用哪种方式实现
对于数组来说,入队列和出队列操作都相对简单,但是可能会造成空间大量浪费，那么我们就可以选择使用链表来实现

创建一个类：

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
}

4.1入队(offer)

因为是链表所以在入队时不用考虑扩容的问题，代码执行时动态分配空间

public void offer(int val) {
    ListNode node = new ListNode(val);
    if(head == null) {
        head = last = node;
    }else {
    last.next = node;
    node.prev = last;
    last = node;
    }
}    

4.2出队(poll)

出队时要判断队头是否为空

public int poll() {
    //判断
    if(head == null) {
        return -1;
    }
    int val = -1;
    if(head.next == null) {
        val = head.val;
        head = null;
        last = null;
        return val;
    }
    val = head.val;
    head = head.next;
    head.prev = null;
    return val;
}    

4.3判断队列是否为空

 public boolean empty() {
     return head == null;
}    

4.4获取对头元素

public int peek() {
    if(head == null) {
        return -1;
    }
    return head.val;
}    

队列的实现测试

public class Test {
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.offer(12);
        queue.offer(23);
        queue.offer(34);
        queue.offer(45);//入队
        int ret = queue.poll();//出队
        System.out.println(ret);
        System.out.println("*****");
        System.out.println(queue.empty());//判断队列是否为空
        System.out.println("*****");
        int num = queue.peek();//获取队头元素
        System.out.println(num);
    }
}    

五、循环队列

实际中我们有时还会使用一种队列叫循环队列,循环队列通常使用数组实现。
利用数组实现一个队列可能会浪费大量的空间,那么,就可以使用循环队列,也能解决资源浪费的问题.

循环队列其本质也是一个数组

那我们如何区分空与满呢
1.通过添加 size 属性记录
2.保留一个位置
3.使用标记
这里我们使用第二种方式

5.1入队

因为是使用数组来实现的，所以在入队之前我们要判断队列是否满了

public boolean isFull() {
    return (rear+1)% elem.length == front;
}    

入队操作

public boolean enQueue(int value) {
    //判断
    if (isFull()) {
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    elem[rear] = value;
    rear = (rear+1)%elem.length;
    return true;
}    

5.2出队

在进行出队操作时要判断队列是否为空

public boolean deQueue() {
    if (isEmpty()) {
        return false;
    }
    front = (front+1)%elem.length;
    return true;
}    

5.3获取队头元素

public int Front() {
    if (isEmpty()) {
        return -1;
    }
    return elem[front];
}    

5.4获取队尾元素

 public int Rear() {
     if (isEmpty()) {
         return -1;
     }
     return elem[rear];
}    

5.5判断队列是否为空

front和rear相遇了就为空

public boolean isEmpty() {
    return front == rear;
}    

六、双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队

Deque是一个接口，使用时必须创建LinkedList的对象
Deque接口比较多，栈和队列都可以使用该接口

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现