栈的模拟实现

一:什么是栈

栈是以先进后出(后进先出)的形式来组织数据结构
比如:
先装入的子弹后射出,后装入的子弹先射出,这就是一种典型的栈.

二:IStack 接口

在这个Stack接口中定义了一些常用的方法

public interface IStack {
    //入栈(尾插)
    void push(int x);
   //出栈(尾删)
    int pop();
   //获取栈顶元素

    int peek();
    //获取栈中元素个数
    int size();
     //栈是否为空
    boolean empty();
 //栈是否满了
    boolean full();

}

三:MyStack类:

栈与顺序表相似,底层一般是用数组来组织的:
所以栈有两个成员变量:int[] elem,int usedSize;

1:push(int x):

入栈(尾插):
在入栈之前我们要检查数组是否满了,如果满了,需要扩容,(以二倍容量扩容),然后在usedSize处插入元素,usedSize++即可;

ublic void push(int x) {
        if(full()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=x;
        usedSize++;
    }

2:pop()

出栈(尾删):
删除一个元素,首先栈不能为空,栈为空在这里我们报异常信息(自定义异常),然后记录最后一个元素,再usedSize–,返回刚刚记录的元素即可

 public int pop() {
        if(empty()){
            throw new EmptyException("栈为空");
        }
        int old=elem[usedSize-1];
        usedSize--;
        return old;
    }

自定义异常类:

public class EmptyException extends RuntimeException{
    public EmptyException() {

    }

    public EmptyException(String message) {
        super(message);
    }
}

3:peek()

获取栈顶元素,但不删除;
如果栈为空,报异常
由于只是获取最后一个元素,并不删除,返回最后一个元素即可.

 public int peek() {
        if(empty()){
            throw new EmptyException("栈为空");
        }
        return elem[usedSize-1];

    }

4:size(),empty(),full()

public int size() {
        return usedSize;
    }

    @Override
    public boolean empty() {
        return usedSize==0;
    }

    @Override
    public boolean full() {
        return usedSize==elem.length;
    }

三:

public class MyStack implements IStack{
    private int[] elem;
    private int usedSize;

    public MyStack() {
        elem=new int[10];
    }

    @Override
    public void push(int x) {
        if(full()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=x;
        usedSize++;
    }

    @Override
    public int pop() {
        if(empty()){
            throw new EmptyException("栈为空");
        }
        int old=elem[usedSize-1];
        usedSize--;
        return old;
    }

    @Override
    public int peek() {
        if(empty()){
            throw new EmptyException("栈为空");
        }
        return elem[usedSize-1];

    }

    @Override
    public int size() {
        return usedSize;
    }

    @Override
    public boolean empty() {
        return usedSize==0;
    }

    @Override
    public boolean full() {
        return usedSize==elem.length;
    }
}

四:栈的时间复杂度:

数组实现栈:入栈和出栈的时间复杂度都是O(1);
双向链表实现栈:
(1):头插,头删:时间复杂度均为O(1)
(2):尾插,尾删:时间复杂度均为O(1)
单链表实现栈:
(1)头插,头删:时间复杂度均为O(1)
(2)尾插,尾删:时间复杂度均为O(N)