Java,  算法和数据结构

如何实现栈这种数据结构

零 栈这种数据结构的特征

  • 依然是一种线性数据结构;
  • 规定只能在一端操作的数据结构;
  • 后进先出,First In Last Out;
  • 看似简单,应用却十分广泛的一种数据结构;

一 栈的实现思路

我们在前面自己动手实现了一个支持泛型类的数组,那么我们就可以考虑通过数组这种线性数据结构来实现一个栈,顺序栈。当然,我们也可以用链表实现一个栈,称之为链式栈

先定义一个支持泛型的栈的接口,包含入栈操作、出栈操作、查看栈顶元素、查看栈的大小、栈是否为空的几个接口方法。外带2个构造方法。

然后,定义一个底层用数组实现的栈,来实现这个接口。

二 栈代码实现

1定义栈的接口代码
public interface Stack<E>{
  //入栈操作
  void push(E e);
  
  //出栈操作,出栈之后,栈顶元素已经从栈中删除
  E pop();
  
  //查看栈顶元素,该元素依然存在于栈中
  E peek();
  
  //查看栈的元素个数
  int getSize();
  
  //栈是否为空
  boolean isEmpty();
}
2 底层用数组实现的顺序栈
public class ArrayStack<E> implements Stack<E>{
  //把我们前面实现的数组作为栈的底层存储,做成栈的成员变量
  private Array<E> array;
  
  //构造方法
  public ArrayStack(int capacity){
    array=new Array<>(capacity);
  }
  
  //default constructor
  public ArrayStack(){
    array=new Array<>();
  }
  
  @Override
  public void push(E e){
    //调用数组的addLast()方法,这样就只能在一端插入元素了。
   //这样封装的话,用户使用栈的时候,就不能随意插入元素了,实现了栈只能在一端操作的目的
    array.addLast(e);
  }
  
  @Override
  public E pop(){
    //直接调用数组的removeLast()方法,又封装成了只能在一端删除元素
    return array.removeLast();
  }
  
  @Override
  public E peek(){
    //调用数组的getLast()方法,封装成只能在一端查看元素值
    retrun array.getLast();
  }
  
  @Override
  public int getSize(){
    return array.getSize();
  }
  
  @Override
  public boolean isEmpty(){
    return array.isEmpty();
  }
  
  @Override
  public String toString(){
    StringBuilder stringBuilder=new StringBuilder();
    stringBuilder.addpend("stack:[");
    for(int i=0;i<array.size;i++){
      stringBuilder.append(array.get(i));
      //当没有遍历到数组最后一个元素时,拼接一个" , ",
      if(i!=array.getSize()-1){
        stringBuilder.append(" , ");
      }
    }
    //加个top字符串,表示栈顶的意思
    stringBuilder.append("] top");
    return stringBuilder.toString();
  }
  
  public static void main(String[] args){
        //初始化1个泛型是Integer类型的栈
        ArrayStack<Integer> arrayStack=new ArrayStack<>();
        //初始化栈的大小为0,因为底层数组也是空的,没有任何元素。但是我们前面实现的数组的初始化容量是10。在栈这边是看不到的,隐藏的。我们想查看的话,可以通过arrayStack.array.getCapacity()来调用。
        System.out.println(arrayStack.getSize());
        System.out.println(arrayStack.array.getCapacity());
        //初始化栈为空
        System.out.println(arrayStack.isEmpty());
        //向栈中插入元素,压栈操作
        for(int i=0;i<5;i++){
            arrayStack.push(i);
        }
        System.out.println(arrayStack.getSize());
        System.out.println(arrayStack);
        //出栈操作
        System.out.println(arrayStack.pop());
        //查看栈顶元素
        System.out.println(arrayStack.peek());
        System.out.println(arrayStack);
    }
}
//结果:
0
10
true
5
Stack [0 , 1 , 2 , 3 , 4] top
4
3
Stack [0 , 1 , 2 , 3] top
​

三 复杂度分析

1空间复杂度

栈除了底层存储的数组占据的存储空间之外,对栈的出栈、入栈操作,不需要更多额外的存储空间,所以其空间复杂度是O(1)。

2 时间复杂度

由于我们是用支持动态扩展的数组来实现的栈,因此,当不需要扩容的话,其时间复杂度就是O(1),如果需要扩容的话,因为需要将原数组中的元素遍历一遍并copy到新数组,所以为O(n)。

同理,对于出栈操作,不缩容的情况为O(1)的时间复杂度,缩容则为O(n)。

结合前面,我们分析数组的时间复杂度时,采用均摊复杂度,则,在最坏情况下,出现扩容、缩容,其时间复杂度仍然是O(1)。

四 栈的应用

例如浏览器的前进后退操作,文本编辑器的撤销和前进操作,系统调用栈,函数调用栈,表达式求值的实现,表达式中特殊符号(括号)是否匹配等。