Python và mã nguồn

Deque là một Queue hoạt động ở cả hai đầu. Dữ liệu có thể được chèn vào phần đầu hoặc phần đuôi và được lấy từ phần đầu hoặc phần đuôi

Động lực

• tuần tự

• Truy cập hạn chế

• Khi nào tôi thực sự có thể sử dụng cái này?
  • Theo dõi thời gian chạy tối thiểu và tối đa cho mã đang được kiểm tra
  • Mô hình hóa cách hành khách lên và xuống máy bay với hai lối vào/lối ra

Thuộc tính

• đầu
• đuôi
• is_empty
• kích thước

hoạt động

• add_first[]
• add_last[]
• xóa_đầu tiên []
• xóa_last[]
• thông thoáng[]

Như chúng ta đã thực hiện trong các phần trước, chúng ta sẽ tạo một lớp mới để triển khai kiểu dữ liệu trừu tượng. Một lần nữa, danh sách Python sẽ cung cấp một tập hợp các phương thức rất hay để xây dựng các chi tiết của hàng đợi. Việc triển khai [] của chúng tôi sẽ giả định rằng phía sau hàng đợi ở vị trí 0 trong danh sách

Liệt kê 1

 1class Deque:
 2    def __init__[self]:
 3        self.items = []
 4
 5    def isEmpty[self]:
 6        return self.items == []
 7
 8    def addFront[self, item]:
 9        self.items.append[item]
10
11    def addRear[self, item]:
12        self.items.insert[0,item]
13
14    def removeFront[self]:
15        return self.items.pop[]
16
17    def removeRear[self]:
18        return self.items.pop[0]
19
20    def size[self]:
21        return len[self.items]

Trong removeFront, chúng tôi sử dụng phương pháp pop để xóa phần tử cuối cùng khỏi danh sách. Tuy nhiên, trong removeRear, phương thức pop[0] phải loại bỏ phần tử đầu tiên của danh sách. Tương tự như vậy, chúng ta cần sử dụng phương thức insert [dòng 12] trong addRear vì phương thức append giả định việc thêm một phần tử mới vào cuối danh sách

CodeLens 1 hiển thị hoạt động của lớp Deque khi chúng tôi thực hiện chuỗi hoạt động từ

Hoạt động. Ví dụ CodeLens Deque Operations [deqtest]

Bạn có thể thấy nhiều điểm tương đồng với mã Python đã được mô tả cho ngăn xếp và hàng đợi. Bạn cũng có thể quan sát thấy rằng trong cách triển khai này, việc thêm và xóa các mục từ phía trước là O[1] trong khi việc thêm và xóa từ phía sau là O[n]. Điều này được mong đợi với các hoạt động phổ biến xuất hiện để thêm và xóa các mục. Một lần nữa, điều quan trọng là phải biết phân công tiền tuyến, hậu phương trong thực hiện.

Một danh sách được liên kết với một khối gồm 64 con trỏ [được đặt thành null] được tạo. Chỉ mục bên phải được khởi tạo ở giữa khối [31] và được dùng để chỉ đối tượng cuối cùng trong hàng đợi. Chỉ mục bên trái được khởi tạo ở giữa khối cộng với một [32] và được sử dụng để chỉ đối tượng đầu tiên trong hàng đợi. Hiện tại, chúng tôi đã không đẩy bất cứ thứ gì vào bộ bài của mình nên tất cả các con trỏ đều không trỏ đến gì

Cấu trúc deque bên trong C cũng có một con trỏ tới khối bên trái nhất và một con trỏ tới khối bên phải nhất. Cả hai hiện đang trỏ đến khối duy nhất này ở trên. Ngoài ra còn có một thuộc tính độ dài tối đa tùy chọn có thể được sử dụng cho hàng đợi giới hạn

typedef struct {
    ...
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;
    Py_ssize_t rightindex;
    ...
    Py_ssize_t maxlen;
    ...
} dequeobject;

Một khối có một liên kết trái và phải. Nó cũng có một mảng gồm 64 con trỏ tới các đối tượng

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

Hãy thêm hai đối tượng vào bộ bài của chúng ta. Ở đây chúng ta sẽ sử dụng các chuỗi có nhãn e1, e2, … Phương thức append thực sự là append-right. Ngoài ra còn có append-left

>>> d.append['e1']
>>> d.append['e2']
>>> d
deque[['e1', 'e2']]

Chỉ mục bên phải đã tăng thêm hai [33] và vẫn trỏ đến đối tượng cuối cùng của deque. Chỉ số bên trái không di chuyển và vẫn trỏ đến đối tượng đầu tiên của deque. Sơ đồ bên dưới hiển thị các đối tượng chuỗi bên trong hàng đợi để đơn giản hóa, trong khi thực tế chúng được trỏ tới

