Java数据结构与算法之栈

Dear 丶 2022-08-09 12:44 224阅读 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