首页 > 试题广场 >

队列操作(后端开发卷)

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

热度指数：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

输出

算法知识视频讲解

亚索学Java

运用基础的数组模拟队列，将队列以及对队列的操作均放在一个类里面，代码略显得多，但是并不复杂，也有很多值得优化的地方。
仅就解题来说，要注意的是，队列要设置成环形队列，防止出现push很多次以后再pop很多次以后，不能再操作队列了，环形队列可以避免这一点。注意环形队列的几个要点;
1、环形“有尾巴”：设置rear指向最后一个元素的下一个位置，front指向第一个元素，初始值均为0，队列长度为：(rear-front+maxsize)%maxsize;
2、队列满的条件是：（rear+1）%maxsize=front;3、队列为空的条件是：rear==front；

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //输入数组和n
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int T = Integer.parseInt(line);
        int Max = 1000;//？
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < T; i++) {//T组测试数据
            Queue queue = new Queue(Max);//一个队列反复操作 则需要环形队列
            String line1 = sc.nextLine();
            int Q = Integer.parseInt(line1);//Q次操作
            for (int j = 0; j < Q; j++) {//Q次操作   把需要打印的操作的结果存放到一个数组res中 最后轮流换行打印输出
                String s = sc.nextLine();
                String[] s1 = s.split(" ");
                switch (s1[0]) {
                    case "PUSH": //插入队尾元素无返回
                        queue.push(s1[1]);
                        break;
                }
                switch (s1[0]) {
                    case "SIZE": //队列大小
                        res.add(queue.size());
                        break;
                }
                switch (s1[0]) {
                    case "TOP": //队列首元素查询
                        res.add(queue.top());
                        break;
                }
                switch (s1[0]) {
                    case "POP": //删除队首元素
                        if(queue.pop()!=null){
                            res.add(queue.pop());
                        }
                        break;
                }
                switch (s1[0]) {
                    case "CLEAR":
                        queue.clear();//清空队列 无返回
                        break;
                }
            }


        }
        for (int i = 0; i < res.size(); i++) {
            System.out.println(res.get(i));
        }
    }

}

class Queue {
    private int Maxsize;
    private int front;//指向队首
    private int rear;//指向队尾元素的后一个位置 初值为0
    private int[] arr;//存放数据

    public Queue(int maxsize) {
        Maxsize = maxsize;
        arr =new int[Maxsize];//数组不初始化，就是null 也无索引也无0
        front = 0;
        rear = 0;
    }

    public void push(String s) {
        int x = Integer.parseInt(s);
        arr[rear] = x;
        rear = (rear + 1) % Maxsize;
    }

    public Integer size() {
        return (rear - front + Maxsize) % Maxsize;
    }

    public Integer top() {
        if (rear == front) {//为空无法取出
            return -1;
        }
        return arr[front];
    }

    public Integer pop() {
        if (rear == front) { //为空无法删除
            return -1;
        }
        front = (front + 1) % Maxsize;//注意是加1取模  不改变arr 这就算删除队列一个元素了
        return null;
    }

    public void clear() {
        rear=front;//清空队列？？
    }

}

发表于 2021-07-06 13:38:39 回复(0)

一直吃一直胖

使用数组模拟队列，用两个int值代表队首和队尾，就可以很好的实现这些方法。

head=en就代表队列中无元素

head代表队首元素下标

en代表队尾元素下标

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
//#define mod 998244353
#define mod 1000000007
#define ll long long
using namespace std;
const int N=1e6+5;
const double ex=1e-8;
int n,m,k;
int a[N];
void solve(){
    int head=0,en=0;
    string s;
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="PUSH"){
            cin>>m;
            a[en++]=m;
        }
        else if(s=="TOP"){
            if(head==en)cout<<-1<<'\n';
            else cout<<a[head]<<'\n';
        }
        else if(s=="POP"){
            if(head==en)cout<<-1<<'\n';
            else head++;
        }
        else if(s=="SIZE"){
            cout<<en-head<<'\n';
        }
        else{
            en=head;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //cout<<fixed<<setprecision(10);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

编辑于 2022-01-07 19:46:20 回复(0)

pein531

java直接调用队列实现类的API

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        while(T -- > 0){
            int n = Integer.parseInt(br.readLine().trim());
            Queue<Integer> queue = new LinkedList<>();
            for(int i = 0; i < n; i++){
                String command = br.readLine();
                if(command.startsWith("PUSH")){
                    String[] params = command.split(" ");
                    int elem = Integer.parseInt(params[1]);
                    queue.offer(elem);
                }else if(command.equals("TOP")){
                    if(queue.isEmpty())
                        System.out.println(-1);
                    else
                        System.out.println(queue.peek());
                }else if(command.equals("POP")){
                    if(queue.isEmpty())
                        System.out.println(-1);
                    else
                        queue.poll();
                }else if(command.equals("SIZE")){
                    System.out.println(queue.size());
                }else if(command.equals("CLEAR"))
                    queue.clear();
            }
        }
    }
}