Hàm C sau đây được gọi nội bộ. Nó lấy đối tượng deque và đối tượng để nối thêm. Kích thước của boong được tăng thêm một. Kích thước của hàng đợi là những gì được trả về khi bạn sử dụng hàm len Python

static inline int
deque_append_internal[dequeobject *deque, PyObject *item, ...]
{
    ...
    Py_SET_SIZE[deque, Py_SIZE[deque] + 1];
    deque->rightindex++;
    deque->rightblock->data[deque->rightindex] = item;
    ...
}

Hãy nối chuỗi e3 với e32

>>> for i in range[3, 33]: d.append['e%d' % i]
>>> d
deque[['e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11', 'e12', 'e13', 'e14', 'e15', 'e16', 'e17', 'e18', 'e19', 'e20', 'e21', 'e22', 'e23', 'e24', 'e25', 'e26', 'e27', 'e28', 'e29', 'e30', 'e31', 'e32']]

Chỉ mục bên phải hiện đang trỏ đến chỉ mục lớn nhất trong khối đầu tiên của chúng tôi

Điều gì xảy ra nếu chúng ta thêm một chuỗi nữa?

>>> d.append['e33']
>>> d
deque[['e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'e9', 'e10', 'e11', 'e12', 'e13', 'e14', 'e15', 'e16', 'e17', 'e18', 'e19', 'e20', 'e21', 'e22', 'e23', 'e24', 'e25', 'e26', 'e27', 'e28', 'e29', 'e30', 'e31', 'e32', 'e33']]

Một khối mới được phân bổ. Chỉ mục bên phải bây giờ trỏ đến chỉ mục đầu tiên của khối mới. Con trỏ khối bên trái tiếp tục trỏ đến khối đầu tiên. Con trỏ khối bên phải bây giờ trỏ đến khối mới

Chức năng bên trong tương tự được gọi như trên nhưng một đoạn mã bổ sung được thực thi để phân bổ một khối mới, cập nhật các liên kết khối và con trỏ khối bên phải

static inline int
deque_append_internal[dequeobject *deque, PyObject *item, Py_ssize_t maxlen]
{
    if [deque->rightindex == BLOCKLEN - 1] {
        block *b = newblock[];
        if [b == NULL]
            return -1;
        b->leftlink = deque->rightblock;
        deque->rightblock->rightlink = b;
        deque->rightblock = b;
        deque->rightindex = -1;
    }
    Py_SET_SIZE[deque, Py_SIZE[deque] + 1];
    deque->rightindex++;
    deque->rightblock->data[deque->rightindex] = item;
    ...
}

Bây giờ chúng ta đã xem phương thức append, chúng ta có thể chuyển sang phương thức popleft. Chúng tôi có thể bật đối tượng đầu tiên trong hàng đợi của mình

________số 8_______

Chỉ mục bên trái trỏ đến đối tượng đầu tiên trong hàng đợi của chúng tôi. Nó tăng lên một và hiện đang trỏ đến chỉ số 33. Chuỗi e1 đã được trả về

Chúng ta có thể thấy trong hàm bên trong popleft rằng kích thước của hàng đợi cũng giảm đi một

static PyObject *
deque_popleft[dequeobject *deque, PyObject *unused]
{
    PyObject *item;
    ...
    item = deque->leftblock->data[deque->leftindex];
    deque->leftindex++;
    Py_SET_SIZE[deque, Py_SIZE[deque] - 1];
    ...
    return item;
}

Hãy tiếp tục và bật tất cả các đối tượng trong khối deque bên trái. Chuỗi e2 đến e32 đã được trả lại. Chỉ số bên trái không được hiển thị ở đây và bây giờ bằng 64

Chỉ số bên trái bằng với độ dài khối [64], khối bên trái có thể được giải phóng để tiết kiệm bộ nhớ. Chỉ số bên trái được đặt thành 0. Con trỏ khối trái và khối phải tương ứng hiện đang trỏ đến cùng một khối

typedef struct {
    ...
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;
    Py_ssize_t rightindex;
    ...
    Py_ssize_t maxlen;
    ...
} dequeobject;

Chúng tôi đã xem xét điều gì sẽ xảy ra khi chúng tôi nối vào cuối hàng đợi [nối bên phải] và khi chúng tôi xuất hiện từ đầu hàng đợi [bật bên trái]. Các phương thức appendleft và pop [pop right] có cơ chế bên trong tương tự nhau

Điều gì là tốt trong mã Python?

Python có đủ không?

Tại sao sử dụng deque thay vì danh sách?

Tại sao lại sử dụng deque trong Python?