java栈和队列

• 1.栈(Stack)
• • 1.1基本概念
  • 1.2栈的实现
• 2. 队列(Queue)
• • 2.1基本概念
  • 2.2实现
  • 2.3循环队列
• 3.双端队列
• • 3.1基本概念

1.栈(Stack)

1.1基本概念

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

1.2栈的实现

1.栈的核心操作
pop():移除栈顶元素。
peek():查看栈顶元素单但不删除。
push():向栈中添加元素。

2.栈的应用实例
(1)操作系统栈：方法调用过程-方法调用栈。
(2)浏览器的前进后退。
(3)编辑器的撤销crt+z(输入栈)。
(4)代码编辑器的括号匹配。
(5)算数运算的符号优先级匹配(双栈)
3.栈的底层实现有两种
(1)基于数组实现：顺序栈。
(2)基于链表实现：链式栈
4.在实际应用中当需要使用最近原则时用栈结构。
5.代码实现：
(1)Stack.java:

package stack_queue.stack;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Stack<E> {
    private E[] elementData;
    //当前栈中的实际元素个数
    private int size;
    public Stack() {
        elementData=(E[]) new Object[10];
    }
    public Stack(int initCap) {
        elementData = (E[]) new Object[initCap];
    }

    //入栈操作
    public void push(E value){
        elementData[size]=value;
        size++;
    }
    //出栈操作，返回原先的栈顶元素
    public E pop(){
        if (getSize() == 0) {
            // 当前栈为空
            throw new NoSuchElementException("栈为空!");
        }
        E oldValue=elementData[size-1];
        size--;
        elementData[size]=null;
        return oldValue;
    }
    //查看栈顶元素，不出栈
    public E peek(){
        if(getSize()==0){
            throw new NoSuchElementException("栈为空!");
        }
        return elementData[size-1];
    }

    private int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        for (int i = 0; i <size ; i++) {
            sb.append(elementData[i]);
            if(i!=size-1){
                sb.append(",");
            }
        }
        sb.append("]top");
        return sb.toString();
    }
}

(2)StackTest.java:

package stack_queue.stack;
public class StackTest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(3);
        stack.push(5);
        stack.push(7);
        // [1,3,5,7] top
        System.out.println(stack);
        // 7
        System.out.println(stack.peek());
        stack.pop();
        // [1,3,5] top
        System.out.println(stack);
    }
}

(3)

2. 队列(Queue)

2.1基本概念

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

2.2实现

1.队列的底层实现有两种：
(1)基于数组的队列;循环队列。
(2)基于链表的队列：由于队首元素删除时若采用数组实现每次出队后都需要进行数组元素的搬移工作，非常耗时效率会比较低。因此我们采用链表实现队列。
2.队列的核心操作:
(1)offer():向队列中添加元素。
(2)poll():移除队首元素 。
(3)peek():查看队首元素但不删除。

3.代码实现：
(1)Queue.java(接口):

package stack_queue.queue;

public interface Queue {
    //入队操作
    void offer(int value);
    //出队操作
    int poll();
    //查看队首元素
    int peek();
}

(2)LinkedQueue.java:

package stack_queue.queue.impl;
import stack_queue.queue.Queue;
import java.util.NoSuchElementException;

// 基于链表的队列
// 队首出，队尾进
public class LinkedQueue implements Queue {
    private Node head;
    private Node tail;
    private int size;
    private class Node {
        private int data;
        private Node next;
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 入队操作
     * @param value
     */
    @Override
    public void offer(int value) {
        //产生一个新元素
        Node node = new Node(value);
        if (head == null) {
            head = tail = node;
        }else {
            tail.next = node;
            tail = node;
        }
        size ++;
    }

    //出队
    @Override
    public int poll() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        int oldValue = head.data;
        Node tmpHead = head;
        head = head.next;
        tmpHead.next = null;
        size --;
        return oldValue;
    }

    //查看队首素，但不出队
    @Override
    public int peek() {
        if (size == 0) {
            throw new NoSuchElementException("队列为空!");
        }
        return head.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        Node node = head;
        while (node != null) {
            sb.append(node.data);
            if (node.next != null) {
                sb.append(",");
            }
            node = node.next;
        }
        sb.append("] tail");
        return sb.toString();
    }
}

(3)QueueTest.java:

package stack_queue.queue;
import stack_queue.queue.impl.LinkedQueue;

public class QueueTest {
    public static void main(String[] args) {
        Queue queue=new LinkedQueue();
        queue.offer(1);
        queue.offer(3);
        queue.offer(5);
        queue.offer(7);
        //front[1,3,5,7]tail
        System.out.println(queue);
        queue.poll();
        //front[3,5,7]tail
        System.out.println(queue);
        System.out.println(queue.peek());
    }
}

(4)运行截图：

2.3循环队列

1.循环队列：
由于顺序队列每次在出队时，都会牵扯到数组头部的删除(O(1)),还要进行元素的搬移工作，非常耗时，效率比较低，因此我们采用循环队列。

3.双端队列

3.1基本概念

1.双端队列（deque）：是指允许两端都可以进行入队和出队操作的队列，那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。