Deque ใน Python

Deque นั้นเป็นลักษณะทั่วไปของโครงสร้างสแต็กและคิว โดยเริ่มต้นจากซ้ายไปขวา มันใช้อ็อบเจกต์รายการเพื่อสร้าง deque ซึ่งให้ความซับซ้อนของเวลา O(1) สำหรับการแตกและต่อท้าย

Deque เป็นคลาสไลบรารีมาตรฐานซึ่งอยู่ใน collections โมดูล

หากต้องการใช้งานในตอนแรก เราต้องนำเข้าโมดูลไลบรารีมาตรฐานของคอลเลกชัน

import collections

ในส่วนนี้เราจะเห็นฟังก์ชันบางอย่างของคลาส Deque

ฟังก์ชันผนวกเข้ากับ Deque

การผนวกมีสองประเภทที่แตกต่างกัน วิธีการ append() ใช้สำหรับเพิ่มองค์ประกอบที่ด้านขวาสุดของคิว และวิธีการ appendleft() ใช้เพื่อผนวกองค์ประกอบทางด้านซ้ายของคิว

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('124dfre')
   print('Dequeue: ' + str(my_deque))
      #insert x at right and B at left
      my_deque.append('x')
      my_deque.appendleft('B')
   print('Dequeue after appending: ' + str(my_deque))

ผลลัพธ์

Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Dequeue after appending: deque(['B', '1', '2', '4', 'd', 'f', 'r', 'e', 'x'])

ฟังก์ชัน Popping ใน Deque

เช่นเดียวกับการผนวก ฟังก์ชันป๊อปมีสองประเภทที่แตกต่างกัน เมธอด pop() ใช้เพื่อลบและส่งคืนองค์ประกอบที่ถูกต้องที่สุดจากคิว และวิธีการ popleft() ใช้เพื่อลบและส่งคืนองค์ประกอบที่เหลือส่วนใหญ่จากคิว

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('124dfre')
   print('Dequeue: ' + str(my_deque))
      #delete item from right and left
      item = my_deque.pop()
   print('Popped Item: ' + str(item))
      item = my_deque.popleft()
   print('Popped Item: ' + str(item))
print('Dequeue after pop operations: ' + str(my_deque))

ผลลัพธ์

Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e'])
Popped Item: e
Popped Item: 1
Dequeue after pop operations: deque(['2', '4', 'd', 'f', 'r'])

ฟังก์ชั่นที่เกี่ยวข้องกับไอเท็มใน Deque

ฟังก์ชันบางอย่างใน Deque ใช้เพื่อรับข้อมูลที่เกี่ยวข้องกับรายการ มีฟังก์ชันบางอย่างเช่น index(), count() เป็นต้น เมธอด index ถูกใช้เพื่อรับดัชนีขององค์ประกอบที่เกิดขึ้นครั้งแรก เมื่อไม่มีการส่งอาร์กิวเมนต์กับองค์ประกอบ มันจะเลือกรายการทั้งหมด เมื่อมีการระบุขีดจำกัด มันจะตรวจสอบดัชนีในขีดจำกัดนั้น ในทางกลับกัน วิธี count() จะนับความถี่ของรายการใน Deque

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
   print('Dequeue: ' + str(my_deque))
      #find the index of D
   print('Index of D:' + str(my_deque.index('D')))
print('Index of D in range 5 to 8 is: ' + str(my_deque.index('D', 5, 8)))
#Count the number of occurrences
   print('Occurrences of A: ' + str(my_deque.count('A')))
print('Occurrences of D: ' + str(my_deque.count('D')))

ผลลัพธ์

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Index of D:4
Index of D in range 5 to 8 is: 5
Occurrences of A: 2
Occurrences of D: 3

ฟังก์ชัน insert() และ remove() ใน Deque

เราได้เห็นฟังก์ชันผนวกและป๊อปใน Deque สำหรับการแทรกและลบองค์ประกอบตามลำดับแล้ว มีอีกสองวิธีที่เกี่ยวข้องกับการแทรกและการลบ วิธีการ insert() ใช้สำหรับใส่ตัวเลข ในกรณีนี้ เราสามารถจัดเตรียมดัชนีสำหรับการแทรก ดังนั้นในตำแหน่งที่ระบุจึงสามารถแทรกรายการได้ และใช้เมธอด remove() เพื่อลบการเกิดขึ้นครั้งแรกขององค์ประกอบ

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Insert letter G and H into the position 5, 7 respectively
my_deque.insert(5, 'G')
my_deque.insert(7, 'H')
print('Dequeue after inserting: ' + str(my_deque))
#Delete first occurrence of letter D
my_deque.remove('D')
print('Dequeue after removing: ' + str(my_deque))

ผลลัพธ์

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Dequeue after inserting: deque(['A', 'A', 'B', 'C', 'D', 'G', 'D', 'H', 'E', 'F', 'D'])
Dequeue after removing: deque(['A', 'A', 'B', 'C', 'G', 'D', 'H', 'E', 'F', 'D'])

ขยายฟังก์ชันใน Deque

ฟังก์ชันขยายใช้เพื่อเพิ่มองค์ประกอบหลายรายการลงใน Deque เราสามารถใช้คอลเล็กชัน เช่น รายการ ทูเพิล เพื่อระบุค่าต่างๆ ได้หลายค่า ฟังก์ชั่นการขยายมีสองประเภท วิธี expand() ใช้สำหรับเพิ่มองค์ประกอบทางด้านขวา ซึ่งคล้ายกับฟังก์ชัน append() ซ้ำๆ และใช้เมธอด expandleft() เพื่อเพิ่มองค์ประกอบทางด้านซ้าย ซึ่งคล้ายกับฟังก์ชัน appendleft() ซ้ำๆ

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Extend by adding 1, 3, 5, 7 to the right and x, y, z to the left
my_deque.extend([1, 3, 5, 7])
my_deque.extendleft(['x', 'y', 'z'])
print('Dequeue after Extending: ' + str(my_deque))

ผลลัพธ์

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Dequeue after Extending: deque(['z', 'y', 'x', 'A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D', 1, 3, 5, 7])

ฟังก์ชันย้อนกลับและหมุนใน Deque

เราสามารถย้อนกลับลำดับของ dequeuer โดยใช้วิธี reverse() มีวิธีการอื่นที่เรียกว่าการหมุน () ใช้วิธีการหมุน deque สามารถหมุนด้วยตัวเลขที่ระบุเป็นอาร์กิวเมนต์ หากอาร์กิวเมนต์เป็นค่าบวก อาร์กิวเมนต์จะหมุนไปทางขวา และสำหรับจำนวนลบจะหมุนซ้าย

โค้ดตัวอย่าง

import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
my_deque.reverse()
print('Deque after Reversing:' + str(my_deque))
#rotate to the right, 3 elements
my_deque.rotate(3)
print('Deque after rotating:' + str(my_deque))

ผลลัพธ์

Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D'])
Deque after Reversing:deque(['D', 'F', 'E', 'D', 'D', 'C', 'B', 'A', 'A'])
Deque after rotating:deque(['B', 'A', 'A', 'D', 'F', 'E', 'D', 'D', 'C'])