栈的概念

  • 栈(stack)是只允许在一端进行插入或者删除操作的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。
  • 栈顶是线性表允许插入删除的一端。
  • 栈底是固定的,不允许进行插入和删除的那一端。
  • 空栈是不含任何元素的空表。
  • 栈时一个先入后出(FILO - First In Last Out)的有序列表。
  • 根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶。
  • 删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。

栈的应用场景

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

顺序栈实现的思路分析

  • 使用数组来模拟栈;
  • 定义一个top来表示栈顶,初始化为-1;
  • 入栈的操作:当有数据加入到栈时,top++;stack[top] = data;
  • 出栈的操作:int value = stack[top]; top--;return value;

链栈实现的思路分析

  • private int size;定义size变量用来衡量栈的长度,判断是否为空
  • private LinkNode top;top指针指向栈顶
  • private LinkNode next; 结点中定义next指针指向下一个结点

顺序栈的代码实现

import java.util.Scanner;

public class ArrayStackDemo {

    public static void main(String[] args) {
        // TODO 测试
        //先创建一个ArrayStack的对象
        ArrayStack stack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner scan = new Scanner(System.in);
        
        while(loop) {
            System.out.println("show:显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加数据到栈");
            System.out.println("pop:表示从栈取出数据");
            System.out.println("请输入代码:");
            key = scan.next();
            switch (key) {
            case "show":
                stack.list();
                break;
            case "push":
                System.out.println("请输入一个数:");
                int value = scan.nextInt();
                stack.push(value);
                break;
            case "pop":
                try {
                    int res = stack.pop();
                    System.out.printf("出栈的数据是:%d\n",res);
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            case "exit":
                scan.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出");

    }

}

//定义一个ArrayStack 表示栈
class ArrayStack {
    private int maxSize; // 栈的大小
    private int[] stack; // 数组,数组模拟栈,数据放在该数组中
    private int top = -1; // top表示栈顶,初始化为-1

    // 构造器
    public ArrayStack(int maxSize) {
        if (maxSize < 1) {
            throw new RuntimeException("参数错误");
        }
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    // 判断是否栈满
    public boolean isFull() {
        return top == maxSize - 1;
    }

    // 判断是否栈空
    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(int value) {
        if (isFull()) {
            System.out.println("stack is full");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop() {
        //先判断栈是否空
        if(isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        int value = stack[top];  //先取得栈顶值
        top--; //指针下移
        return value;
    }

    // 显示栈的情况(遍历),遍历时需要从栈顶开始显示数据
    public void list() {
        if (isEmpty()) {
            System.out.println("stack is empty");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.printf("stack[%d] = %d\n", i, stack[i]);
        }
    }
}

链栈的代码实现


import java.util.Scanner;
public class LinkedStackDemo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkedStack stack = new LinkedStack();
        String key = "";
        boolean loop = true;
        Scanner scan = new Scanner(System.in);

        while (loop) {
            System.out.println("show:显示栈");
            System.out.println("exit:退出程序");
            System.out.println("push:表示添加数据到栈");
            System.out.println("pop:表示从栈取出数据");
            System.out.println("请输入代码:");
            key = scan.next();
            switch (key) {
            case "show":
                stack.show();
                break;
            case "push":
                System.out.println("请输入一个姓名:");
                String tmp = scan.next();
                //生成新对象压入栈中
                stack.push(new LinkNode(tmp));
                break;
            case "pop":
                try {
                    //接受返回来的对象
                    LinkNode sNode = stack.pop();
                    System.out.println(sNode.getName());
                } catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
                break;
            case "exit":
                scan.close();
                loop = false;
                break;
            default:
                break;
            }
        }
        System.out.println("程序退出");
        scan.close();
    }
}

class LinkedStack {
    private int size;
    private LinkNode top;

    public LinkedStack() {
        top = null; // 空栈
    }

    // 以指定元素来创建栈
    public LinkedStack(LinkNode node) {
        top = node;
        top.setNext(null);
        size++;
    }

    /**
     * 获取链栈的长度
     * @return
     */
    public int getSize() {
        return size;
    }

    /**
     * 将结点压入栈中
     * @param node 欲压入的结点
     */
    public void push(LinkNode node) {
        //链栈中没有元素时的处理
        if (isEmpty()) { 
            node.setNext(null);
            top = node;
            size++;
            return;
        }
        //栈中有元素时的处理
        node.setNext(top);
        top = node;
        size++;
        return;
    }

    /**
     * 出栈
     * @return 返回结点
     */
    public LinkNode pop() {
        //
        if(isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        LinkNode tmp = top;
        size--;
        top = top.getNext();
        return tmp;
    }

    /**
     * 遍历栈
     */
    public void show() {
        if (isEmpty()) {
            System.out.println("stack is empty");
            return;
        }
        LinkNode current = top;
        for(int i=0;i<size;i++) {
            
            System.out.println(current);
            current = current.getNext();
        }

    }

    /**
     * 判断栈是否为空
     * @return 
     */
    public boolean isEmpty() {
        return (size==0) ? true : false;
    }
}

class LinkNode {
    private String name;
    private LinkNode next;
    public LinkNode(String name) {
        this.name = name;
    }
    
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public LinkNode getNext() {
        return next;
    }

    public void setNext(LinkNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "LinkNode [name=" + name + "]";
    }

}
Last modification:December 12th, 2020 at 04:54 pm
如果觉得我的文章对你有用,请随意赞赏