发表于 2021-07-22 14:34:05 回复(3)

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)

maoxiaomao

维护一个列表当一个假队列，出队O(n)，入队O(1)

T=int(input())
for i in range(T):  #有T组测试数据
    Q=int(input())  #改组测试数据有Q次操作
    q=[]
    for j in range(Q):
        s = input().strip().split()
        if len(s)==2:     #入队操作
            q.append(s[1])
        else:             #其他操作
            if s[0]=='TOP':          #查看队首
                if len(q)==0:print(-1)
                else:print(q[0])
            elif s[0]=='SIZE':
                print(len(q))
            elif s[0]=='POP':        #出队
                if len(q)==0:print(-1)
                else:del q[0]
            else:                    #clear清空操作
                while len(q)!=0:q.pop()

发表于 2021-06-02 21:06:07 回复(0)

C/C++

zhangbw_

使用数组模拟，维护一个front和一个rear指针

#include <iostream>
using namespace std;

const int MAX = 1e5 + 5;
int arr[MAX];

void solve() {
    int Q; cin >> Q;
    int rear = -1, front = -1;
    string ops;
    int val;
    while (Q--) {
        cin >> ops;
        if (ops == "PUSH") {
            cin >> val;
            arr[++rear] = val;
        } else if (ops == "POP") {
            if (front == rear) cout << "-1" << endl;
            else front++;
        } else if (ops == "TOP") {
            if (front == rear) cout << "-1" << endl;
            else cout << arr[front + 1] << endl;
        } else if (ops == "SIZE") {
            cout << rear - front << endl;
        } else {
            front = rear = -1;
        }
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        solve();
    }
}

发表于 2023-02-28 10:53:41 回复(0)

星瞳从小很可爱

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        Queue<int> list = new Queue<int>();
        int T = int.Parse(Console.ReadLine().Trim());
        while(T>0)
        {
            T--;
            int Q=int.Parse( Console.ReadLine());
            list.Clear();
            while(Q>0)
            {
                Q--;
                string[] instruction=Console.ReadLine().Trim().Split(' ');
                
                switch(instruction[0])
                {
                    case "PUSH": 
                        { 
                            list.Enqueue(int.Parse(instruction[1])); 
                            break; 
                        }
                    case "POP": 
                        { 
                            if (list.Count != 0)
                              list.Dequeue();
                          else
                              Console.WriteLine(-1);
                            break; 
                        }
                    case "TOP": 
                        { 
                            if (list.Count != 0) 
                             Console.WriteLine(list.Peek());
                            else
                                Console.WriteLine(-1);
                            break; 
                        }
                    case "SIZE": 
                        { 
                            Console.WriteLine(list.Count); 
                            break; 
                        }
                    case "CLEAR": 
                        { 
                            list.Clear(); 
                            break; 
                        }
                    default:break;
                }
            }
        }
    }
}

发表于 2022-04-20 18:46:54 回复(0)

我爱吃橘子122

group = int(input())
while group > 0:
    group -= 1
    number = int(input())
    l = []
    size = 0
    while number > 0:
        number -= 1
        command = input()
        if 'PUSH' in command:
            number0 = command.replace('PUSH ', '')
            number0 = int(number0)
            l.append(number0)
            size += 1
            continue
        if 'TOP' in command:
            if size > 0:
                print(l[0])
            else:
                print(-1)
            continue
        if 'POP' in command:
            if size > 0:
                size -= 1
                del l[0]
            else:
                print(-1)
            continue
        if 'SIZE' == command:
            print(size)
            continue
        if 'CLEAR' == command:
            l = []
            size = 0
            continue

发表于 2022-04-02 21:16:08 回复(0)

