Java数据结构与算法之栈-蒲公英云

Java数据结构与算法之栈

Dear 丶 2022-08-09 12:44 352阅读 0赞

由于本身栈比较简单，故直接上代码。在代码中看相关知识
栈的代码如下：
//MyStack.java

package com.wayne.StackX;
/* * 1， 栈只允许访问一个数据项，即最后插入的数据项。 * 2， 栈的特性：先进后出或者是后进先出。 * 3， 栈的出栈和入栈的时间复杂度都为常数O(1) * 4， 栈通常用于某种类型的字符串的逆序 */
public class MyStack { 
    //栈的三要素:数组、栈的最大长度、栈顶标记索引
    /* * 数组charStack，目前先用数组实现，后期可用ADT实现长度不固定的栈 * 最大长度maxSize，由于采用数组方式存放数据，故只好先设置长度 * 栈顶标记索引，用于记录栈顶的位置（Java中没有指针定义，故尽量避免使用类似词语。） */
    private char[] charStack;
    private int maxSize;
    private int top;
    /** * 初始化一个长度为length的空栈 * @param length 栈的预计长度 */
    public MyStack(int length){
        maxSize = length;
        charStack = new char[maxSize];
        top = -1;   
    }
    /** * 将一个元素elementChar压入栈中 * @param elementChar 等待被压入的栈 */
    public void push(char elementChar){
        charStack[++top] = elementChar;
    }
    /** * 将栈顶元素弹出栈 * @return 返回栈顶元素 */
    public char pop(){
        return charStack[top--];
    }
    /** * 观察栈顶元素，将栈顶元素打印出来 */
    public void peek(){
        System.out.println(charStack[top]);
    }
    /** * 判断栈是否为空 * @return 如果为空，则返回true，如果不为空，则返回false */
    public boolean isEmpty(){
        return top == -1;
    }
    /** * 判断是否满栈 * @return 如果满，则返回true；如果没有满，则返回假 */
    public boolean isFull(){
        return top == maxSize-1;
    }
}

再来两个例子
//字符逆序ReversLetterApp.java

package com.wayne.test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import com.wayne.StackX.MyStack;
public class ReversLetterApp {
    public static void main(String[] args) throws IOException {
        //封装键盘录入
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String strInput = br.readLine();
        //给一个屏幕提示
        System.out.println("What you have entered is:");
        System.out.println(strInput);
        //根据输入的字符串，初始化栈的最大值
        MyStack myStack = new MyStack(strInput.length());
        //将字符串中每一个字符取出，然后压入栈中
        for(char chTemp:strInput.toCharArray())
        {
            myStack.push(chTemp);
        }
        //从栈中取出每一个元素，并形成最后的目标串
        //由于只是单线程，故可以使用StringBuilder,提高效率
        StringBuilder sb = new StringBuilder();
        while(!myStack.isEmpty())
            sb.append(myStack.pop());
        String resultStr = sb.toString();
        //给出一个结果提示
        System.out.println("after reversing,the result is:");
        System.out.println(resultStr);
    }
}

//括号匹配BracketMatchApp.java

package com.wayne.test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import com.wayne.StackX.MyStack;
public class ReversLetterApp {
    public static void main(String[] args) throws IOException {
        //封装键盘录入
        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));
        String strInput = br.readLine();
        //给一个屏幕提示
        System.out.println("What you have entered is:");
        System.out.println(strInput);
        //根据输入的字符串，初始化栈的最大值
        MyStack myStack = new MyStack(strInput.length());
        //将字符串中每一个字符取出，然后压入栈中
        for(char chTemp:strInput.toCharArray())
        {
            myStack.push(chTemp);
        }
        //从栈中取出每一个元素，并形成最后的目标串
        //由于只是单线程，故可以使用StringBuilder,提高效率
        StringBuilder sb = new StringBuilder();
        while(!myStack.isEmpty())
            sb.append(myStack.pop());
        String resultStr = sb.toString();
        //给出一个结果提示
        System.out.println("after reversing,the result is:");
        System.out.println(resultStr);
    }
}