Struktur data Python dan pembelajaran algoritma baris gilir dua hujung

Artikel ini membawa anda pengetahuan yang berkaitan tentang python Ia terutamanya memperkenalkan isu yang berkaitan dengan baris gilir dua hujung, termasuk konsep asas baris gilir dua hujung, pelaksanaan baris gilir dua hujung dan dua hujung. Pemakaian baris gilir akhir, saya harap ia akan membantu semua orang.

Pembelajaran yang disyorkan: Tutorial python

0 Objektif pembelajaran

Baris gilir dua hujung ialah data linear lain struktur. Walaupun ia juga merupakan jadual linear terhad, tidak seperti tindanan dan baris gilir, baris gilir dua hujung mempunyai sedikit sekatan operasi asasnya juga merupakan subset operasi jadual linear, tetapi dari perspektif jenis data, ia berbeza daripada jadual Linear sangat berbeza. . Bahagian ini akan memperkenalkan definisi baris gilir dua hujung dan pelaksanaannya yang berbeza, dan memberikan beberapa aplikasi praktikal baris gilir dua hujung.
Dengan mengkaji bahagian ini, anda harus menguasai kandungan berikut:

• Konsep asas dan kaedah pelaksanaan yang berbeza bagi baris gilir dua hujung
• Pelaksanaan dan kerumitan masa operasi asas dua kali baris gilir -berakhir
• Gunakan operasi asas baris gilir dua hujung untuk melaksanakan algoritma kompleks

1.1 Konsep asas baris gilir dua hujung

1. Konsep asas baris gilir dua hujung

Baris gilir dua hujung (double-end queue, deque) juga merupakan senarai linear di mana operasi sisipan dan pemadaman dihadkan kepada kedua-dua hujung jujukan, tetapi tidak seperti tindanan dan baris gilir, baris gilir dua hujung mempunyai sedikit sekatan , untuk baris gilir dua hujung, kedua-dua ekor (rear) dan kepala (front) baris gilir membenarkan elemen untuk dimasukkan dan dipadamkan. Elemen baharu boleh ditambah pada kepala atau ekor baris gilir. Begitu juga, elemen sedia ada boleh dialih keluar dari kedua-dua hujung. Dari satu segi, baris gilir dua hujung boleh dianggap sebagai gabungan timbunan dan baris gilir.

Walaupun baris gilir dua hujung mempunyai banyak ciri tindanan dan baris gilir, ia tidak memerlukan mengikut LIFO prinsip dan FIFO prinsip yang ditakrifkan oleh kedua-dua struktur data ini .

1.2 Jenis data abstrak baris gilir dua hujung

Selain menambah dan mengalih keluar elemen, baris gilir dua hujung juga mempunyai operasi tambahan seperti permulaan, penghakiman kosong baris gilir dan penentuan panjang giliran. Khususnya, jenis data abstrak deque ditakrifkan seperti berikut:

Operasi asas:
1. __itit__(): Mulakan deque
Buat deque kosong
   2. size(): Dapatkan dan kembalikan bilangan elemen n
     Jika baris gilir dua hujung kosong, kembalikan integer 0
   3. isempty(): Tentukan sama ada baris gilir dua hujung kosong
 Nilai sama ada elemen disimpan dalam baris gilir dua hujung
 4. addfront(data): Tambah elemen pada kepala baris gilir dua hujung
  Masukkan data elemen ke dalam kepala baris gilir
 5. addrear(data): Double Tambah elemen pada penghujung baris gilir dua hujung
    Masukkan data elemen ke penghujung baris gilir
  6. removefront(): Padamkan elemen kepala double- baris gilir berakhir
    Padam dan kembalikan elemen kepala baris gilir
  7. removerear(): Padam Elemen ekor baris gilir dua hujung
  Padam dan kembalikan elemen ekor baris gilir

2. Pelaksanaan baris gilir dua hujung

Seperti baris gilir biasa, baris gilir dua hujung juga mempunyai storan berurutan dan Terdapat dua kaedah perwakilan storan storan rantai.

2.1 Pelaksanaan Deque Berurutan Elemen dari kepala baris gilir ke ekor baris gilir dua hujung perlu menggunakan dua penunjuk dan

untuk menunjukkan kedudukan baris gilir elemen kepala dan elemen ekor giliran masing-masing. Apabila memulakan deque kosong,