在迎接offer的考拉很糊涂

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int k;
    cin >> k;
    deque<int> q;
    for(int j = 0; j< k;j++)
    {
        string ming_li;
        cin >> ming_li;
        if( ming_li == "PUSH")
        {
            int num;
            cin >> num;
            q.push_back(num);
        }
        else if( ming_li == "TOP")
        {
            if(q.empty())
            {
                cout << -1 <<'\n';
                continue;
            }
            cout << q.front() <<'\n';
        }
        else if( ming_li == "POP")
        {
            if(q.empty())
                cout << -1<<'\n';
            q.pop_front();
        }
        else if( ming_li == "SIZE")
        {
            cout << q.size() <<'\n';
        }
        else if( ming_li == "CLEAR")
        {
            q.clear();
        }
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
 
    return 0;
}

这么写为什么是错误的，明明案例都是通过的，是因为使用了API吗。。。。。。

编辑于 2022-03-23 10:52:17 回复(1)

大白兔嘤嘤嘤

a = input('');
for i = 1:a
    b= input('');
    str = {};
    for ii = 1:b
    caozuo = strsplit(input('','s'));
    if length(caozuo)==2
        str = [str,caozuo{2}];
    else
        caozuo = caozuo{1};
        if strcmp(caozuo,'TOP')
            if length(str) ~= 0;disp((str{1,1})); else disp(-1);end
        elseif strcmp(caozuo,'POP')
            if length(str) ~= 0;str(1)=[]; else disp(-1);end
        elseif strcmp(caozuo,'SIZE')
            disp(length(str))
        elseif strcmp(caozuo,'CLEAR')
                str ={};
        end
     end
     end
end

哪位大神看看，总说我格式不对

发表于 2022-03-17 14:02:28 回复(0)

孤星丶泪

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = sc.nextInt();
        sc.nextLine();
        while (times > 0) {
            MyQueue que = new MyQueue();
            int n = sc.nextInt();
            sc.nextLine();
            for (int i = 0; i < n; i++) {
                String s = sc.nextLine();
                if(s.startsWith("PUSH")){
                    String[] strs = s.split("\\s+");
                    int val = Integer.parseInt(strs[1]);
                    que.push(val);
                }else{
                    switch (s){
                        case "TOP":
                            if (que.size()==0){
                                System.out.println(-1);
                            }else{
                                System.out.println(que.getHead());
                            }
                            break;
                        case "SIZE":
                            System.out.println(que.size());
                            break;
                        case "POP":
                            if(que.size()==0){
                                System.out.println(-1);
                            }else{
                                que.deque();
                            }
                            break;
                        case "CLEAR":
                            que = new MyQueue();
                            break;
                        default:
                            break;
                    }
                }
            }
            times--;
        }
    }

    static class MyQueue {

        public Node head;
        public Node tail;
        public int size;

        public MyQueue() {
            size = 0;
            head = new Node();
            tail = head;
        }


        public void push(int val) {
            //入队使用尾插法
            Node cur = new Node(val);
            cur.next = tail.next;
            tail.next = cur;
            tail = cur;
            size++;
        }

        public int deque() {
            //由于链表的特性，删除只能在头部删除
            //用head保存头节点
            if (size == 0) {
                return -1;
            } else {
                int x = head.next.val;
                head.next = head.next.next;
                size--;
                //关键性语句，如果队列中数据量为0
                //要回归到初始状态，防止head和tail的指向会出现错误
                if(size == 0){
                    head = new Node();
                    tail = head;
                }
                return x;
            }
        }

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

        public int size() {
            return size;
        }

        public int getHead() {
            if (size == 0) {
                return -1;
            } else {
                return head.next.val;
            }
        }
    }

    static class Node {

        int val;
        Node next;

        public Node(int val){
            this.val = val;
        }

        public Node(){
        }

    }
}

发表于 2021-09-03 15:19:04 回复(0)

onestan

#include <bits/stdc++.h>
using namespace std;

int main()
{
int T,Q;
cin>>T;
string temp1;
int temp2;
vector<int> temp3;
for(int i=0;i<T;++i)
{
temp3.clear();
cin>>Q;
for(int j=0;j<Q;++j)
{
cin>>temp1;
if(temp1=="PUSH")
{
cin>>temp2;
temp3.push_back(temp2);
}
else if(temp1=="TOP")
{
if(temp3.size()>0) cout<<temp3[0]<<endl;
else cout<<-1<<endl;
}
else if(temp1=="POP")
{
if(temp3.size()>0) temp3.erase(temp3.begin());
else cout<<-1<<endl;
}
else if(temp1=="SIZE") cout<<temp3.size()<<endl;
else temp3.clear();
}
}
return 0;
}

发表于 2021-08-15 15:01:04 回复(0)