首页 > 其他分享 >栈、队列、符号表

栈、队列、符号表

时间：2022-11-08 16:02:54浏览次数：35  
标签：Node 符号表 队列 next key return null public

栈概述

生活中的栈

  • 存储货物或供旅客住宿的地方，可引申为仓库、中转站。例如我们现在生活中的酒店，在古时候叫客栈，
    是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈

计算机中的栈

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

栈的实现

  • 栈API设计
  • 类名：Stack
  • 构造方法：Stack()：创建Stack对象
  • 成员方法：1.public boolean isEmpty()：判断栈是否为空，是返回true，否返回false
    2.public int size()：获取栈中元素的个数
    3.public T pop()：弹出栈顶元素
    4.public void push(T t)：向栈中压入元素t
  • 成员变量：1.private Node head：记录首结点
    2.private int N：当前栈的元素个数
  • 成员内部类：private class Node：结点类
public class Stack<T> implements Iterable{
    private Node head;
    private int N;

    private class Node{
        public T item;
        public Node next;
        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }

    public Stack(){
        this.head = new Node(null,null);
        this.N = 0;
    }

    public boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return N;
    }

    public void push(T t){
        Node oldFirst = head.next;
        Node newNode = new Node(t, null);
        head.next = newNode;
        newNode.next = oldFirst;
        N++;
    }

    public T pop(){
        Node oldFirst = head.next;
        if (oldFirst==null){
            return null;
        }
        head.next = oldFirst.next;
        N--;
        return oldFirst.item;
    }
    @Override
    public Iterator iterator() {
        return new SIterator();
    }

    private class SIterator implements Iterator{
        private Node n;
        public SIterator(){
            this.n = head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}
public class StackTest {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");

        for (Object item:stack){
            System.out.println(item);
        }
        System.out.println("=======================");

        String result = stack.pop();
        System.out.println("弹出的元素是："+result);
        System.out.println("剩余的元素个数："+stack.size());
    }
}

案例

括号匹配问题

  • 问题描述：给定一个字符串，里边可能包含"()"小括号和其他字符，请编写程序检查该字符串中的小括号是否成对出现
public class BracketsMatch {
    public static void main(String[] args) {
        String str = "(上海(长安)())";
        boolean match = isMatch(str);
        System.out.println(str+"中的括号是否匹配："+match);
    }
    
    public static boolean isMatch(String str){
        return false;
    }
}
  • 分析：
1.创建一个栈用来存储左括号
2.从左往右遍历字符串，拿到每一个字符
3.判断该字符串是不是左括号，如果是，放入栈中存储
4.判断该字符是不是右括号，如果不是，继续下一个循环
5.如果该字符是右括号，则从栈中弹出一个元素t
6.判断元素t是否为null，如果不是，则证明有对应的左括号，如果不是，则证明没有对应的左括号
7.循环结束后，判断栈中还有没有剩余的左括号，如果有，则不匹配，如果没有，则匹配

public class BracketsMatch {
    public static void main(String[] args) {
        String str = "(上海(长安)())";
        boolean match = isMatch(str);
        System.out.println(str+"中的括号是否匹配："+match);
    }

    public static boolean isMatch(String str){
        Stack<String> chars = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            String currChar = str.charAt(i)+"";
            if (currChar.equals("(")){
                chars.push(currChar);
            }else if (currChar.equals(")")){
                String pop = chars.pop();
                if (pop==null){
                    return false;
                }
            }
        }
        if (chars.size()==0){
            return true;
        }else{
            return false;
        }
    }
}

逆波兰表达式求值问题

  • 逆波兰表达式求职问题是我们计算机中经常遇到的一类问题，要研究明白这个问题，首先我们得搞清楚
    什么是逆波兰表达式？要搞清楚逆波兰表达式，我们得从中缀表达式说起
  • 中缀表达式：
    中缀表达式就是我们平常生活中使用的表达式，中缀表达式的特点是：二元运算符总是置于两个操作数中间
  • 逆波兰表达式(后缀表达式)
    后缀表达式的特点：运算符总是放在跟它相关的操作数之后
public class ReversePolishNotationTest {
    public static void main(String[] args) {
        String[] notation = {"3","7","15","-","*","18","6","/","+"};
        int result = calculate(notation);
        System.out.println("逆波兰表达式的结果为："+result);
    }
    
    public static int calculate(String[] notation){
        
        return -1;
    }
}
  • 分析：
1.创建一个栈对象oprands存储操作数
2.从左往右遍历逆波兰表达式，得到每一个字符串
3.判断该字符串是不是运算符，如果不是，把该操作数压入oprands栈中
4.如果是运算符，则从oprands栈中弹出两个操作数o1，o2
5.使用该运算符计算o1和o2，得到结果result
6.把该结果压入oprands栈中
7.遍历结束后，拿出栈中最终的结果返回

public class ReversePolishNotationTest {
    public static void main(String[] args) {
        String[] notation = {"3","17","15","-","*","18","6","/","+"};
        int result = calculate(notation);
        System.out.println("逆波兰表达式的结果为："+result);
    }