, apabila elemen dimasukkan ke dalam baris gilir, front, dan apabila elemen dinyah gilir, rear Pada masa yang sama, untuk menggunakan semula ruang kosong, kami menganggap ruang gelang ekor daripada deque berurutan, Ruang terakhir dan ruang pertama dianggap sebagai ruang berterusan (atas sebab tertentu, sila rujuk ): front=rear=0rear 加 1front 加 1

Begitu juga, berjujukan baris gilir dua hujung boleh menjadi panjang tetap dan Panjang dinamik, apabila baris gilir dua hujung penuh, baris gilir dua hujung berurutan tetap panjang akan membuang baris gilir dua hujung penuh pengecualian, dan baris gilir dua hujung berurutan dinamik akan secara dinamik memohon ruang kosong.

2.1.1 Permulaan deque

Permulaan deque berurutan memerlukan 4 maklumat: senarai digunakan untuk menyimpan elemen data,

Digunakan untuk menyimpan panjang maksimum senarai

, dan deque dan max_size digunakan untuk merekod indeks elemen kepala dan elemen ekor masing-masing: queue

class Deque:
    def __init__(self, max_size=6):
        self.max_size = max_size
        self.deque = [None] * self.max_size
        self.front = 0
        self.rear = 0

2.1.2 Cari panjang deque

Oleh kerana front dan rear digunakan untuk merekod indeks elemen kepala dan elemen ekor masing-masing , jadi kami Panjang baris gilir dua hujung boleh dikira dengan mudah pada masa yang sama, kita perlu mempertimbangkan bahawa baris gilir dua hujung ialah barisan bulat front mungkin lebih besar daripada rear dan tidak boleh secara langsung melalui rear-front. Kita perlu menggunakan pengiraan formula untuk menyelesaikan masalah ini:

Python dilaksanakan seperti berikut:

    def size(self):
        return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 Menentukan bahawa baris gilir dua hujung kosong

Menurut front dan rear Nilai boleh dengan mudah menentukan sama ada baris gilir dua hujung kosong:

    def isempty(self):
        return self.rear==self.front

2.1.4 Tentukan sama ada baris gilir dua hujung penuh

Mengikut nilai front dan rear Nilai dengan mudah boleh menentukan sama ada terdapat ruang kosong dalam dua baris gilir -berakhir:

    def isfull(self):
        return ((self.rear+1) % self.max_size == self.front)

2.1.5 Menambah elemen pada kepala dan ekor baris gilir dua hujung

Apabila menambah elemen, anda perlu terlebih dahulu menentukan baris gilir dua hujung Sama ada terdapat ruang kosong dalam baris gilir akhir, dan kemudian bergantung pada sama ada baris gilir dua hujung ialah baris gilir dua hujung berurutan panjang tetap atau baris gilir dua hujung berjujukan dinamik, operasi menambah elemen adalah sedikit berbeza:
[Tambah operasi Elemen baris gilir dua hujung jujukan panjang tetap] Jika baris gilir penuh, pengecualian akan dilemparkan:

    # 注意队头和队尾修改索引的添加元素的不同顺序
    def addrear(self, data):
        if not self.isfull():
            self.deque[self.rear] = data
            self.rear = (self.rear+1) % self.max_size        else:
            raise IndexError("Full Deque Exception")
    
    def addfront(self, data):
        if self.isfull():
            self.resize()
        if self.isempty():
            # 当Struktur data Python dan pembelajaran algoritma baris gilir dua hujung
            self.deque[self.rear] = data
            self.rear = (self.rear+1) % self.max_size        else:
            self.front = (self.front - 1 + self.max_size) % self.max_size
            self.deque[self.front] = data

[Tambah operasi elemen jujukan dinamik deque] Jika deque penuh, mohon ruang yang baharu dahulu, dan kemudian lakukan operasi tambah:

    def resize(self):
        new_size = 2 * self.max_size
        new_deque = [None] * new_size
        d = new_size - self.max_size        for i in range(self.max_size):
            new_deque[(self.front+i+d) % new_size] = self.deque[(self.front+i) % self.max_size]
        self.deque = new_deque
        self.front = (self.front+d) % new_size
        self.max_size = new_size        
    # 注意队头和队尾修改索引的添加元素的不同顺序
    def addrear(self, data):
        if self.isfull():
            self.resize()
        self.deque[self.rear] = data
        self.rear = (self.rear+1) % self.max_size    def addfront(self, data):
        if self.isfull():
            self.resize()
        self.front = (self.front - 1 + self.max_size) % self.max_size
        self.deque[self.front] = data

