队列操作(后端开发卷)

运用基础的数组模拟队列，将队列以及对队列的操作均放在一个类里面，代码略显得多，但是并不复杂，也有很多值得优化的地方。
仅就解题来说，要注意的是，队列要设置成环形队列，防止出现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;//清空队列？？
    }

}

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
        }
        
    }
}

使用数组模拟，维护一个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();
    }
}

基于链表实现：

#include <iostream>
#include <string>
#include <memory>
using namespace std;
struct ListNode
{
    int value_;
    unique_ptr next_;
    explicit ListNode(int x) : value_{x}, next_{nullptr} {}
};
class LinkedListQueue
{
private:
    unique_ptr front_;
    ListNode *rear_ {nullptr};
    int queue_size_ {0};
public:
    LinkedListQueue () = default;
    LinkedListQueue(const LinkedListQueue&) = delete;
    LinkedListQueue& operator=(const LinkedListQueue&) = delete;
    // 获取长度
    [[nodiscard]] int get_size() const
    {
        return queue_size_;
    }
    // 判断是否为空
    [[nodiscard]] bool is_empty() const
    {
        return queue_size_ == 0;
    }
    // 入队（插入队尾）：在尾节点后面添加num节点
    void push(int num)
    {
        // 新建一个num节点
        auto node = make_unique(num);
        // 当队列为空时，将头、尾节点都指向num节点
        if(is_empty())
        {
            rear_ = node.get();      // 将node的原始指针保存至rear_
            front_ = std::move(node);   // 转移所有权到front_
        }
        else // 若队列不为空，将该节点添加至尾节点之后
        {
            rear_->next_ = std::move(node);     // 将当前尾节点的下一个节点指向num节点
            rear_ = rear_->next_.get();     // 更新尾节点为num节点
        }
        queue_size_++;
    }
    // 取出队首（仅查看队首元素）
    [[nodiscard]] int top() const
    {
        // 如果队列为空，直接返回-1
        if(is_empty())
        {
            return -1;
        }
        else // 否则返回队首元素
        {
            return front_->value_;
        }
    }
    // 删除队首：将队首节点删除并返回删除的元素
    int pop()
    {
        // 如果当前队列为空，则无法删除，输出-1
        if(is_empty())
        {
            return -1;
        }
        // 获取队首元素
        int num = front_->value_;
        // 如果队首节点等于队尾节点，表明这是最后一个节点
        if(front_.get() == rear_)
        {
            rear_ = nullptr; // 需要手动将队尾节点置空
        }
        // 让队首节点指向下一个节点
        front_ = std::move(front_->next_);// unique_ptr会自动删除旧节点
        queue_size_--;
        return num;
    }
    // 清空队列
    void clear()
    {      
        front_ = nullptr;
        rear_ = nullptr;
        queue_size_ = 0;
    }
};
int main() 
{
    int n;
    cin >> n;
    while(n--)
    {
        int q;
        cin >> q;
        LinkedListQueue queue;
        string manipulation;
        while(q--)
        {
            cin >> manipulation;
            if(manipulation == "PUSH")
            {
                int x;
                cin >> x;
                queue.push(x);
            }
            else if (manipulation == "TOP")
            {
                cout << queue.top() << endl;
            }
            else if (manipulation == "POP")
            {
                int res = queue.pop();
                if(res == -1)
                {
                    cout << res << endl;
                }
            }
            else if (manipulation == "SIZE") 
            {
                cout << queue.get_size() << endl;
            }
            else if (manipulation == "CLEAR")
            {
                queue.clear();
            }
        }
    }
    return 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;
                }
            }
        }
    }
}

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

#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吗。。。。。。

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

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

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(){
        }

    }
}