解题思路

  1. 使用一个固定大小的数组来存储队列元素。
  2. 维护两个指针 head 和 tail，分别指向队首和队尾。
  3. push 操作：将元素加入队尾，更新 tail 指针。
  4. pop 操作：输出并移除队首元素，更新 head 指针。
  5. front 操作：输出队首元素。
  6. 检查队列是否满或空，以决定是否输出 "full" 或 "empty"。

代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class CircularQueue {
private:
    vector<int> data;
    int head, tail, size, capacity;

public:
    CircularQueue(int n) : data(n), head(0), tail(0), size(0), capacity(n) {}

    void push(int x) {
        if (size == capacity) {
            cout << "full\n";
        } else {
            data[tail] = x;
            tail = (tail + 1) % capacity;
            size++;
        }
    }

    void pop() {
        if (size == 0) {
            cout << "empty\n";
        } else {
            cout << data[head] << "\n";
            head = (head + 1) % capacity;
            size--;
        }
    }

    void front() {
        if (size == 0) {
            cout << "empty\n";
        } else {
            cout << data[head] << "\n";
        }
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    CircularQueue cq(n);

    string op;
    while (q--) {
        cin >> op;
        if (op == "push") {
            int x;
            cin >> x;
            cq.push(x);
        } else if (op == "pop") {
            cq.pop();
        } else if (op == "front") {
            cq.front();
        }
    }
    return 0;
}

import java.util.Scanner;

class CircularQueue {
    private int[] data;
    private int head, tail, size, capacity;

    public CircularQueue(int n) {
        data = new int[n];
        head = 0;
        tail = 0;
        size = 0;
        capacity = n;
    }

    public void push(int x) {
        if (size == capacity) {
            System.out.println("full");
        } else {
            data[tail] = x;
            tail = (tail + 1) % capacity;
            size++;
        }
    }

    public void pop() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(data[head]);
            head = (head + 1) % capacity;
            size--;
        }
    }

    public void front() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(data[head]);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        CircularQueue cq = new CircularQueue(n);

        for (int i = 0; i < q; i++) {
            String op = sc.next();
            if (op.equals("push")) {
                int x = sc.nextInt();
                cq.push(x);
            } else if (op.equals("pop")) {
                cq.pop();
            } else if (op.equals("front")) {
                cq.front();
            }
        }
    }
}

class CircularQueue:
    def __init__(self, n):
        self.data = [0] * n
        self.head = 0
        self.tail = 0
        self.size = 0
        self.capacity = n

    def push(self, x):
        if self.size == self.capacity:
            print("full")
        else:
            self.data[self.tail] = x
            self.tail = (self.tail + 1) % self.capacity
            self.size += 1

    def pop(self):
        if self.size == 0:
            print("empty")
        else:
            print(self.data[self.head])
            self.head = (self.head + 1) % self.capacity
            self.size -= 1

    def front(self):
        if self.size == 0:
            print("empty")
        else:
            print(self.data[self.head])

# 读取输入
n, q = map(int, input().split())
cq = CircularQueue(n)

for _ in range(q):
    op = input().strip()
    if op.startswith("push"):
        _, x = op.split()
        cq.push(int(x))
    elif op == "pop":
        cq.pop()
    elif op == "front":
        cq.front()

算法及复杂度分析

  • 算法：循环队列的基本操作
  • 时间复杂度： 对于每个操作。
  • 空间复杂度：，其中 是队列的容量。

这个问题考察了循环队列的实现，重点在于正确维护 head 和 tail 指针的移动和边界条件的处理。