队列操作(后端开发卷)

[编程题]队列操作(后端开发卷)

热度指数：3066 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

数据结构基础之一——队列
队列有五种基本操作，插入队尾、取出队首、删除队首、队列大小、清空队列。

现在让你模拟一个队列的操作，具体格式参考输入。

注意本题有多组输入。

数据范围：操作数满足 $0 \le n \le 100000 \$ ，读入的数都满足 $0 \le val \le 1000 \$
进阶：空间复杂度 $O(n)\$ ，所有操作的时间复杂度都满足 $O(1) \$

输入描述:

第一行输入一个整数T，表示接下来有T组测试数据。
对于每组测试数据：
第一行输入一个整数Q，表示有Q次操作。
接下来Q行，每行输入一种队列操作方式，具体格式如下：

初始状态下队列为空。

插入队尾：PUSH X
取出队首：TOP//仅仅是看一下队首元素，不要把队首元素删除
删除队首：POP
队列大小：SIZE
清空队列：CLEAR

1<=T<=100
1<=Q,x<=1000
保证操作为以上5种的任意一种。

输出描述:

对于每组测试数据：
如果操作为“取出队首”，输出队首元素，如果无法取出，输出“-1”
如果操作为“删除队首”，如果无法删除，输出“-1”
如果操作为“队列大小”，输出队列大小
其他操作无需输出

示例1

输入

2
7
PUSH 1
PUSH 2
TOP
POP
TOP
POP
POP
5
PUSH 1
PUSH 2
SIZE
POP
SIZE

输出

算法知识视频讲解

JavaScript

Williammm

class Queue {
    constructor(n){
      this.maxsize=n //数组最大容量
      this.arr = new Array(n)//用于存数据的数组，模拟队列
      this.front = this.rear = 0//初始化下标值，指向队列头部
    }
    push(n){
        this.arr[this.rear]=n
        this.rear = (this.rear+1)%this.maxsize
    }
    top(){
        if(this.rear==this.front){//为空无法取出
            return -1
        }
        return this.arr[this.front]
    }
    pop(){
        if(this.rear==this.front){//为空无法删除
            return -1
        }
        this.front = (this.front+1)%this.maxsize
        return null
    }
    size(){
        return (this.rear-this.front+this.maxsize)%this.maxsize
    }
    clear(){
        this.rear = this.front
    }
}
var T = parseInt(readline())
for(var i=0;i<T;i++){
    let queue = new Queue(1000)
    var Q = parseInt(readline())
    for(var j=0;j<Q;j++){
        var lines = readline().split(" ")
        switch (lines[0]){
            case "PUSH":
                queue.push(lines[1])
                break
        }
        switch (lines[0]){
            case "TOP":
                console.log(queue.top())
                break
        }
        switch (lines[0]){
            case "POP":
                if(queue.pop()!==null){
                console.log(queue.pop())
                }
                break
        }
        switch (lines[0]){
            case "SIZE":
                console.log(queue.size())
                break
        }
        switch (lines[0]){
            case "CLEAR":
                queue.clear()
                break
        }
        
    }
}

发表于 2021-08-24 17:22:33 回复(0)