    public static int calculate(String[] notation){
        Stack<Integer> oprands = new Stack<Integer>();
        for (int i = 0; i < notation.length; i++) {
            String curr = notation[i];
            Integer o1;
            Integer o2;
            Integer result;
            switch (curr){
                case "+":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    result = o2+o1;
                    oprands.push(result);
                    break;
                case "-":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    result = o2-o1;
                    oprands.push(result);
                    break;
                case "*":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    result = o2*o1;
                    oprands.push(result);
                    break;
                case "/":
                    o1 = oprands.pop();
                    o2 = oprands.pop();
                    result = o2/o1;
                    oprands.push(result);
                    break;
                default:
                    oprands.push(Integer.parseInt(curr));
                    break;
            }
        }

        int result = oprands.pop();
        return result;
    }
}

队列

  • 队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，
    它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来
  • 队列API设计：
  • 类名：Queue
  • 构造方法：Queue()：创建Queue对象
  • 成员方法：1.public boolean isEmpty()：判断队列是否为空，是返回true，否返回false
    2.public int size()：获取队列中元素的个数
    3.public T dequeue()：从队列中拿出一个元素
    4.public void enqueue(T t)：往队列中插入一个元素
  • 成员变量：1.private Node head：记录首结点
    2.private int N：当前栈的元素个数
    3.private Node last：记录最后一个结点
  • 成员内部类：private class Node：结点类

队列的实现

public class Queue<T> implements Iterable{
    private Node head;
    private Node last;
    private int N;

    private class Node{
        public T item;
        public Node next;

