一.栈（Stack）

*栈也是一种线性表结构

*相比数组，栈对应的操作是数组的子集

*栈的元素从一端进、同一端出，且为后进先出，Last In First Out（LIFO）

 

1.栈的应用：

——各种编辑器中无处不在的undo（撤销）操作

——程序调用的系统栈

2.栈的基本实现：

先创建一个接口Stack<E>：

public interface Stack
     
       {    int getSize(); //栈的大小    boolean isEmpty(); //判断栈是否为空    void push(E e); //入栈    E pop(); //出栈    E peek(); //查看栈顶元素}
     

 

创建类ArrayStack<E>实现接口，实现栈的基本功能：

public class ArrayStack
     
       implements Stack
      
       {    private Array
       
         array;        //有参构造函数    public ArrayStack(int capacity) {        array = new Array
        
         (capacity);    }    //无参构造函数    public ArrayStack() {        array = new Array
         
          ();    }        @Override    public int getSize() {        return array.getSize();    }    @Override    public boolean isEmpty() {        return array.isEmpty();    }    @Override    public void push(E e) {        array.addLast(e);    }    @Override    public E pop() {        return array.removeLast();    }    @Override    public E peek() {        return array.getLast();    }        public int getCapacity(){        return array.getCapacity();    }        @Override    public String toString(){        StringBuilder res = new StringBuilder();        res.append("Stack: ");        res.append('[');        for(int i = 0 ; i < array.getSize() ; i ++){            res.append(array.getArr(i));            if(i != array.getSize() - 1)                res.append(", ");        }        res.append("] top");        return res.toString();    }    }
         
        
       
      
     

 

用栈的原理解决刮花是否正确的成对出现的问题：

import java.util.Stack;class Solution {    public boolean isValid(String s){        Stack
     
       stack = new Stack<>();        for(int i=0; i
     

 

二.队列（Queue）

1.什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。即First In First Out （FIFO）。

2.实现数组队列：

public class ArrayQueue
     
       implements Queue
      
        {        private Array
       
         queue;        public ArrayQueue(int capacity) {        queue = new Array
        
         (capacity);    }    public ArrayQueue() {        queue = new Array
         
          ();    }        @Override    public int getSize() {        return queue.getSize();    }    @Override    public boolean isEmpty() {        return queue.isEmpty();    }    @Override    public void enqueue(E e) {        queue.addLast(e);    }    @Override    public E dequeue() {        return queue.removeFirst();    }    @Override    public E getFront() {        return queue.getFirst();    }        public int getCapacity(){        return queue.getCapacity();    }        @Override    public String toString(){        StringBuilder ret = new StringBuilder();        ret.append("Queue： ");        ret.append("front [");        for(int i=0; i
          
            queue = new ArrayQueue<>(); for(int i=0; i<10; i++){ queue.enqueue(i); if(i % 3 ==0) queue.dequeue(); System.out.println(queue); } }}
          
         
        
       
      
     

 

3.实现循环队列：

public class LoopQueue
     
       implements Queue
      
        {    private E[] arr;    private int front;    private int tail;    private int size;        public LoopQueue(int capacity) {        arr = (E[])new Object[capacity+1];        front = 0;        tail = 0;        size = 0;    }        public LoopQueue() {        this(10);    }        @Override    public int getSize() {        return size;    }    @Override    public boolean isEmpty() {        return tail==front;    }    @Override    public void enqueue(E e) {        if((tail + 1) % arr.length == front)            resize(getCapacity()*2);        arr[tail] = e;        tail = (tail + 1) % arr.length;        size++;    }    @Override    public E dequeue() {         if(isEmpty())             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");         E ret = arr[front];         arr[front] = null;         front = (front + 1) % arr.length;         size--;         if(size == getCapacity() / 4 && getCapacity() / 2 != 0)                resize(getCapacity() / 2);         return ret;    }    @Override    public E getFront() {        // TODO Auto-generated method stub        return null;    }        public int getCapacity(){        return arr.length - 1;    }        public void resize(int newCapacity){        E[] newArr = (E[])new Object[newCapacity + 1];        for(int i=0; i
       
         queue = new LoopQueue<>();            for(int i = 0 ; i < 10 ; i ++){                queue.enqueue(i);                System.out.println(queue);                if(i % 3 == 2){                    queue.dequeue();                    System.out.println(queue);                }            }        }}