10、数据结构与算法 - 实战：栈1

题目：回文字符串判断，就是一个字符串，从左到右读和从右到左读是完全一样的
例如：abcdedcba就是回文

/**
 * 字符串回文判断
 * @param str 需要判断的字符串
 * @return true 是回文  false 不是回文
 */
public static boolean isPalindrome(String str) {

    LinkedListStack<Character> stack = new LinkedListStack<Character>();

    // 将字符串转换成字符数组
    char[] inputChar = str.toCharArray();

    // 字符数组的中间序号
    int mid = inputChar.length / 2;

    // 将字符数组的前一半字符压入栈中
    for (int i = 0; i < mid; i++) {
        stack.push(inputChar[i]);
    }

    // 如果字符数组大小为奇数
    if (inputChar.length % 2 != 0) {
        mid += 1;
    }

    // 对比字符数组后半部分字符和栈中字符
    for (int i = mid; i < inputChar.length; i++) {
        System.out.println(inputChar[i] + " == " + stack.top());
        if (inputChar[i] != stack.pop()) {
            return false;
        }
    }
    return true;
}

测试代码：

public static void main(String[] args) {
    String string = "asdffdsa";
    if (isPalindrome(string)) {
        System.out.println("是回文");
    } else {
        System.out.println("不是回文");
    }
}

题目：设计一个可以把栈中元素按照升序排列的排序算法

/**
 * 设计一个可以把栈中元素按照升序排列的排序算法
 * @param sourceStack 需要排序的原栈
 * @return 排序后的栈
 */
public static LinkedListStack<Integer> sort(LinkedListStack<Integer> sourceStack) {
    LinkedListStack<Integer> resultStack = new LinkedListStack<Integer>();
    while (!sourceStack.isEmpty()) {
        Integer temp = sourceStack.pop();
        while (!resultStack.isEmpty() && resultStack.top() > temp) {
            sourceStack.push(resultStack.pop());
        }
        resultStack.push(temp);
    }
    return resultStack;
}

测试代码：

public static void main(String[] args) {
    LinkedListStack<Integer> sourceStack = new LinkedListStack<Integer>();
    sourceStack.push(4);
    sourceStack.push(6);
    sourceStack.push(2);
    LinkedListStack<Integer> resultStack= sort(sourceStack);
    // 先获取栈的大小
    int size = resultStack.size();
    for (int i = 0; i < size; i++) {
        System.out.println("第" + i + "个元素：" + resultStack.pop());
    }
}

题目：给定一个栈，如何只使用栈操作（push和pop）逆置栈中的内容

// 使用到递归调用
public class StackReversal<AnyType> {

    public void reverseStack(LinkedListStack<AnyType> stack) {
        if (stack.isEmpty()) {
            return;
        }
        AnyType temp = stack.pop();
        reverseStack(stack);
        insertAtBottom(stack, temp);
    }

    public void insertAtBottom(LinkedListStack<AnyType> stack, AnyType data) {
        if (stack.isEmpty()) {
            stack.push(data);
            return;
        }
        AnyType temp = stack.pop();
        insertAtBottom(stack, data);
        stack.push(temp);
    }
}

测试代码：

public static void main(String[] args) {    
    LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
    stack.push(4);
    stack.push(3);
    stack.push(2);

    StackReversal<Integer> sr = new StackReversal<Integer>();
    sr.reverseStack(stack);
    // 先获取栈的大小
    int size = stack.size();
    System.out.println("-----------");
    for (int i = 0; i < size; i++) {
        System.out.println("第" + i + "个元素：" + stack.pop());
        System.out.println("-----------");
    }
}