数据结构与算法05栈

一、介绍

二、栈的应用场景

1. 子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以 回到原来的程序中。
2. 处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆 栈中。
3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
4. 二叉树的遍历。
5. 图形的深度优先(depth一first)搜索法。
   Stack来自于Vector，那么显然stack的底层实现是数组。
   

三、数组模拟栈

思路：

package Stack;
import java.util.Scanner;
public class ArrayStackDemo  {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(4);
    }
     static class ArrayStack{
        private int maxSize;//栈的大小
        private int top=-1;//栈顶初始化
        private int [] stack;//数组模拟栈
    //构造器
        public  ArrayStack(int maxSize){
            this.maxSize=maxSize;
            stack=new int[this.maxSize];
        }
        //判断栈满
        public boolean isFull(){
           return top==maxSize-1;
        }
        //判断栈空
        public boolean isEmpty(){
            return top==-1;
        }
        //入栈
        public void push (int value){
            if(isFull()){
                System.out.println("栈满");
            }
            top++;
            stack[top]=value;
        }
        //出栈
        public int pop(){
            if(isEmpty()){
                throw new RuntimeException("没有元素");
            }
           int value=stack[top];
            top--;
            return value;
        }
        //显示栈的情况（遍历栈）,从栈顶开始遍历
        public void list(){
            if(isEmpty()){
                throw new RuntimeException("没有数据");
            }
            for (int i =top; i >=0 ; i--) {
               System.out.printf("stack[%d]=%d\n",i,stack[i]);
            }
        }
    }
}

四、栈的常用方法

push( num) //入栈
pop() //栈顶元素出栈
empty() //判定栈是否为空
peek() //获取栈顶元素
search(num) //判端元素num是否在栈中，如果在返回1，不在返回-1。

public class A {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        Integer p1 = s.push(1);//1
        Integer p2 = s.push(2);//2
        Integer peek = s.peek();    //2
        boolean empty = s.empty();   //false
        int search = s.search(1);  // 2
        Integer pop = s.pop();         //2
        boolean empty1 = s.isEmpty();  //false
    }
}

一、线性查找算法

public class seqSearch {
    public static void main(String[] args) {
        int [] arr={1,3,2,4,7,6,0};
       int index = seqsearch(arr,9);
        System.out.println(index);
    }
    public static int seqsearch(int [] arr ,int value){
        for(int i=0;i<arr.length;i++){
            if (arr[i]==value)
                return i;
        }
        return -1;
    }
}

二、二分查找算法

在这里插入代码片

三、插值算法