玩转数据结构（二）基于动态数组实现的栈

逃离我推掉我的手 2022-05-21 08:22 229阅读 0赞

栈是一种先进后出的数据结构。在计算机中有好多处用到栈，例如：文本编译器中的undo操作、计算机系统中的递归调用、JVM中方法的执行中、括号匹配算法等都会用到栈这种数据结构。在这次博客中，使用上次封装的Array数组来实现自己的栈。资源跳转：[玩转数据结构>封装自己的Array数组][Array]

### 1、栈的接口 ###

public interface Stack<E> {
        int getSize();
        void push(E e);
        E pop();
        E peek();
        boolean isEmpty();
    }

### 2、实现栈 ###

public class ArrayStack<E> implements Stack<E> {
       private Array<E> array;
    
       public ArrayStack() {//默认容量为10
           this(10);
       }
    
        public ArrayStack(int capacity) {
            array = new Array<E>(capacity);
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @Override
        public void push(E e) {//在数组最后添加元素，时间复杂度为O（1）
            array.addLast(e);
        }
    
        @Override
        public E pop() {
            return array.removeLast();
        }
    
        @Override
        public E peek() {
            return array.getLast();
        }
    
        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }
    
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(String.format("ArrayStack:size=%d, capacity=%d ",array.getSize(), array.getCapacity()));
            stringBuilder.append("[");
            for (int i = 0; i < array.getSize(); i++) {
                stringBuilder.append(array.get(i));
                if(i != array.getSize() - 1) {
                    stringBuilder.append(",");
                }
            }
    
            stringBuilder.append("] top");
            return stringBuilder.toString();
        }
    }

### 3、测试 ###

public static void main(String[] args) {
            ArrayStack<Integer> arrayStack = new ArrayStack<Integer>();
            System.out.println("入栈：");
            for (int i = 0; i < 10; i++) {
                System.out.print(i + " ");
                arrayStack.push(i);
            }
    
            System.out.println("\n出栈：");
            for (int i = 0; i < 10; i++) {
                System.out.print(arrayStack.pop() + " ");
            }
    
        }

### 4、结果 ###

入栈：
    0 1 2 3 4 5 6 7 8 9 
    出栈：
    9 8 7 6 5 4 3 2 1 0

在实现栈时，入栈和出栈都是在数组的尾部进行的，因为不用进行数据的移动，因此数组的尾部操作时间复杂度为0（1）。

[Array]: https://blog.csdn.net/zhoujian_Liu/article/details/80900912