        public Node(T item,Node next){
            this.item = item;
            this.next = next;
        }
    }
    public Queue(){
        this.head = new Node(null,null);
        this.last = null;
        this.N = 0;
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void enqueue(T t){
        if (last==null){
            last = new Node(t,null);
            head.next = last;
        }else{
            Node oldLast = last;
            last = new Node(t, null);
            oldLast.next = last;
        }
        N++;
    }
    public T dequeue(){
        if (isEmpty()){
            return null;
        }
        Node oldFirst = head.next;
        head.next = oldFirst.next;
        N--;

        if (isEmpty()){
            last = null;
        }
        return oldFirst.item;
    }

    @Override
    public Iterator iterator() {
        return new QIterator();
    }

    private class QIterator implements Iterator{
        private Node n;

        public QIterator(){
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }
}
public class QueueTest {
    public static void main(String[] args) {
        Queue<String> q = new Queue<>();

        q.enqueue("a");
        q.enqueue("b");
        q.enqueue("c");
        q.enqueue("d");

        for (Object str : q) {
            System.out.println(str);
        }
        System.out.println("===========================");
        String result = q.dequeue();
        System.out.println("出队列的元素是"+result);
        System.out.println("剩余的元素个数："+q.size());
    }
}

符号表

  • 符号表最主要的目的就是将一个键和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的
    键值对数据，我们可以根据键来查找对应的值。符号表中，键具有唯一性
  • 符号表在实际生活中的使用场景是非常广泛的：
    字典中找出单词的释义，图书索引中找出某个术语相关的页码，网络搜索中找出某个关键字对应的网页...
  • 符号表API设计
  • 结点类：
  • 类名：Node<Key,Value>
  • 构造方法：Node(Key key,Value value,Node next)：创建Node对象
  • 成员变量：1.public Key key：存储键
    2.public Value value：存储值
    3.public Node next：存储下一个结点
  • 符号表：
  • 类名：SymbolTable<Key,Value>
  • 构造方法：SymbolTable()：创建SymbolTable对象
  • 成员方法：1.public Value get(Key key)：根据键key，找对应的值
    2.public void put(Key key,Value val)：向符号表中插入一个键值对
    3.public void delete(Key key)：删除键为key的键值对
    4.public int size()：获取符号表的大小
  • 成员变量：1.private Node head：记录首结点
    2.private int N：记录符号表中键值对的个数

符号表的实现

public class SymbolTable<Key,Value> {
    private Node head;
    private int N;

    private class Node{
        public Key key;
        public Value value;
        public Node next;

        public Node(Key key,Value value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public SymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }

    public int size(){
        return N;
    }

    public void put(Key key,Value value){
        Node n = head;
        while (n.next!=null){
            n = n.next;
            if (n.key.equals(key)){
                n.value = value;
                return;
            }
        }

        Node newNode = new Node(key, value, null);
        Node oldFirst = head.next;
        newNode.next = oldFirst;
        head.next = newNode;

        N++;
    }

    public void delete(Key key){
        Node n = head;
        while (n.next!=null){
            if (n.next.key.equals(key)){
                n.next = n.next.next;
                N--;
                return;
            }
            n =n.next;
        }
    }

    public Value get(Key key){
        Node n = head;
        while (n.next!=null){
            n = n.next;
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }
}
public class SymbolTableTest {
    public static void main(String[] args) {
        SymbolTable<Integer, String> symbolTable = new SymbolTable<>();

        symbolTable.put(1,"aa");
        symbolTable.put(2,"bb");
        symbolTable.put(3,"cc");

        System.out.println("插入完毕后，元素的个数为："+symbolTable.size());

        symbolTable.put(2,"dd");
        System.out.println("替换完毕后的元素的个数为："+symbolTable.size());

        System.out.println("替换完毕后，键2对应的值为："+symbolTable.get(2));

        symbolTable.delete(2);
        System.out.println("删除完毕后,元素的个数："+symbolTable.size());
    }
}

有序符号表

  • 刚才实现的符号表，我们可以称之为无序符号表，因为在插入的时候，并没有考虑键值对的顺序，而在实际生活中，有时候
    我们需要根据键的大小进行排序，插入数据时要考虑顺序，那么接下来我们就实现一下有序符号表
public class OrderSymbolTable<Key extends Comparable<Key>,Value> {
    private Node head;
    private int N;

    private class Node{
        public Key key;
        public Value value;
        public Node next;

        public Node(Key key,Value value,Node next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    public OrderSymbolTable(){
        this.head = new Node(null,null,null);
        this.N = 0;
    }

    public int size(){
        return N;
    }

    public void put(Key key,Value value){
        Node curr = head.next;
        Node pre = head;
        while (curr!=null && key.compareTo(curr.key)>0){
            pre = curr;
            curr = curr.next;
        }

        if (curr!=null && key.compareTo(curr.key)==0){
            curr.value = value;
            return;
        }

        Node newNode = new Node(key, value, curr);
        pre.next = newNode;

        N++;
    }

    public void delete(Key key){
        Node n = head;
        while (n.next!=null){
            if (n.next.key.equals(key)){
                n.next = n.next.next;
                N--;
                return;
            }
            n =n.next;
        }
    }

    public Value get(Key key){
        Node n = head;
        while (n.next!=null){
            n = n.next;
            if (n.key.equals(key)){
                return n.value;
            }
        }
        return null;
    }
}
public class OrderSymbolTableTest {
    public static void main(String[] args) {
        OrderSymbolTable<Integer, String> table = new OrderSymbolTable<>();

        table.put(1,"张三");
        table.put(2,"李四");
        table.put(4,"赵六");
        table.put(7,"田七");

        table.put(3,"王五");
    }
}

标签：Node,符号表,队列,next,key,return,null,public
From： https://www.cnblogs.com/song-hua/p/16869294.html

相关文章

  • 2.队列
    环形队列环形队列理论环形队列的本质就是一个数组。用两个标识分别表示对头和队尾，在逻辑上呈现为一个环形当队列不为空时，对头指向头元素，队尾指向最后一个元素的下一个元......
  • JS数据结构与算法-队列结构
    队列结构一.认识队列受限的线性结构:我们已经学习了一种受限的线性结构:栈结构.并且已经知道这种受限的数据结构对于解决某些特定问题,会有特别的效果.下面,我们再......
  • 【Leetcode】 剑指offer：栈与队列 --Day01
    写在前面2023届秋招形势严峻，作为2024届本科生倍感压力。时间紧迫，需要加快脚步。计划之一是在未来的36天时间里通关Leetcode的剑指offer系列算法题。这一系列的学习周期为......
  • leetcode(34)优先队列系列题目
    218.天际线问题用SortedList存边界，每次删除或加入边界判断最高点是否变化classSolution:defgetSkyline(self,buildings:List[List[int]])->List[List[int]]:......
  • 025 通过链表学Rust之使用栈实现双端队列
    介绍视频地址：https://www.bilibili.com/video/av78062009/相关源码：https://github.com/anonymousGiga/Rust-link-list详细内容本节我们使用栈来实现双端队列。实现栈栈的实......
  • 14-组件篇之消息队列(3)_ev
                                                   ......
  • 使用单调队列解决 “滑动窗口最大值” 问题
    1\.单调队列的典型问题单调队列是一种用来高效地解决“滑动窗口最大值”问题的数据结构。举个例子，给定一个整数数组，要求输出数组中大小为K的窗口中的最大值，这就是窗口......
  • 13-组件篇之消息队列(2)_ev
    在app端生成一个客户端id到最后面进行去重就做到幂等性  面试重点      存储是最耗时的                   ......
  • 微服务Spring Boot 整合Redis 基于Redis的Stream 消息队列 实现异步秒杀下单
    文章目录​​一、什么是Redis消息队列？​​​​二、Redis消息队列--基于RedisList实现消息队列​​​​三、Redis消息队列--基于Pubsub的消息队列​​​​四、......
  • 阻塞队列 - BlockingQueue
     线程通信的一个工具。在任意时刻，不管并发有多高，在单JVM上面，同一时间永远只有一个线程能够对队列进行入队或者出队操作。1.线程安全的队列；2.队列类型：无限队列、有限队......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99