首页 > 其他分享 >线性表 - 栈和队列

线性表 - 栈和队列

时间:2024-01-25 22:23:43浏览次数:29  
标签:return 线性表 队列 int boolean isEmpty capacity public

后进先出 LIFO

两种实现方式

  • 使用数组实现的叫静态栈
  • 使用链表实现的叫动态栈

相关题目

简单难度

225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
   
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
   
    public int pop() {
        return q1.poll();
    }
   
    public int top() {
        return q1.peek();
    }
   
    public boolean empty() {
        return q1.isEmpty();
    }
}

中等难度

71. 简化路径 https://leetcode.cn/problems/simplify-path/
class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        StringBuffer ans = new StringBuffer();
        if (stack.isEmpty()) {
            ans.append('/');
        } else {
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
        }
        return ans.toString();
    }
}

队列

先进先出 FIFO

相关题目

简单难度

933. 最近的请求次数 https://leetcode.cn/problems/number-of-recent-calls/
class RecentCounter {
    Queue<Integer> q;
    public RecentCounter() {
        q = new LinkedList<>();
    }
   
    public int ping(int t) {
        q.offer(t);
        while (q.peek().intValue() < t - 3000) {
            q.remove();
        }
        return q.size();
    }
}

中等难度

641. 设计循环双端队列 https://leetcode.cn/problems/design-circular-deque/
class MyCircularDeque {
    private int[] elements;
    private int rear, front;
    private int capacity;
    public MyCircularDeque(int k) {
        capacity = k + 1;
        rear = front = 0;
        elements = new int[k + 1];
    }
   
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }
   
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }
   
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }
   
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }
   
    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }
   
    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }
   
    public boolean isEmpty() {
        return rear == front;
    }
   
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}
/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

标签:return,线性表,队列,int,boolean,isEmpty,capacity,public
From: https://www.cnblogs.com/understanding-friends/p/17988319

相关文章

  • 【数据结构】72变的双端队列
    双端队列前言大家好,很高兴又和大家见面啦!!!在前面的篇章中,咱们详细介绍了队列这种新的数据结构,现在我们简单的回顾一下队列的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。数据的逻辑结构队列的数据元素在逻辑上是呈现线性结构,也就是说队列也是一种线性表,只不过是一种......
  • 进程间通信(队列和生产消费模型)
    (一)引入(1)什么是进程间的通信IPC进程间通信(Inter-ProcessCommunication,IPC)是指两个或多个进程之间进行信息交换的过程它是一种计算机编程技术,用于在不同的进程之间共享数据和资源(2)如何实现进程间通信借助于消息队列,进程可以将消息放入队列中,然后由另一个进程从队列中取......
  • 双端队列(deque)--python
    Python中的双端队列(deque)是一种特殊的数据结构,它允许在队列的两端进行插入和删除操作12。双端队列可以看成栈和队列的结合3。在Python中,我们可以使用collections模块中的deque类来创建双端队列12。下面是一些常用的操作方法1:Python`fromcollectionsimportdeque`#创建一个......
  • 基于Redis的Stream类型的完美消息队列解决方案(全)
    1概述2追加新消息,XADD,生产消息3从消息队列中获取消息,XREAD,消费消息4消息ID说明5消费者组模式,consumergroup6Pending等待列表7消息转移8坏消息问题,DeadLetter,死信问题9信息监控,XINFO10命令一览11Stream数据结构,RadixTree,基数树12相关产品1概述Redis5.......
  • 优先队列
    数学数学-组合数学数学-数论数学-博弈论数学-线性代数数学-概率期望动态规划动态规划-优化动态规划-背包进阶动态规划-计数dp动态规划-图上dp数据结构数据结构-线段树进阶数据结构-平衡树数据结构-Trie数据结构-分块数据结构-莫队数据结构-点分治数据结构-......
  • 栈与队列解题报告
    刚考完试。重返oi!这次挂掉80pts20pts挂在T1,未考虑读的时候数字占多个字符,60pts挂在多测未清空上。T1https://www.luogu.com.cn/problem/P1981经典表达式求值。我这里采用了一种比较奇特的方法。我以每个加号为分界线。当我遍历到其中一个加号时,保证加号之前只有一个数。然......
  • rocketmq--死信队列
    在RocketMQ中,死信队列(DeadLetterQueue,DLQ)用于存放无法成功消费的消息。当消息重试消费次数超过设定的阈值后,消息将被转移到死信队列。使用SpringBoot集成RocketMQ时,可以通过以下步骤来处理死信队列中的消息。首先,在pom.xml中添加RocketMQSpringBootStarter的依赖:<dependen......
  • 基于信号量的环形队列的生成消费模型(万字长文详解)
    linux线程之信号量POSIX信号量阻塞队列的缺陷==这是一个我们自己的实现阻塞队列!==classBlockQueue{public:BlockQueue(constint&maxcap=gmaxcap):maxcap_(maxcap){pthread_mutex_init(&mutex_,nullptr);......
  • 第三章 Spring Boot 整合 Kafka消息队列 消息者
    ​ 前言        Kafka是一个消息队列产品,基于Topicpartitions的设计,能达到非常高的消息发送处理性能。本文主是基于SpirngBoot封装了Apache的Kafka-client,用于在SpringBoot项目里快速集成kafka。 一、Kafka是什么?ApacheKafka是分布式发布-订阅消息系统。......
  • .NET 6 实现一个任务队列,且在不同线程中调用队列,队列始终都是串行执行
    在.NET6中,要实现一个任务队列,确保队列中的任务始终串行执行,即使它们是由不同线程调用的,你可以使用Channel<T>结合Task.Run或者更简单地使用BlockingCollection<T>与Task.Factory.StartNew或async/await模式。不过,为了保持代码的简洁性和现代性,我会推荐使用Channel<T>结合async/aw......