صف دوطرفه

در علوم کامپیوتر یک صف دوطرفه (Double ended queue یا dequeue) نوعی نوع داده انتزاعی است که یک صف را تعمیم می‌بخشد به طوری که بتوان هم از ابتدای صف و هم از انتهای صف حذف یا اضافه کرد و دسترسی داشت.

ویژگی‌ها

این ساختمان داده هم مانند صف از عملکرد بر اساس سیاست FIFO (خروج به ترتیب ورود) و هم مانند پشته از عملکرد بر اساس سیاست LIFO (خروج به ترتیب عکس ورود) پشتیبانی می‌کند. به همین دلیل می‌توان گفت پشته و صف خاص شده‌های صف دوطرفه هستند و می‌توان هر دو را با استفاده از صف دو طرفه پیاده‌سازی کرد.

توابع

حذف و اضافه در صف دوطرفه

در صف دو طرفه دو عمل اصلی صف و پشته (حذف و اضافه) تبدیل به چهار عمل اصلی به صورت اضافه کردن به ابتدا، اضافه کردن به انتها، حذف از ابتدا، حذف از انتها می‌شوند. همچنین معمولاً از توابعی برای دسترسی به عنصر اول و آخر صف استفاده می‌شود.

نام این عملیات در زبان‌های مختلف متفاوت است. می‌توانید تعدادی از نام توابع صف را در زبان‌های برنامه‌نویسی در جدول زیر مشاهده کنید.

توابع	نام مشهور	Ada	C++	Java	Perl	PHP	Python	Ruby	JavaScript
اضافه کردن عنصر به انتهای آرایه	inject, snoc	Append	push_back	offerLast	push	array_push	append	push	push
اضافه کردن عنصر به اول آرایه	push, cons	Prepend	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	unshift
حذف عنصر انتها	eject	Delete_Last	pop_back	pollLast	pop	array_pop	pop	pop	pop
حذف عنصر ابتدا	pop	Delete_First	pop_front	pollFirst	shift	array_shift	popleft	shift	shift
برگرداندن عنصر انتها		Last_Element	back	peekLast	$array[-1]	end	<obj>[-1]	last	<obj>[<obj>.length - 1]
برگرداندن عنصر ابتدا		First_Element	front	peekFirst	$array[0]	reset	<obj>[0]	first	<obj>[0]

پیاده‌سازی

معمولاً صف دوطرفه را با استفاده از آرایه پویا یا فهرست پیوندی دوطرفه پیاده‌سازی می‌کنند.

به طور مثال پیاده‌سازی ای از صف دوطرفه با استفاده از آرایه پویا در زبان برنامه‌نویسی پایتون به صورت زیر است:

class Deque:
    #Constructor
    def __init__(self):
        self.elements = []
    #Insert element at front
    def addFront(self, element):
        self.elements.append(element)
    #Insert element at back
    def addBack(self, element):
        self.elements.insert(0,element)
    #Remove first element
    def removeFront(self):
        self.elements.pop()
    #Remove last element
    def removeBack(self):
        self.elements.pop(0)
    #Return first element
    def first(self):
        return self.elements[0]
    #Return last element
    def last(self):
        return self.elements[len(self.elements)-1]
    #Return current size of deque
    def size(self):
        return len(self.elements)

پیچیدگی

در صورت پیاده‌سازی با آرایه پویا یا فهرست پیوندی دوطرفه تمام عملیات از $O(1)$ می‌باشد.

منابع

ویکی‌پدیا انگلیسی