侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

coydone
2021-06-05 / 0 评论 / 0 点赞 / 341 阅读 / 1,891 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

概述

栈是一种基于先进后出(FILO)的数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底(压栈/入栈),最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(弹栈/出栈)(最后一 个数据被第一个读出来)。

我们称数据进入到栈的动作为压栈,数据从栈中出去的动作为弹栈。

栈的实现

API设计

类名:Stack
构造方法 Stack():创建Stack对象
成员方法
	public boolean isEmpty():判断栈是否为空,是返回true,否返回false
	public int size():获取栈中元素的个数
	public E pop():弹出栈顶元素
	public void push(E e):向栈中压入元素e
成员变量
	private Node head:记录首结点
	private int n:当前栈的元素个数

代码实现

//栈
public class Stack<E> {
    //记录首结点
    private Node<E> head;
    //当前栈的元素个数
    private int n;

    public Stack() {
        head = new Node(null, null);
        n = 0;
    }

    //判断栈是否为空,是返回true,否返回false
    public boolean isEmpty() {
        return n == 0;
    }

    //获取栈中元素的个数
    public int size() {
        return n;
    }

    //弹出栈顶元素
    public E pop() {
        //记录栈顶元素
        Node oldFirst = head.next;
        if (oldFirst == null) {
            return null;
        }
        //删除首个元素
        head.next = head.next.next;
        //个数-1
        n--;
        return (E) oldFirst.item;
    }

    //向栈中压入元素e
    public void push(E e) {
        // 记录旧的下一个节点,栈顶元素
        Node oldNext = head.next;
        // 创建新的节点
        Node node = new Node(e, oldNext);
        // 个数+1
        n++;
        // 新的节点连接到head的下一个节点
        head.next = node;
    }

    private class Node<E> {
        E item;
        Node next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

括号匹配案例

给定一个字符串,里边可能包含"()"小括号和其他字符,请编写程序检查该字符串的中的小括号是否成对出现。 (左括号数量与右括号数量相同)

分析
1. 创建一个栈用来存储左括号
2. 从左往右遍历字符串,拿到每一个字符
3. 判断该字符是不是左括号,如果是,放入栈中存储
4. 判断该字符是不是右括号,如果不是,继续下一次循环
5. 如果该字符是右括号,则从栈中弹出一个元素t;
6. 判断元素t是否为null,如果不是null,则证明有对应的左括号,如果是null,则证明没有对应的左括号
7. 循环结束后,判断栈中还有没有剩余的左括号,如果有,则不匹配,如果没有,则匹配
/**
 * 判断str中左右括号是否匹配
 * @param str 待匹配的字符串
 * @return
 */
private static boolean matchBrackets(String str) {
    // 1. 创建一个栈来存储左括号
    Stack<String> stack = new Stack();
    // 2. 从右往右遍历字符串,拿到每一个字符
    for (int i = 0; i < str.length(); i++) {
        // 拿到每一个字符串
        String currentChar = str.charAt(i) + "";
        // 3.判断该字符串是不是左括号,如果是,则放入栈中
        if (currentChar.equals("(")) {
            stack.push(currentChar);
            // 4. 判断该字符串是否是右括号,如果是,从栈中弹出一个元素t
        } else if (currentChar.equals(")")) {
            String t = stack.pop();
            // 判断t是否为null。如果为null说明没有左括号匹配,否则有左括号匹配
            if (t == null) {
                return false;
            }
            // 如果不是,继续下一个循环
        }
    }
    // 循环完毕之后,判断栈中是否还有剩余的左括号,如果有,说明不匹配,如果没有,则匹配
    if (stack.size() == 0) {
        return true;
    } else {
        return false;
    }
}
0

评论区