实现一个栈和队列

首先说明什么是栈和队列。
栈的话是一个先进后出，后进先出的数据结构。鉴于我们目前学了链表，所以我们有两种实现栈的方式，顺栈和链栈。

image.png

队列的话，正好相反，是一种先进先出，后进后出的数据结构，同样我们有两种方式实现。顺队列和链队列。

image.png

顺栈实现

首先我们要定义什么属性？既然是数组实现，那要有数组吧。既然是数组，那栈的容量就是确定的，要有栈的容量最大值吧。因为我要控制后进先出和数组循环利用，要有个类似指针的东西吧，我们以数组下标为索引控制。

那么我们的属性，呼之欲出了。

package 顺栈;
/**
 * 
 * @author xuxiao
 *
 */
public class MyArrayStack {
     private Object[] data;
     private int maxSize;
     private int top=-1;
}

OK了，什么？你问top是什么？top是栈顶指针，为什么是-1？emmm。。

因为数组下标是从0开始的。。

接下来我们写构造吧，我们希望在创建实例时即完成数组的初始化，那么我们这样写：

public MyArrayStack() {
         this(10);
     }
    public MyArrayStack(int initialSize) {
         if(initialSize >=0){
                this.maxSize = initialSize;
                data = new Object[initialSize];
                top = -1;
            }else{
                throw new RuntimeException("初始化大小不能小于0：" + initialSize);
            }
    }

设置栈深度为10，（别说数组容量了，我们在写栈！专业一点。）

我们在来想我们的类里要暴露出什么样的api给用户调用？
首先，来一个判空吧（isEmpty），让用户知道我们的栈里有没有数据。
再然后肯定要进栈啊（push），然后出栈啊（pop），查看栈顶元素啊（peek）再然后来个根据对象来查询该对象在栈中什么位置啊（search）。

差不多了，就这些吧，我们一个个来写。
判空和当前存储容量，很简单

public boolean isEmpty() {
        return top==-1?true:false;
    }
public int getSize() {
        return size;
    }

查看栈顶元素，也很简单

public Object peek() {
        if(top==-1)
             throw new RuntimeException("栈为空！");
        return data[top];       
    }

接下来写进栈和出栈吧，都很简单

public boolean push(Object o) {
        if(top == maxSize -1)
            throw new RuntimeException("栈已满，无法将元素入栈！");
        data[top++]=o;
        return true;
    }
    public Object pop() {
        if(top==-1)
             throw new RuntimeException("栈为空！");
        return data[top--];     
    }

最后写根据实例查询其在堆栈的位置（以1为基准）

public int search(Object o) {
        int i=top;
        while(top != -1){
            if(peek() != o){
                top --;
            }else{
                break;
            }
        }
        int result = top+1;
        top = i;
        return result;      
    }

顺栈的完整代码如下：

package 顺栈;

public class MyArrayStack {
     private Object[] data;
     private int maxSize;
     private int size;
     private int top=-1;//栈顶指针
     public MyArrayStack() {
         this(10);
     }
    public MyArrayStack(int initialSize) {
         if(initialSize >=0){
                this.maxSize = initialSize;         
                data = new Object[initialSize];
                top = -1;
            }else{
                throw new RuntimeException("初始化大小不能小于0：" + initialSize);
            }
    }
    public boolean isEmpty() {
        return top==-1?true:false;
    }
    public int getSize() {
        return size;
    }
    public Object peek() {
        if(top==-1)
             throw new RuntimeException("栈为空！");
        return data[top];       
    }
    public boolean push(Object o) {
        if(top == maxSize -1)
            throw new RuntimeException("栈已满，无法将元素入栈！");
        data[top++]=o;
                size++;
        return true;
    }
    public Object pop() {
        if(top==-1)
             throw new RuntimeException("栈为空！");
        return data[top--];     
    }
    public int search(Object o) {
        int i=top;
        while(top != -1){
            if(peek() != o){
                top --;
            }else{
                break;
            }
        }
        int result = top+1;
        top = i;
        return result;      
    }
}

这样顺栈我们就撸完了。接下来是链栈，需要写的api和顺栈相同，我们就直接开搞了。
ps:不过有区别的是，链栈没有容量限制（你要说你把计算机内存都用完了当我没说。）所以就没有maxSize这个属性了，我们只统计size（当前容量）。
至于写内部类结点，基本操作啦，链表里都说过了。

package 链栈;
/**
 * 
 * @author xuxiao
 *
 * @param <T>
 */
public class MyLinkedStack<T> {
private Node<T> top;
private int size;
public MyLinkedStack() {
    top=new Node<T>();
    size=0;
}
private static class Node<T>{
    public T data;
    public Node<T> next;
    public Node() {
        this(null,null);
    }
    public Node(T data, Node<T> next) {
        super();
        this.data = data;
        this.next = next;
    }
}
}

接下来写判空，和当前容量

public int getSize() {
    return size;
}
public boolean isEmpty() {
    return size==0;
}

很简单吧，在接着写进栈出栈

public boolean push(T t) {
    //让top指向新创建的元素，新元素的next引用指向原来的栈顶
    Node<T> node = new Node<T>(t,top);
    top=node;
    size++;
    return true;
}
public T pop() {
    if(isEmpty())
        throw new RuntimeException("空栈异常");
    T result=top.data;
    //top指向下一个结点
    top=top.next;
    size--;
    return result;
}

差不多了，还差一个查看栈顶元素，补上吧

public T peek() {
    if(isEmpty())
        throw new RuntimeException("空栈异常！");
    return top.data;
}

至于根据实例查询在栈中位置，对于链栈来说没有意义，因为数组可以拿位置当索引用，链表拿位置干不了啥。这里就不要求写了，当然感兴趣的可以自己试着写下。
链栈的完整代码如下：