Sama seperti baris gilir berjujukan dinamik, kita juga perlu mempertimbangkan indeks selepas menyalin, jika tidak, mungkin terdapat ruang kosong yang tidak boleh digunakan:

Kerumitan masa untuk menambah elemen ialah $O(1)$. Walaupun apabila baris gilir dua hujung berjujukan dinamik penuh, elemen dalam baris gilir dua hujung yang asal perlu disalin ke baris gilir dua hujung baharu dahulu, dan kemudian elemen baharu ditambah Walau bagaimanapun, rujuk kepada pengenalan jujukan operasi tambah jadual dalam "Jadual Jujukan dan Pelaksanaan Operasinya", Sejak jumlah masa n tambah operasi elemen$T(n)$ dan $O(n)$ adalah berkadar dengan (1) . 2.1.6 Padamkan elemen di kepala atau ekor baris gilir Jika baris gilir dua hujung tidak kosong, padam dan kembalikan elemen akhir yang ditentukan:

2.2 Pelaksanaan baris gilir dua hujung berantai

Satu lagi perwakilan storan baris gilir dua hujung ialah menggunakan struktur storan berantai, jadi ia juga sering dipanggil baris gilir dua hujung berantai, di mana operasi

dan operasi

    # 注意队头和队尾修改索引的删除元素的不同顺序
    def removefront(self):
        if not self.isempty():
            result = self.deque[self.front]
            self.front = (self.front+1) % self.max_size            return result        else:
            raise IndexError("Empty Deque Exception")
    
    def removerear(self):
        if not self.isempty():
            self.rear = (self.rear - 1 + self.max_size) % self.max_size
            result = self.deque[self.rear]
            return result        else:
            raise IndexError("Empty Deque Exception")

dilaksanakan dengan memasukkan elemen di kepala dan ekor senarai terpaut masing-masing, manakala operasi

dan operasi dilaksanakan oleh memadamkan nod dari kepala dan ekor masing-masing. Untuk mengurangkan kerumitan masa pemadaman nod di bahagian ekor, baris gilir dua hujung dilaksanakan berdasarkan senarai pautan dua kali.

addfrontaddrear2.2.1 Nod baris gilir dua hujungremovefrontremoverearPelaksanaan nod baris gilir dua hujung tidak berbeza daripada senarai terpaut dua kali:

2.2.2 Permulaan baris gilir dua hujung

Dalam fungsi permulaan baris gilir dua hujung, jadikan penuding kepala

dan penuding ekor

kedua-duanya menghala ke

, dan mulakan baris gilir dua hujung Panjang:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)

2.2.3 Cari panjang baris gilir dua hujung

frontNilai yang dikembalikan oleh rear digunakan untuk mencari panjang daripada baris gilir dua hujung. Jika tiada atribut None, ia diperlukan Panjang baris gilir dua hujung boleh diperolehi dengan merentasi keseluruhan senarai terpaut:

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.num = 0

2.2.4 Menentukan sama ada baris gilir dua hujung kosong

Mengikut panjang baris gilir dua hujung, ia boleh dinilai dengan mudah sama ada baris gilir dua hujung kosong: numnum

2.2 .5 Menambah elemen

    def size(self):
        return self.num

Apabila menambah elemen pada baris gilir dua hujung, anda boleh memasukkan elemen baharu di hujung atau kepala baris gilir, jadi anda perlu mengubah suai

dan

penunjuk, dan juga ubah suai

dan

    def isempty(self):
        return self.num  penunjuk nod; jika baris gilir dua hujung kosong sebelum menambah elemen, pemprosesan yang sepadan perlu dilakukan: <h4>
<pre class="brush:php;toolbar:false">    def addrear(self, data):
        node = Node(data)
        # 如果添加元素前Struktur data Python dan pembelajaran algoritma baris gilir dua hujung为空，则添加结点时，需要将front指针也指向该结点
        if self.front is None:
            self.rear = node
            self.front = node        else:
            node.previous = self.rear
            self.rear.next = node
            self.rear = node
        self.num += 1
    
    def addfront(self, data):
        node = Node(data)
        # 如果添加元素前Struktur data Python dan pembelajaran algoritma baris gilir dua hujung为空，则添加结点时，需要将rear指针也指向该结点
        if self.rear is None:
            self.front = node
            self.rear = node        else:
            node.next = self.front
            self.front.previous = node
            self.front = node
        self.num += 1

2.2.6 删除元素

