数据结构和算法-4.1-栈

栈&队列 与 数组的区别

• 用途：数组，链表，树等一般用来作为数据存储的工具，栈和队列更多是用来作为构思程序算法的辅助工具，用来执行某项特殊任务，例如handler中的messageQueue消息队列，Activity栈等；
• 受限访问：数组可以通过下标随机访问或遍历，而栈和队列访问是受限的，即在特定时刻只有一个数据项可以被读取或删除；
• 抽象数据类型：栈和队列的关键点在于它的逻辑特性，而非实现细节，它们可以用其他数据结构，如数组，链表等来实现；
• 栈和队列插入和移除数据项的时间复杂度都是O(1);

栈

• 只允许访问最后插入的数据项，移除这个数据项后才可以访问倒数第二个插入的数据项，依此类推，例如往一个桶里面放东西，取出的时候要先取出最上面的；
• LIFO：last in first out，后进先出
• 栈的容量通常比较小，一般用来作为算法或应用程序中临时存储数据
• 通常提供的限定访问方法是push()和pop()，这是比较通用的命名；
• 栈的实现
  1. 先创建一个栈的基类

  public abstract class Stack<T> {
    //是否为空
    public abstract boolean isEmpty();
    //入栈
    public abstract void push(T value);
    //出栈
    public abstract T pop();
    //查看
    public abstract T peek();
    //打印栈
    public abstract void display();
  }
  

  2. 用数组实现栈，后面讲到链表后，也将介绍用链表实现栈

  public class ArrayStack<T> extends Stack<T> {
  
    protected int maxSize;
    protected int top;
    private T[] stackArray;
  
    public ArrayStack(int maxSize){
        stackArray= (T[]) new Object[maxSize];
        this.maxSize=maxSize;
        top=-1;
    }
  
    @Override
    public boolean isEmpty(){
        return top==-1;
    }
  
    public int size(){
        return top+1;
    }
  
    @Override
    public void push(T value){
        ensureCapacity();//扩充数组
        stackArray[++top]=value;
    }
  
    //当数组满后进行扩充
    private void ensureCapacity() {
        if (stackArray.length==top+1)
            stackArray= Arrays.copyOf(stackArray,2*stackArray.length+1);
    }
  
    @Override
    public T pop(){
        if (top<0)
            //throw new EmptyStackException();
            return null;
        T temp=stackArray[top];
        stackArray[top]=null;//防止内存泄漏
        top--;
        return temp;
    }
  
    @Override
    public T peek(){
        if (top<0)
            return null;
        return stackArray[top];
    }
  
    /**
     * 打印数组
     */
    @Override
    public void display() {
        System.out.print("ArrayStacker: ");
        for (int i = 0; i <=top; i++) {
            System.out.print("[" + i + "]-->" + stackArray[i] + "  ");
        }
        System.out.println();
    }
  }
  

  3. 对上面栈的使用

  private static void testStack() {
        //创建一个栈的实例
        ArrayStack<String> stacker = new ArrayStack<>(10);
        //入栈
        for (int i = 100; i < 120; i++) {
            stacker.push("" + i);
            stacker.display();
        }
        //查看
        System.out.println("peek:" + stacker.peek());
        System.out.println("peek:" + stacker.peek());
        System.out.println("peek:" + stacker.peek());
        //出栈
        while (!stacker.isEmpty()) {
            System.out.println("pop:" + stacker.pop());
            stacker.display();
        }
        // 例子：对输入的字符串进行逆序
        System.out.println("请输入要逆序的字符串：");
        Scanner sc = new Scanner(System.in);
        if (sc.hasNext()) {
            String param = sc.next();
            char[] chars = param.toCharArray();
            for (char aChar : chars) {
                stacker.push(aChar + "");
            }
            System.out.print("逆序后的字符串：");
            while (!stacker.isEmpty()) {
                System.out.print(stacker.pop());
            }
        }
    }