package com.ys.datastructure;
public class MyStack {
    private int[] array;
    private int maxSize;
    private int top;
    public MyStack(int size){
        this.maxSize = size;
        array = new int[size];
        top = -1;
    }
    //壓入數(shù)據(jù)
    public void push(int value){
        if(top < maxSize-1){
            array[++top] = value;
        }
    }
    //彈出棧頂數(shù)據(jù)
    public int pop(){
        return array[top--];
    }
    //訪問棧頂數(shù)據(jù)
    public int peek(){
        return array[top];
    }
    //判斷棧是否為空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判斷棧是否滿了
    public boolean isFull(){
        return (top == maxSize-1);
    }
}

package com.ys.test;
import com.ys.datastructure.MyStack;
public class MyStackTest {
    public static void main(String[] args) {
        MyStack stack = new MyStack(3);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.peek());
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

package com.ys.datastructure;
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack {
    //存儲元素的數(shù)組,聲明為Object類型能存儲任意類型的數(shù)據(jù)
    private Object[] elementData;
    //指向棧頂?shù)闹羔?
    private int top;
    //棧的總?cè)萘?
    private int size;
    //默認構(gòu)造一個容量為10的棧
    public ArrayStack(){
        this.elementData = new Object[10];
        this.top = -1;
        this.size = 10;
    }
    public ArrayStack(int initialCapacity){
        if(initialCapacity < 0){
            throw new IllegalArgumentException("棧初始容量不能小于0: "+initialCapacity);
        }
        this.elementData = new Object[initialCapacity];
        this.top = -1;
        this.size = initialCapacity;
    }
    //壓入元素
    public Object push(Object item){
        //是否需要擴容
        isGrow(top+1);
        elementData[++top] = item;
        return item;
    }
    //彈出棧頂元素
    public Object pop(){
        Object obj = peek();
        remove(top);
        return obj;
    }
    //獲取棧頂元素
    public Object peek(){
        if(top == -1){
            throw new EmptyStackException();
        }
        return elementData[top];
    }
    //判斷棧是否為空
    public boolean isEmpty(){
        return (top == -1);
    }
    //刪除棧頂元素
    public void remove(int top){
        //棧頂元素置為null
        elementData[top] = null;
        this.top--;
    }
    /**
     * 是否需要擴容，如果需要，則擴大一倍并返回true，不需要則返回false
     * @param minCapacity
     * @return
     */
    public boolean isGrow(int minCapacity){
        int oldCapacity = size;
        //如果當前元素壓入棧之后總?cè)萘看笥谇懊娑x的容量，則需要擴容
        if(minCapacity >= oldCapacity){
            //定義擴大之后棧的總?cè)萘?
            int newCapacity = 0;
            //棧容量擴大兩倍(左移一位)看是否超過int類型所表示的最大范圍
            if((oldCapacity<<1) - Integer.MAX_VALUE >0){
                newCapacity = Integer.MAX_VALUE;
            }else{
                newCapacity = (oldCapacity<<1);//左移一位，相當于*2
            }
            this.size = newCapacity;
            int[] newArray = new int[size];
            elementData = Arrays.copyOf(elementData, size);
            return true;
        }else{
            return false;
        }
    }
}

//測試自定義棧類 ArrayStack
//創(chuàng)建容量為3的棧，然后添加4個元素，3個int，1個String.
@Test
public void testArrayStack(){
    ArrayStack stack = new ArrayStack(3);
    stack.push(1);
    //System.out.println(stack.peek());
    stack.push(2);
    stack.push(3);
    stack.push("abc");
    System.out.println(stack.peek());
    stack.pop();
    stack.pop();
    stack.pop();
    System.out.println(stack.peek());
}v

//進行字符串反轉(zhuǎn)
@Test
public void testStringReversal(){
    ArrayStack stack = new ArrayStack();
    String str = "how are you";
    char[] cha = str.toCharArray();
    for(char c : cha){
        stack.push(c);
    }
    while(!stack.isEmpty()){
        System.out.print(stack.pop());
    }
}

//分隔符匹配
//遇到左邊分隔符了就push進棧，遇到右邊分隔符了就pop出棧，看出棧的分隔符是否和這個有分隔符匹配
@Test
public void testMatch(){
    ArrayStack stack = new ArrayStack(3);
    String str = "12<a[b{c}]>";
    char[] cha = str.toCharArray();
    for(char c : cha){
        switch (c) {
        case '{':
        case '[':
        case '<':
            stack.push(c);
            break;
        case '}':
        case ']':
        case '>':
            if(!stack.isEmpty()){
                char ch = stack.pop().toString().toCharArray()[0];
                if(c=='}' && ch != '{'
                    || c==']' && ch != '['
                    || c==')' && ch != '('){
                    System.out.println("Error:"+ch+"-"+c);
                }
            }
            break;
        default:
            break;
        }
    }
}