package 链栈;

public class MyLinkedStack<T> {
private Node<T> top;
private int size;


public MyLinkedStack() {
    top=new Node<T>();
    size=0;
}

private static class Node<T>{
    public T data;
    public Node<T> next;
    public Node() {
        this(null,null);
    }
    public Node(T data, Node<T> next) {
        super();
        this.data = data;
        this.next = next;
    }
}
public int getSize() {
    return size;
}
public boolean isEmpty() {
    return size==0;
}
public boolean push(T t) {
    //让top指向新创建的元素，新元素的next引用指向原来的栈顶
    Node<T> node = new Node<T>(t,top);
    top=node;
    size++;
    return true;
}
public T pop() {
    if(isEmpty())
        throw new RuntimeException("空栈异常");
    T result=top.data;
    //top指向下一个结点
    top=top.next;
    size--;
    return result;
}

public T peek() {
    if(isEmpty())
        throw new RuntimeException("空栈异常！");
    return top.data;
}

}

顺队列

队列要注意的是，我们是要先进先出的，所以我们需要让数组“循环利用”，因为不做循环利用的话，数组很快就被用完了。
除了这个，我们为了区别于栈，入队称为add，出队称为poll，大概就这样吧。
写代码，先是属性和构造，没啥好说的

package 顺队列;
public class MyArrayQueue {
/**
 * 
 * @author xuxiao
 *
 */
    private Object[] data=null;
    private int maxSize; //队列容量
    private int front;  //队列头，允许删除
    private int rear;   //队列尾，允许插入
    private int size;
  //构造函数
    public MyArrayQueue(){
        this(10);
    }
    public MyArrayQueue(int initialSize){
        if(initialSize >=0){
            this.maxSize = initialSize;
            data = new Object[initialSize];
            front = rear =0;
        }else{
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }
}

然后是判空和当前容量。

    public boolean isEmpty(){
        return getSize()==0;
    }
   public int getSize() {
        return size;
    }

然后是查询队首元素

public Object peek(){
        if(isEmpty()){
            throw new RuntimeException("空队列异常");
        }else{
            return  data[front];
        }    
    }

然后是入队和出队,注意要循环利用哦，到了数组尾部要循环到数组首部。

public boolean add(Object o){
        if(getSize()== maxSize){
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }else{
            rear=rear%getSize();
            data[rear++]=o;
            size++;
            return true;
        }
    }
    public Object poll() {
        if(isEmpty()) {
            throw new RuntimeException("空队列异常");
        }else {
            front=front%getSize();
            Object result=data[front++];
            return result;
        }
    }

最后给出完整代码吧

package 顺队列;
/**
 * 
 * @author xuxiao
 *
 */
public class MyArrayQueue {
    private Object[] data=null;
    private int maxSize; //队列容量
    private int front;  //队列头，允许删除
    private int rear;   //队列尾，允许插入
    private int size;
  //构造函数
    public MyArrayQueue(){
        this(10);
    }
    public MyArrayQueue(int initialSize){
        if(initialSize >=0){
            this.maxSize = initialSize;
            data = new Object[initialSize];
            front = rear =0;
        }else{
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }
  //判空
    public boolean isEmpty(){
        return getSize()==0;
    }
    public Object peek(){
        if(isEmpty()){
            throw new RuntimeException("空队列异常");
        }else{
            return  data[front];
        }    
    }
    public int getSize() {
        return size;
    }
    public boolean add(Object o){
        if(getSize()== maxSize){
            throw new RuntimeException("队列已满，无法插入新的元素！");
        }else{
            rear=rear%getSize();
            data[rear++]=o;
            size++;
            return true;
        }
    }
    public Object poll() {
        if(isEmpty()) {
            throw new RuntimeException("空队列异常");
        }else {
            front=front%getSize();
            Object result=data[front];
            return result;
        }
    }
}

ok，我们的顺队列也撸完了，最后一个链队列，我就直接给代码了，相信讲解了之前的，链队列不需要我讲解也能写出来。这里我就只给出完整的参考代码吧。有疑问的同学上课提出来，看博客有疑问的小伙伴评论区里提问，我看到就会回的。

package 链队列;
/**
 * 
 * @author xuxiao
 *
 * @param <T>
 */
public class MyLinkedQueue<T> {
    private Node<T> front;// 队列头，允许删除  
    private Node<T> rear;// 队列尾，允许插入  
    private int size; //队列当前长度 
    
    public MyLinkedQueue() {
        front=new Node<T>();
        rear=new Node<T>();
        size=0;
    }

    private static class Node<T>{
        public T data;
        public Node<T> next;
        public Node() {
            this(null,null);
        }
        public Node(T data, Node<T> next) {
            super();
            this.data = data;
            this.next = next;
        }   
    }  
    public int getSize() {
        return size;
    }
   public boolean isEmpty() {
       return getSize()==0;
   }
   //添加元素入队
   public boolean add(T x) {
       if(isEmpty()) {
           front=rear=new Node<T>(x,null);////只有一个节点，front、rear都指向该节点
       }
       else {
           Node<T> newNode=new Node<T>(x,null);
           rear.next=newNode;//让尾节点的next指向新增的节点
           rear=newNode;//以新节点作为新的尾节点
       }
       size++;
       return true;
   }
   //得到队首元素
   public T peek() {
       if(isEmpty())
           throw new RuntimeException("空队列异常");
       return front.data;     
   }
   //队首出队
   public T poll() {
       if(isEmpty())
           throw new RuntimeException("空队列异常");
       T result = front.data;
       front=front.next;
       size--;
       return result;
   }
}