数据结构栈stack（2）

拼搏现实的明天。 2022-11-24 14:17 141阅读 0赞

### 栈(stack) ###

#### 1、前言 ####

*  栈是一个种线性结构，非常重要。遵循“先进后出”的有序列表
 *  栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入、删除的一端，为变化的一端，称为栈顶（Bottom）。

#### 2、栈应用场景 ####

*  1）子程序的调用：在跳往子程序前，会先将下一个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
 *  2）处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
 *  3）表达式的转换\[中缀表达式转后缀表达式\]与求值。
 *  4）二叉树的遍历
 *  5）图形的深度优先（depth-first）搜索法

#### 3、实现栈的思路分析 ####

1）这里我们使用数组类模拟栈

2）定义一个top来表示栈顶，初始化为-1

3）入栈的操作，当有数据打入到栈时，top++;stack\[top\]=data;

4）出栈的操作，intvalue=stack\[top\];top–,return value

#### 4、栈堆抽象类型定义及基本操作 ####

基本操作：

（1）getSize()：获取栈的元素个数

如何获取栈元素个数，大家都知道栈当top=0时，栈存在一个元素，那么获取栈元素个数就直接返回top即可获取

（2）isEmpty()：判断栈是否为空

栈如何为空，若存储栈的长度为stackSize，那么栈的顶位置top必须小于stackSize的范围内，通常把控栈判定条件定位top等于-1即可。

（3）isFull()：判断栈是否已满

判断栈是否满，很简单只要判断top如果大于等于stackSize-1即可（因为数组下标是从0开始的）

（4）push()：压栈/入栈

（5）pop()：弹栈/出栈

（6）peek()：返回栈顶元素

（7）list()：显示栈/遍历栈

#### 4、代码实现（栈顺序存储） ####

public class ArrayStack1 { 
        public static void main(String[] args) { 
            MyArrayStack stack = new MyArrayStack(4);
            stack.push("1深圳");
            stack.push("2广州");
            stack.push("3贵阳");
            stack.push("4杭州");
            stack.list();
            System.out.println("===========");
            stack.pop();
            stack.pop();
            stack.list();
            System.out.println("============");
            System.out.println(stack.peek());
            System.out.println(stack.peek());
        }
    }
    class MyArrayStack{ 
        private Object[] stack;//定义个数组存放栈的元素
        private int maxSize;//栈的大小
        private int top = -1;//当top=-1时，是空栈
        //初始化栈空间
        public MyArrayStack(int maxSize){ 
            this.maxSize = maxSize;
            stack = new Object[this.maxSize];//初始化栈才能存放数据
        }
        //1、获取栈的元素个数
        public int getSize(){ 
            return top;
        }
        //2、判断栈是否为空
        public boolean isEmpty(){ 
            return top == -1;
        }
        //3、判断栈是否已满
        public boolean isFull(){ 
            return top >= stack.length - 1;
        }
        //4、入栈操作
        public void push(Object value){ 
            if (isFull()){ 
                System.out.println("栈已满");
                return;
            }
            top++;
            stack[top] = value;
        }
        //5、出栈操作
        public Object pop(){ 
            if (isEmpty()){ 
                throw new RuntimeException("stack empty");
            }
            Object value = stack[top];
            top--;
            return value;
        }
        //6、显示栈/遍历栈
        public void list(){ 
            if (isEmpty()){ 
                System.out.println("stack empty");
                return;
            }
            for (int i = top; i >= 0; i--){ 
                System.out.println(stack[i]);
            }
        }
        //7、返回栈元素
        public Object peek(){ 
            if (isEmpty()){ 
                throw new RuntimeException("栈已空");
            }
            return stack[top--];
        }
    
    }

#### 5、栈链式存储 ####

（1）定义StackInterFace

public interface StackInterFace { 
        int getSize();
        boolean isEmpty();
        void push(Object value);
        Object pop();
        Object peek();
    }

（2）LinkedStackImp类及Node内部

public class LinkedStackImp implements StackInterFace { 
        private Node top;//存储栈顶的引用
        private int size;//存储栈元素个数
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size == 0;
        }
    
        @Override
        public void push(Object value) { 
            //根据元素生成节点，插入到链表的头部，新的next指向原来的top
            Node pNode = new Node(value,top);
            //修改top栈顶指针指向新的节点
            top = pNode;
            size++;
        }
    
        @Override
        public Object pop() { 
            //判断堆栈是否为空
            if (size < 1){ 
                throw new StackOverflowError("栈为空");
            }
            Object olData = top.data;//将需要返回的数据返回
            top = top.next;//将top往后移
            size--;
            return olData;
        }
    
        @Override
        public Object peek() { 
            if (size < 1){ 
                throw new StackOverflowError("栈已空");
            }
            return top.data;
        }
    
        @Override
        public String toString() { 
            StringBuffer sb = new StringBuffer();
            sb.append("[");
            for (Node i = top; i != null; i = i.next){ 
                sb.append(i.data);
                if (i.next != null){ 
                    sb.append(",");
                }
            }
            sb.append("]");
            return sb.toString();
        }
    
        //定一个内部类描述链表的节点
        private class Node{ 
            Object data;//存储数据
            Node next;//存储下一个节点的引用
    
            //初始化
            public Node(Object data, Node next) { 
                this.data = data;
                this.next = next;
            }
        }
    }

（3）测试

public class Test1 { 
        public static void main(String[] args) { 
            LinkedStackImp linked = new LinkedStackImp();
            linked.push("1，Java");
            linked.push("2，C++");
            linked.push("3，python");
            System.out.println(linked);
            System.out.println("====");
            System.out.println(linked.pop());
            System.out.println(linked.pop());
        }
    }

#### 6、栈的练习 ####

（1）将十进制转换为二进制

本次联系接着前面的代码实现的

package stack;
    /** * @Author MarkJava * @Date 2020/7/30 20:58 **/
    public class Test1 { 
        public static void main(String[] args) { 
            System.out.println(convert(100,2));
        }
    
        /** * 练习：将十进制num转换为decimal指定地址 * @param num 接收十进制整数 * @param decimal 指定进制 * @return */
        public static String convert(int num, int decimal){ 
            LinkedStackImp stackImp = new LinkedStackImp();//new一个栈，用栈类存储余数
            int remainder = num % decimal;//取摸
            while (num != 0) { 
                stackImp.push(remainder);//计算出的余数，把它压入栈中
                num = num / decimal;//
                remainder = num % decimal;
            }
            StringBuilder sb = new StringBuilder();//用来保存余数
            while (!stackImp.isEmpty()){ //判断如果stackImp不为空
                sb.append(stackImp.pop());
            }
            return sb.toString();
        }
    }

（2）检测表达式中的括弧是否匹配

如：(3+5) \* \[2-3\] - \{23/2\} + (\[\{\}\])

（3）算术表达式的求值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]: /images/20221124/56630a26d9d848b582ea03b2b090d0e7.png