玩转数据结构之使用数组实现自定义栈

上一篇我们手动实现了动态数组功能,这一篇我们使用前面自定义的动态数组实现栈功能，栈这个数据结构(后进先出)对于大家也都比较熟悉，这里也就不再赘述；

• 首先我们定义一个接口，主要涵盖栈的相对应的方法

package com.sjgd.stack;


public interface Stack {

    
    int getSize();

    
    boolean isEmpty();

    
    void push(E e);

    
    E pop();

    
    E peek();
}

• 利用上一节的动态数组实现栈对应的功能

package com.sjgd.stack;


public class ArrayStack implements Stack {
   
   private Array array;

   public ArrayStack() {
       array = new Array<>();
   }

   public ArrayStack(int capacity) {
       array = new Array<>(capacity);
   }


   @Override
   public int getSize() {
       return array.getSize();
   }

   @Override
   public boolean isEmpty() {
       return array.isEmpty();
   }

   @Override
   public void push(E e) {
       array.addLast(e);
   }

   @Override
   public E pop() {
       return array.removeLast();
   }

   @Override
   public E peek() {
       return array.get(getSize() - 1);
   }


   
   @Override
   public String toString() {
       StringBuilder stringBuilder = new StringBuilder();
       stringBuilder.append("Stack: [");
       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();
   }
}

• 测试代码以及解决LeetCode问题

package com.sjgd.stack;


public class Test {
   public static void main(String[] args) {
       //验证自定义Stack功能
       ArrayStack arrayStack = new ArrayStack<>();
       for (int i = 0; i < 10; i++) {
           arrayStack.push(i);
           System.out.println(arrayStack);
       }
       arrayStack.pop();
       System.out.println(arrayStack);

       //使用自定义Stack解决LeetCode功能
       System.out.println(isValid("()[]{}")); //true
       System.out.println(isValid("([)]")); // false
   }


   

   public static boolean isValid(String s) {
       ArrayStack arrayStack = new ArrayStack<>();
       for (int i = 0; i < s.length(); i++) {
           char c = s.charAt(i);
           if (c == '(' || c == '{' || c == '[') {
               //判断是左括号则入栈
               arrayStack.push(c);
           } else {
               if (arrayStack.isEmpty()) {
                   return false;
               }
               //取出栈顶元素
               char top = arrayStack.pop();
               if (c == ')' && top != '(') {
                   return false;
               }
               if (c == '}' && top != '{') {
                   return false;
               }
               if (c == ']' && top != '[') {
                   return false;
               }
           }
       }

       //入栈出栈完成，该栈中没有元素则表示匹配成功
       return arrayStack.isEmpty();
   }

}

由于入栈和出栈并不需要数组中元素进行移动，因此入栈和出栈时间复杂度均为O(1);