CodeTailor

1
class ArrayDeque:
2
    """基于数组的双端队列实现（循环数组）"""
3
    def __init__(self, capacity=10):
4
        self.capacity = capacity
5
        self.deque = [None] * capacity
6
        self.front = 0  # 指向队首元素
7
        self.rear = 0   # 指向队尾的下一个位置
8
        self.size = 0
9

10
    def __str__(self):
11
        if self.is_empty():
12
            return "Deque: []"
13

14
        elements = []
15
        for i in range(self.size):
16
            idx = (self.front + i) % self.capacity
17
            elements.append(str(self.deque[idx]))
18
        return f"Deque: [{', '.join(elements)}]"
19

20
    def is_empty(self):
21
        return self.size == 0
22

23
    def is_full(self):
24
        return self.size == self.capacity
25

26
    def _resize(self):
27
        """动态扩容"""
28
        self.capacity *= 2
29
        new_deque = [None] * self.capacity
30

31
        for i in range(self.size):
32
            old_idx = (self.front + i) % (self.capacity // 2)
33
            new_deque[i] = self.deque[old_idx]
34

35
        self.deque = new_deque
36
        self.front = 0
37
        self.rear = self.size
38

39
    def add_front(self, value):
40
        """前端添加 - O(1)"""
41
        if self.is_full():
42
            self._resize()
43

44
        self.front = (self.front - 1) % self.capacity
45
        self.deque[self.front] = value
46
        self.size += 1
47

48
    def add_rear(self, value):
49
        """后端添加 - O(1)"""
50
        if self.is_full():
51
            self._resize()
52

53
        self.deque[self.rear] = value
54
        self.rear = (self.rear + 1) % self.capacity
55
        self.size += 1
56

57
    def remove_front(self):
58
        """前端移除 - O(1)"""
59
        if self.is_empty():
60
            raise IndexError("Remove from empty deque")
61

62
        value = self.deque[self.front]
63
        self.deque[self.front] = None
64
        self.front = (self.front + 1) % self.capacity
65
        self.size -= 1
66
        return value
67

68
    def remove_rear(self):
69
        """后端移除 - O(1)"""
70
        if self.is_empty():
71
            raise IndexError("Remove from empty deque")
72

73
        self.rear = (self.rear - 1) % self.capacity
74
        value = self.deque[self.rear]
75
        self.deque[self.rear] = None
76
        self.size -= 1
77
        return value
78

79
    def peek_front(self):
80
        """查看前端 - O(1)"""
81
        if self.is_empty():
82
            raise IndexError("Peek from empty deque")
83
        return self.deque[self.front]
84

85
    def peek_rear(self):
86
        """查看后端 - O(1)"""
87
        if self.is_empty():
88
            raise IndexError("Peek from empty deque")
89
        return self.deque[(self.rear - 1) % self.capacity]
90

91
    def size(self):
92
        return self.size

1
deque = ArrayDeque(5)
2
deque.add_rear(1)    # 后端添加
3
deque.add_rear(2)
4
deque.add_front(0)   # 前端添加
5
deque.add_rear(3)
6
print(deque)  # Deque: [0, 1, 2, 3]
7
print("前端:", deque.peek_front())  # 0
8
print("后端:", deque.peek_rear())   # 3
9
print("移除前端:", deque.remove_front())  # 0
10
print("移除后端:", deque.remove_rear())   # 3
11
print(deque)  # Deque: [1, 2]

1
class PrinterQueue:
2
    """打印机队列模拟"""
3
    def __init__(self):
4
        self.queue = deque()
5
        self.current_job = None
6

7
    def add_print_job(self, document, pages, priority="normal"):
8
        """添加打印任务"""
9
        job = {
10
            'document': document,
11
            'pages': pages,
12
            'priority': priority,
13
            'status': 'waiting'
14
        }
15

16
        # 根据优先级插入
17
        if priority == "high":
18
            # 插入到普通任务前面
19
            temp_queue = deque()
20
            inserted = False
21
            while self.queue:
22
                job_in_queue = self.queue.popleft()
23
                if not inserted and job_in_queue['priority'] == "normal":
24
                    temp_queue.append(job)
25
                    inserted = True
26
                temp_queue.append(job_in_queue)
27

28
            if not inserted:
29
                temp_queue.append(job)
30

31
            self.queue = temp_queue
32
        else:
33
            self.queue.append(job)
34

35
        print(f"添加打印任务: {document} ({pages}页)")
36

37
    def process_next_job(self):
38
        """处理下一个任务"""
39
        if not self.queue:
40
            print("没有待处理的任务")
41
            return None
42

43
        self.current_job = self.queue.popleft()
44
        self.current_job['status'] = 'printing'
45
        print(f"正在打印: {self.current_job['document']}")
46
        return self.current_job
47

48
    def cancel_job(self, document):
49
        """取消指定任务"""
50
        for job in list(self.queue):
51
            if job['document'] == document:
52
                self.queue.remove(job)
53
                print(f"已取消任务: {document}")
54
                return True
55
        print(f"未找到任务: {document}")
56
        return False
57

58
    def show_queue(self):
59
        """显示当前队列"""
60
        print("\n当前打印队列:")
61
        for i, job in enumerate(self.queue, 1):
62
            print(f"{i}. {job['document']} ({job['pages']}页) - {job['priority']}优先级")