در علوم کامپیوتر یک صف دوطرفه ( Double ended queue یا dequeue ) نوعی نوع داده انتزاعی است که یک صف را تعمیم می بخشد به طوری که بتوان هم از ابتدای صف و هم از انتهای صف حذف یا اضافه کرد و دسترسی داشت.
این ساختمان داده هم مانند صف از عملکرد بر اساس سیاست FIFO ( خروج به ترتیب ورود ) و هم مانند پشته از عملکرد بر اساس سیاست LIFO ( خروج به ترتیب عکس ورود ) پشتیبانی می کند. به همین دلیل می توان گفت پشته و صف خاص شده های صف دوطرفه هستند و می توان هر دو را با استفاده از صف دو طرفه پیاده سازی کرد.
در صف دو طرفه دو عمل اصلی صف و پشته ( حذف و اضافه ) تبدیل به چهار عمل اصلی به صورت اضافه کردن به ابتدا، اضافه کردن به انتها، حذف از ابتدا، حذف از انتها می شوند. همچنین معمولاً از توابعی برای دسترسی به عنصر اول و آخر صف استفاده می شود.
نام این عملیات در زبان های مختلف متفاوت است. می توانید تعدادی از نام توابع صف را در زبان های برنامه نویسی در جدول زیر مشاهده کنید.
معمولاً صف دوطرفه را با استفاده از آرایه پویا یا فهرست پیوندی دوطرفه پیاده سازی می کنند.
به طور مثال پیاده سازی ای از صف دوطرفه با استفاده از آرایه پویا در زبان برنامه نویسی پایتون به صورت زیر است:
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 #Return last element def last ( self ) : return self. elements #Return current size of deque def size ( self ) : return len ( self. elements ) پیچیدگی در صورت پیاده سازی با آرایه پویا یا فهرست پیوندی دوطرفه تمام عملیات از O ( 1 ) می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین ساختمان داده هم مانند صف از عملکرد بر اساس سیاست FIFO ( خروج به ترتیب ورود ) و هم مانند پشته از عملکرد بر اساس سیاست LIFO ( خروج به ترتیب عکس ورود ) پشتیبانی می کند. به همین دلیل می توان گفت پشته و صف خاص شده های صف دوطرفه هستند و می توان هر دو را با استفاده از صف دو طرفه پیاده سازی کرد.
در صف دو طرفه دو عمل اصلی صف و پشته ( حذف و اضافه ) تبدیل به چهار عمل اصلی به صورت اضافه کردن به ابتدا، اضافه کردن به انتها، حذف از ابتدا، حذف از انتها می شوند. همچنین معمولاً از توابعی برای دسترسی به عنصر اول و آخر صف استفاده می شود.
نام این عملیات در زبان های مختلف متفاوت است. می توانید تعدادی از نام توابع صف را در زبان های برنامه نویسی در جدول زیر مشاهده کنید.
معمولاً صف دوطرفه را با استفاده از آرایه پویا یا فهرست پیوندی دوطرفه پیاده سازی می کنند.
به طور مثال پیاده سازی ای از صف دوطرفه با استفاده از آرایه پویا در زبان برنامه نویسی پایتون به صورت زیر است:
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 #Return last element def last ( self ) : return self. elements #Return current size of deque def size ( self ) : return len ( self. elements ) پیچیدگی در صورت پیاده سازی با آرایه پویا یا فهرست پیوندی دوطرفه تمام عملیات از O ( 1 ) می باشد.
wiki: صف دوطرفه