مفهوم اندازه و ظرفیت (Size, Capacity) در آرایه
یکی از پایه ای ترین ساختار داده آرایه ها هستند. در آرایه ها ما بصورت ترتیبی مقادیر را قرار می دهیم.
برای تعریف یک آرایه ما باید در قدم اول ظرفیت آرایه رو مشخص کنیم برای مثال ظرفیتش اگه 4 تا باشه فقط می تونیم 4 تا عنصر رو داخلش قرار بدیم.
همچنین لیست های پایتون، یک Array List هستند که در پشت صحنه همان آرایه ها هستند. پس سوالی که مطرح میشود این است که در لیست ها ما چجوری میتونیم هر چقدر که دوست داریم عنصر قرار بدیم و در تعریف کردن سایز رو هم مشخص نمیکنیم؟
در پشت صحنه اتفاقی که میوفتد دقیقا یک آرایه تعریف میشود با ظرفیت مشخص و وقتی که آرایه پر شد و ظرفیت خالی نداشت، یک آرایه بزرگ تر ساخته می شود و عناصر داخل آرایه جدید کپی میشود.
در عکس کاملا مشخص است چگونه این اتفاق میوفتد.
#note #data_structures
@Syntax_fa
یکی از پایه ای ترین ساختار داده آرایه ها هستند. در آرایه ها ما بصورت ترتیبی مقادیر را قرار می دهیم.
برای تعریف یک آرایه ما باید در قدم اول ظرفیت آرایه رو مشخص کنیم برای مثال ظرفیتش اگه 4 تا باشه فقط می تونیم 4 تا عنصر رو داخلش قرار بدیم.
همچنین لیست های پایتون، یک Array List هستند که در پشت صحنه همان آرایه ها هستند. پس سوالی که مطرح میشود این است که در لیست ها ما چجوری میتونیم هر چقدر که دوست داریم عنصر قرار بدیم و در تعریف کردن سایز رو هم مشخص نمیکنیم؟
در پشت صحنه اتفاقی که میوفتد دقیقا یک آرایه تعریف میشود با ظرفیت مشخص و وقتی که آرایه پر شد و ظرفیت خالی نداشت، یک آرایه بزرگ تر ساخته می شود و عناصر داخل آرایه جدید کپی میشود.
در عکس کاملا مشخص است چگونه این اتفاق میوفتد.
#note #data_structures
@Syntax_fa
👍8
ساختمان داده Deque (Double-Ended Queue)
Deque،
مخفف "Double-Ended Queue"، یک نوع ساختمان داده است که به‌صورت همزمان امکان اضافه و حذف عناصر را از هر دو انتها (ابتدا و انتها) فراهم می‌کند. این ویژگی Deque را به یک ابزار قدرتمند در بسیاری از الگوریتم‌ها و برنامه‌های کاربردی تبدیل کرده است.
ویژگی‌های Deque
1. دسترسی دو طرفه: امکان اضافه و حذف عناصر از (ابتدا و انتها) را فراهم می‌کند.
2. انعطاف‌پذیری: ترکیبی از ویژگی‌های پشته (stack) و صف (queue) را داراست.
3. پیچیدگی زمانی بهینه: عملیات افزودن و حذف در هر دو انتها دارای زمان اجرای O(1) است(اگر به لیست های پیوندی پیاده شود)
عملیات‌های اصلی در Deque:
1. افزودن به ابتدا (Add to Front):
- عملیات:
- توضیح: این عملیات یک عنصر را به ابتدای Deque اضافه می‌کند.
2. افزودن به انتها (Add to Rear):
- عملیات:
- توضیح: این عملیات یک عنصر را به انتهای Deque اضافه می‌کند.
3. حذف از ابتدا (Remove from Front):
- عملیات:
- توضیح: این عملیات اولین عنصر را از Deque حذف می‌کند.
4. حذف از انتها (Remove from Rear):
- عملیات:
- توضیح: این عملیات آخرین عنصر را از Deque حذف می‌کند.
5. دسترسی به اولین عنصر (Peek at Front):
- عملیات:
- توضیح: این عملیات اولین عنصر را بدون حذف از Deque برمی‌گرداند.
6. دسترسی به آخرین عنصر (Peek at Rear):
- عملیات:
- توضیح: این عملیات آخرین عنصر را بدون حذف از Deque برمی‌گرداند.
7. بررسی خالی بودن (Check if Empty):
- عملیات:
- توضیح: این عملیات بررسی می‌کند که آیا Deque خالی است یا خیر.
8. بررسی اندازه (Check Size):
- عملیات:
- توضیح: این عملیات تعداد عناصر موجود در Deque را برمی‌گرداند.
پیاده‌سازی Deque
برای پیاده‌سازی Deque، چندین ساختار داده وجود دارند که می‌توانند به کار گرفته شوند، اما دو ساختار داده‌ای که معمولاً برای پیاده‌سازی Deque مناسب هستند عبارتند از:
1. لیست پیوندی دوطرفه (Doubly Linked List):
- توضیح: لیست پیوندی دوطرفه دارای گره‌هایی است که هر گره شامل دو اشاره‌گر است: یکی به گره قبلی و دیگری به گره بعدی.
این ساختار داده امکان افزودن و حذف عناصر از هر دو انتها را با پیچیدگی زمانی O(1) فراهم می‌کند.
- مزایا:
- زمان اجرای بهینه برای عملیات افزودن و حذف.
- انعطاف‌پذیری بالا.
- معایب:
- سربار حافظه به دلیل استفاده از اشاره‌گرها.
2. آرایه دایره‌ای (Circular Array):
- توضیح: آرایه دایره‌ای یک آرایه ثابت است که انتهای آن به ابتدای آرایه پیوند داده شده است. این ساختار داده نیز امکان افزودن و حذف عناصر از هر دو انتها را با پیچیدگی زمانی O(1) فراهم می‌کند.
- مزایا:
- استفاده کارآمد از حافظه.
- دسترسی سریع به عناصر.
- معایب:
- اندازه ثابت آرایه می‌تواند منجر به مشکلاتی در صورت نیاز به فضای بیشتر یا کمتر شود.
- نیاز به مدیریت دقیق اندیس‌ها برای جلوگیری از سرریز (overflow) یا سربار (underflow).
تمرین:
مثال Deque رو تو زبانی که کار میکنید پیاده سازیش کنید و توی کامنت ارسال کنید.
#deque #data_structures
@Syntax_fa
Deque،
مخفف "Double-Ended Queue"، یک نوع ساختمان داده است که به‌صورت همزمان امکان اضافه و حذف عناصر را از هر دو انتها (ابتدا و انتها) فراهم می‌کند. این ویژگی Deque را به یک ابزار قدرتمند در بسیاری از الگوریتم‌ها و برنامه‌های کاربردی تبدیل کرده است.
ویژگی‌های Deque
1. دسترسی دو طرفه: امکان اضافه و حذف عناصر از (ابتدا و انتها) را فراهم می‌کند.
2. انعطاف‌پذیری: ترکیبی از ویژگی‌های پشته (stack) و صف (queue) را داراست.
3. پیچیدگی زمانی بهینه: عملیات افزودن و حذف در هر دو انتها دارای زمان اجرای O(1) است(اگر به لیست های پیوندی پیاده شود)
عملیات‌های اصلی در Deque:
1. افزودن به ابتدا (Add to Front):
- عملیات:
addFirst(element)- توضیح: این عملیات یک عنصر را به ابتدای Deque اضافه می‌کند.
2. افزودن به انتها (Add to Rear):
- عملیات:
addLast(element)- توضیح: این عملیات یک عنصر را به انتهای Deque اضافه می‌کند.
3. حذف از ابتدا (Remove from Front):
- عملیات:
removeFirst()- توضیح: این عملیات اولین عنصر را از Deque حذف می‌کند.
4. حذف از انتها (Remove from Rear):
- عملیات:
removeLast()- توضیح: این عملیات آخرین عنصر را از Deque حذف می‌کند.
5. دسترسی به اولین عنصر (Peek at Front):
- عملیات:
peekFirst()- توضیح: این عملیات اولین عنصر را بدون حذف از Deque برمی‌گرداند.
6. دسترسی به آخرین عنصر (Peek at Rear):
- عملیات:
peekLast()- توضیح: این عملیات آخرین عنصر را بدون حذف از Deque برمی‌گرداند.
7. بررسی خالی بودن (Check if Empty):
- عملیات:
isEmpty()- توضیح: این عملیات بررسی می‌کند که آیا Deque خالی است یا خیر.
8. بررسی اندازه (Check Size):
- عملیات:
size()- توضیح: این عملیات تعداد عناصر موجود در Deque را برمی‌گرداند.
پیاده‌سازی Deque
برای پیاده‌سازی Deque، چندین ساختار داده وجود دارند که می‌توانند به کار گرفته شوند، اما دو ساختار داده‌ای که معمولاً برای پیاده‌سازی Deque مناسب هستند عبارتند از:
1. لیست پیوندی دوطرفه (Doubly Linked List):
- توضیح: لیست پیوندی دوطرفه دارای گره‌هایی است که هر گره شامل دو اشاره‌گر است: یکی به گره قبلی و دیگری به گره بعدی.
این ساختار داده امکان افزودن و حذف عناصر از هر دو انتها را با پیچیدگی زمانی O(1) فراهم می‌کند.
- مزایا:
- زمان اجرای بهینه برای عملیات افزودن و حذف.
- انعطاف‌پذیری بالا.
- معایب:
- سربار حافظه به دلیل استفاده از اشاره‌گرها.
2. آرایه دایره‌ای (Circular Array):
- توضیح: آرایه دایره‌ای یک آرایه ثابت است که انتهای آن به ابتدای آرایه پیوند داده شده است. این ساختار داده نیز امکان افزودن و حذف عناصر از هر دو انتها را با پیچیدگی زمانی O(1) فراهم می‌کند.
- مزایا:
- استفاده کارآمد از حافظه.
- دسترسی سریع به عناصر.
- معایب:
- اندازه ثابت آرایه می‌تواند منجر به مشکلاتی در صورت نیاز به فضای بیشتر یا کمتر شود.
- نیاز به مدیریت دقیق اندیس‌ها برای جلوگیری از سرریز (overflow) یا سربار (underflow).
تمرین:
مثال Deque رو تو زبانی که کار میکنید پیاده سازیش کنید و توی کامنت ارسال کنید.
#deque #data_structures
@Syntax_fa
👍7