Timbunan dan Baris Gilir || Python || Struktur Data dan Algoritma

timbunan

Timbunan - Ia ialah bekas storan yang menyokong pengambilan melalui pesanan masuk terakhir, keluar dahulu ( LIFO). Tindanan mungkin merupakan bekas yang sesuai untuk digunakan apabila pesanan pengambilan tidak penting sama sekali, seperti semasa memproses kerja kelompok.

Contohnya, pertimbangkan timbunan pinggan yang digunakan di kafetaria: susunan pinggan dikeluarkan daripada timbunan adalah kebalikan susunan piring itu ditambahkan, kerana hanya pinggan atas sahaja boleh diakses .

Operasi INSERT pada tindanan sering dipanggil PUSH dan operasi DELETE, yang tidak mengambil hujah elemen, sering dipanggil POP.

Tolak (x,s): Masukkan item x di bahagian atas tindanan s.

Pop : Kembalikan (dan keluarkan) item teratas tindanan s.

Makanan yang dimasukkan ke dalam peti sejuk saya biasanya keluar dengan cara yang sama, walaupun terdapat insentif tarikh luput. Secara algoritma, LIFO cenderung berlaku semasa melaksanakan algoritma rekursif.

Aplikasi Tindanan -

1. Panggilan fungsi: Digunakan untuk mengurus pelaksanaan fungsi dan rekursi.
2. Buat asal operasi: Menjejaki perubahan dalam editor untuk "Buat asal/Buat Semula."
3. Sejarah penyemak imbas: Simpan halaman yang dilawati untuk menjejak ke belakang.
4. Penghuraian ungkapan: Menilai dan menukar ungkapan matematik.
5. Pengesahan sintaks: Memadankan kurungan atau teg dalam kod.
6. Pengurusan memori: Mengurus tindanan panggilan semasa pelaksanaan program.
7. DFS: Melaksanakan Carian Pertama Kedalaman dalam algoritma graf.

Laksanakan Tindanan Menggunakan Tatasusunan -

• push() - Masukkan elemen ke dalam tindanan
• pop() - Keluarkan elemen daripada timbunan
• top() - Mengembalikan elemen atas tindanan.
• isEmpty() - Mengembalikan benar jika tindanan kosong dan palsu.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

Beratur

Baris gilir - Ia ialah bekas storan yang menyokong pengambilan semula dengan perintah masuk dahulu, keluar dahulu (FIFO). Kami memanggil operasi INSERT pada baris gilir ENQUEUE, dan kami memanggil operasi DELETE DEQUEUE. Seperti POP operasi tindanan, DEQUEUE tidak mengambil hujah elemen. Tindanan dan baris gilir ialah set dinamik yang mana elemen dialih keluar daripada set oleh operasi DELETE dipratakrifkan.

Enqueue(x,q): Sisipkan item x di belakang baris gilir q.

Dequeue(q): Kembalikan (dan alih keluar) item hadapan daripada baris q.

Barisan mempunyai kepala dan ekor.

• Apabila elemen dimasukkan ke dalam baris gilir, ia mengambil tempat di bahagian belakang baris gilir, sama seperti pelanggan yang baru tiba mengambil tempat di hujung baris.

• Elemen yang dibatalkan sentiasa berada di kepala barisan, seperti pelanggan di kepala barisan, yang telah menunggu paling lama.

Aplikasi Baris Gilir -

1. Penjadualan tugas: Mengurus proses dan kerja CPU dengan teratur.
2. BFS: Melaksanakan Breadth-First Search dalam graf.
3. Cetak baris gilir: Mengendalikan kerja cetakan secara berurutan.
4. Penghalaan rangkaian: Menampan paket data untuk penghantaran.
5. Pusat panggilan: Mengurus panggilan pelanggan mengikut urutan menunggu.
6. Penstriman: Menampan strim video atau audio dalam masa nyata.
7. Acara input: Memproses input papan kekunci dan tetikus dalam sistem GUI.

Laksanakan Baris Menggunakan Tatasusunan-

• enqueue() – Sisipan elemen pada baris gilir.
• dequeue() – Mengalih keluar elemen daripada baris gilir.
• peek() atau front()- Memperoleh elemen data yang tersedia di nod hadapan baris gilir tanpa memadamkannya.
• isEmpty() – Menyemak sama ada baris gilir kosong.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

Laksanakan Baris Gilir menggunakan Tindanan -

• push(x) - Alihkan semua elemen dari tindanan1 ke tindanan 2 untuk membalikkan susunannya dan kemudian dan sekali lagi gerakkan semula semua elemen dari tindanan2 ke tindanan 1.
• pop() - Mengalih keluar elemen dari hadapan baris gilir dan mengembalikannya
• peek() - Mengembalikan elemen di hadapan baris gilir
• kosong() - Mengembalikan benar jika baris gilir kosong, palsu sebaliknya

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

Laksanakan Tindanan menggunakan Baris Gilir -

• tekan(x) - Tambahkan elemen baharu pada baris gilir kedua, kemudian alihkan semua elemen daripada baris gilir 1 ke baris gilir 2 untuk mengekalkan susunan tindanan (LIFO) dan Tukar baris gilir.
• pop() - Mengalih keluar elemen di bahagian atas tindanan dan mengembalikannya
• peek atau top() - Mengembalikan elemen di hadapan baris gilir
• kosong() - Mengembalikan benar jika baris gilir kosong, palsu sebaliknya

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

Atas ialah kandungan terperinci Timbunan dan Baris Gilir || Python || Struktur Data dan Algoritma. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!