目录

一定义.

入栈

出栈

二.栈与线性表的关系

三.栈的实现方式

四.链表实现栈

1.结点的API设计

2.栈的API设计

2.1栈的初始化设计

2.2元素入栈

2.3元素出栈

五.括号匹配问题

完整代码展示

答案

---

一定义.

栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
●我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

●栈（stack）又被称为堆栈，它是一种只允许在一端（一般是表尾）进行插入和删除操作的线
性表。
●作为一种特殊的数据结构，由于栈被限定只能在尾进行插入和删除操作。

入栈

出栈

二.栈与线性表的关系

栈是一种特殊的线性表，它同样由一系列数据元素组成，但是栈的操作受到限制，只允许在一端（称为栈顶）进行插入（压栈，push）和删除（弹栈，pop）操作。栈遵循后进先出（LIFO，Last In First Out）的原则。

三.栈的实现方式

        栈通过以下两种方式实现：

        1.顺序表实现

        2.链表实现

        我们今天讲第二种方式。

四.链表实现栈

链表使用节点来存储数据元素。每个节点包含数据部分和指向下一个节点的引用。在链表实
现栈时，我们通常将链表的头节点作为栈顶。

1.结点的API设计

2.栈的API设计

2.1栈的初始化设计

class StackResult<T>
{
    //结点类
    class  Node
    {
        T data;//存储数据
        Node next;//下一个结点

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    //记录首结点
    private Node head;
    //元素个数
    private int N;
    // 构造方法
    public StackResult()
    {
        //初始化头结点
        this.head =new Node(null,null);
        this.N =0;//s初始元素个数为0
    }
}

2.2元素入栈

思路分析：根据前面的入栈流程图，我们可以简单分为4步

1.找到头结点指向栈顶的值

2.创建一个新结点，为新栈顶

3.让头结点指向新栈顶的值

4.让新结点指向原来的栈顶

 //把元素入栈
    public void push(T data)
    {
        //找到头结点指向栈顶的值
        Node oldFirst=head.next;
        //创建新结点
        Node newFirst=new Node(data,null);
        //让头结点指向新结点
        head.next=newFirst;
        //让新结点指向原来的栈顶
        newFirst.next=oldFirst;
        N++;
    }

2.3元素出栈

思路分析：

根据前面的出栈流程图，我们可以分为

1.找到原来头结点指向栈顶的值

2.让头结点指向原来栈顶指向下一个结点的值

 //元素出栈
    public T pop()
    {
        //找到头结点指向栈顶的的值
        Node oldFirst=head.next;
        //检查是否为空
        if(oldFirst==null)
        {
            return null;
        }
        //让头结点指向原来栈顶指向下一个结点的值
        head.next=oldFirst.next;
        N--;
        return oldFirst.data;
    }

五.括号匹配问题

问题描述：判断字符串”(a+b）*（c-d)”字符串中的括号是否匹配

 //括号匹配
    public static boolean  isMatch(String str )
    {
       //创建一个存储字符串的栈
        StackResult<Character> stack=new StackResult<>();
        //遍历字符串
        for(int i=0;i<str.length();i++)
        {
            char ch=str.charAt(i);
            if(ch=='(')
            {
                stack.push(ch);//当遇到字符（时，将其入栈
            }
            else if (ch==')')//遇到字符串）时，先检查栈是否为空
            {
                if(stack.isEmpty())
                {
                    return false;//为空返回false
                }
                stack.pop();//不为空将其出栈
            }
        }
    return stack.isEmpty();//检查栈是否为空，为空则说明全部匹配成功，反之失败
    }

完整代码展示

class StackResult<T>
{
    //结点类
    class  Node
    {
        T data;//存储数据
        Node next;//下一个结点

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
    //记录首结点
    private Node head;
    //元素个数
    private int N;
    // 构造方法
    public StackResult()
    {
        //初始化头结点
        this.head =new Node(null,null);
        this.N =0;//s初始元素个数为0
    }
  //其他方法---------------------------------------------------
    //判断当前栈中的元素个数是否为0
    public boolean isEmpty()
    {
        return N==0;
    }
    //获取栈中的元素个数
    public int size()
    {
        return N;
    }
    //把元素入栈
    public void push(T data)
    {
        //找到头结点指向栈顶的值
        Node oldFirst=head.next;
        //创建新结点
        Node newFirst=new Node(data,null);
        //让头结点指向新结点
        head.next=newFirst;
        //让新结点指向原来的栈顶
        newFirst.next=oldFirst;
        N++;
    }
    //元素出栈
    public T pop()
    {
        //找到头结点指向栈顶的的值
        Node oldFirst=head.next;
        //检查是否为空
        if(oldFirst==null)
        {
            return null;
        }
        //让头结点指向原来栈顶指向下一个结点的值
        head.next=oldFirst.next;
        N--;
        return oldFirst.data;
    }
    //括号匹配
    public static boolean  isMatch(String str )
    {
       //创建一个存储字符串的栈
        StackResult<Character> stack=new StackResult<>();
        //遍历字符串
        for(int i=0;i<str.length();i++)
        {
            char ch=str.charAt(i);
            if(ch=='(')
            {
                stack.push(ch);//当遇到字符（时，将其入栈
            }
            else if (ch==')')//遇到字符串）时，先检查栈是否为空
            {
                if(stack.isEmpty())
                {
                    return false;//为空返回false
                }
                stack.pop();//不为空将其出栈
            }
        }
    return stack.isEmpty();//检查栈是否为空，为空则说明全部匹配成功，反之失败
    }
}
public class StudentMs3
{
    public static void main(String[] args)
    {

        String str ="(a+b)*(c-d)";
        boolean result = StackResult.isMatch(str);
        System.out.println(result);
    }
}

答案