若Struktur data Python dan pembelajaran algoritma baris gilir dua hujung不空，可以从删除队头或队尾元素并返回，删除操作需要更新队头指针 front 以及尾指针 rear，同时也要修改结点的 next 和 previous 指针，若出队元素尾队中最后一个结点，还需要进行相应处理：

    def removefront(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.front.data
        self.front = self.front.next
        self.num -= 1
        if self.isempty():
            self.rear = self.front        else:
            # 若删除操作完成后，Struktur data Python dan pembelajaran algoritma baris gilir dua hujung不为空，将 front 指针的前驱指针指向 None
            self.front.previous = None
        return result    
    def removerear(self):
        if self.isempty():
            raise IndexError("Empty Queue Exception")
        result = self.rear.data
        self.rear = self.rear.previous
        self.num -= 1
        if self.isempty():
            self.front = self.rear        else:
            # 若删除操作完成后，Struktur data Python dan pembelajaran algoritma baris gilir dua hujung不为空，将 rear 指针的后继指针指向 None
            self.rear.next = None
        return result

2.3 Struktur data Python dan pembelajaran algoritma baris gilir dua hujung的不同实现对比

Struktur data Python dan pembelajaran algoritma baris gilir dua hujung的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。

3. Struktur data Python dan pembelajaran algoritma baris gilir dua hujung应用

接下来，我们首先测试上述实现的Struktur data Python dan pembelajaran algoritma baris gilir dua hujung，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。

3.1 顺序Struktur data Python dan pembelajaran algoritma baris gilir dua hujung的应用

首先初始化一个顺序Struktur data Python dan pembelajaran algoritma baris gilir dua hujung deque，然后测试相关操作：

# 初始化一个最大长度为5的Struktur data Python dan pembelajaran algoritma baris gilir dua hujungdq = Deque(5)print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung空?', dq.isempty())for i in range(3):
    print('队头添加元素：', 2*i)
    dq.addfront(2*i)
    print('队尾添加元素：', 2*i+1)
    dq.addrear(2*i+1)print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为：', dq.size())for i in range(3):
    print('队尾删除元素：', dq.removerear())
    print('队头删除元素：', dq.removefront())print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为：', dq.size())

测试程序输出结果如下：

Struktur data Python dan pembelajaran algoritma baris gilir dua hujung空? True队头添加元素： 0队尾添加元素： 1队头添加元素： 2队尾添加元素： 3队头添加元素： 4队尾添加元素： 5Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为： 0

3.2 链Struktur data Python dan pembelajaran algoritma baris gilir dua hujung的应用

首先初始化一个链Struktur data Python dan pembelajaran algoritma baris gilir dua hujung queue，然后测试相关操作：

# 初始化新队列dq = Deque()print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung空?', dq.isempty())for i in range(3):
    print('队头添加元素：', i)
    dq.addfront(2*i)
    print('队尾添加元素：', i+3)
    dq.addrear(2*i+1)print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为：', dq.size())for i in range(3):
    print('队尾删除元素：', dq.removerear())
    print('队头删除元素：', dq.removefront())print('Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为：', dq.size())

测试程序输出结果如下：

Struktur data Python dan pembelajaran algoritma baris gilir dua hujung空? True队头添加元素： 0队尾添加元素： 3队头添加元素： 1队尾添加元素： 4队头添加元素： 2队尾添加元素： 5Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0Struktur data Python dan pembelajaran algoritma baris gilir dua hujung长度为： 0

3.3 利用Struktur data Python dan pembelajaran algoritma baris gilir dua hujung基本操作实现复杂算法

[1] 给定一字符串 string (如：abamaba)，检查其是否为回文。

使用Struktur data Python dan pembelajaran algoritma baris gilir dua hujung可以快速检查一字符串是否为回文序列，只需要将字符串中字符依次入队，然后从Struktur data Python dan pembelajaran algoritma baris gilir dua hujung两端依次弹出元素，对比它们是否相等：

def ispalindrome(string):
    deque = Deque()
    for ch in string:
        deque.addfront(ch)
    flag = True
    while deque.size() > 1 and flag:
        ch1 = deque.removefront()
        ch2 = deque.removerear()
        if ch1 != ch2:
            flag = False
    return flag

验证算法有效性：

print('abcba是否为回文序列：', ispalindrome('abcba'))print('charaahc是否为回文序列：', ispalindrome('charaahc'))

结果输出如下：

abcba是否为回文序列： True
charaahc是否为回文序列： False

推荐学习：python教程

Atas ialah kandungan terperinci Struktur data Python dan pembelajaran algoritma baris gilir dua hujung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!