مقاله در مورد پیاده سازی پشته

بخشی از مقاله

پیاده سازی پشته

بخشهای مختلف پروتکل پشته TCP/IP (Protocol Stack)
لایه دسترسی شبکه عملیات لایه فیزیکی و لایه پیوند داده مدل OSI را با هم تلفیق می کند . این لایه دربرگیرنده رسانه ارتباطی و پروتکل های ارتباطی برای انتقال فریم ها روی آن رسانه است .

پشته TCP/IP شامل چهار لایه است ( از بالا به پایین ) :
ـ لایه دسترسی به شبکه

ـ لایه ارتباطات میزبان به میزبان
ـ لایه سرویس های کاربردی
▪ لایه دسترسی به شبکه

لایه دسترسی شبکه عملیات لایه فیزیکی و لایه پیوند داده مدل OSI را با هم تلفیق می کند . این لایه دربرگیرنده رسانه ارتباطی و پروتکل های ارتباطی برای انتقال فریم ها روی آن رسانه است . لایه دسترسی به شبکه در TCP/IP می تواند پروتکل های استاندارد صنعتی مثل اترنت ۱۰ Base –T را استفاده کند .

ولی در بعضی از پشته ها این دسترسی به روشهای متفاوتی پیاده سازی خواهد شد . پشته NDIS (Network Driver Interface Specification ) که در ویندوز NT و شبکه های LANMAN استفاده شده ، اجازه می دهد که پروتکل های دسترسی به شبکه مختلفی بصورت قابل تعویضی با یک پشته TCP/IP استفاده شوند .
▪ لایه ارتباطات اینترنتی
لایه ارتباطات اینترنتی مسئول ایجاد ارتباط بین میزبانها است ، بدون توجه به لایه دسترسی به شبکه ای که بکار گرفته شده است . این لایه می بایست قادر به ارتباط برقرار کردن بین میزبانهای شبکه محلی و شبکه های گسترده باشد . بنابراین در این لایه باید یک آدرس بندی و پروتکل ارتباطی قابل مسیردهی داشته باشیم . لایه ارتباطات اینترنتی از IP برای آدرس دهی و انتقال داده ها استفاده می کند . بنابراین این لایه ذاتاً غیر اتصالی است و متناظر با لایه شبکه (Netwoek Layer) مدل OSI است . بعلاوه لایه ارتباطات اینترنتی مسئول فراهم آوردن همه

اطلاعات لازم برای لایه دسترسی به شبکه به مـنـظور فرستادن فریمهایش به مقـصـد مـحـلی است ( یا مقـصد میـزبـان دیـگری یا مسیـریـاب) . بـنـابرایـن ، ایـن لایـه بـایـد پروتکل ARP ( Address Resolution Protocol) را هم در بر داشته باشد . پروتکل دیگری به نام RARP ( Reverse Address Resoulation Protocol ) برای آدرس دهی ایستگاههای بدون دیسکت (diskless) نیز وجود دارد که براین لایه تکیه دارد .
بعلاوه این لایه می بایست قادر به مسیریابی داده ها از طریق Internetwork به مقصدهای خود باشد . بنابراین ، این لایه دربرگیرنده پروتکل RIP (Routing Informatio Protocol) نیز می باشد

که می تواند از ابزارهای روی شبکه پرس وجو هایی انجام دهد تا تعیین کند که بسته ها به یک مقصد مشخص چگونه باید مسیریابی شوند .
همچنین لایه ارتباطات اینترنت شامل قابلیتهایی برای میزبانها به منظور تبادل اطلاعات درباره مشکلات یا خطا ها در شبکه می باشد . پروتکلی که این ویژگی را پیاده سازی می کند ، ICMP (Internet Control Message Protocol ) نام دارد و در نهایت ، لایه ارتباطات اینترنتی ویژگی Multicast را دربردارد (ویژگی که کار ارسال اطلاعات به چندین مقصد میزبان را در هر لحظه خواهیم داشت ) .
این فرآیند توسط پروتکل (Internet Group Management Protocol) پشتیبانی می شود.
لایه ارتباطات میزبان به میزبان : لایه ارتباطات میزبان به میزبان سرویسهای مورد نیاز برای ایجاد ارتباطات قابل اعتماد بین میزبانهای شبکه را پیاده سازی می کند و مطابق با لایه حمل و قسمتی از لایه جلسه مدل OSI است و در ضمن در برگیرنده قسمتی از کارهای لایه های نمایش و کاربردی نیز می باشد . لایه میزبان به میزبان شامل دو پروتکل است . اولین آن TCP (Transimission Control Protocol) می باشد . TCP توانائی برقراری سرویس ارتباط گرا بین میزبانها را فراهم می کند . آن شامل ویژگیهای زیر می باشد :
▪ قسمت بندی داده ها به بسته (Packets)
▪ ساخت رشته های داده از بسته ها
▪ دریافت تائید
▪ سرویس های سوکت برای ایجاد چندین ارتباط با چندین پورت روی میزبانهای دور
▪ بازبینی بسته و کنترل خطا
▪ کنترل جریان انتقال داده
▪ مرتب سازی و ترتیب بندی بسته
سرویس های TCP سرویس های ارتباط گرای قابل اعتمادی با قابلیتهای زیبای کشف خطا ها و مشکلات را فراهم می کنند .

پروتکل دوم در لایه میزبان به میزبان ،UDP (User Datagram Protocol) نام دارد . UDP برای فراهم کردن یک مکانیزم کاهش سرزیری شبکه در انتقال داده ها روی لایه های پائین تر طراحی شده است . هـر چند که این لایه هم مدیریت بسته و سرویس های مرتب سازی را ارائه می دهد ولی UDP نیاز به سرویس های قدرتمند ارتباط گرای TCP مثل تائید ، کنترل جریان داده و مرتب سازی مجدد بسته ها برای انجام کارهای خود را دارد . UDP برای کاهش سرریزی پشته در برنامه های طراحی شده که سرویس های ارتباط گرای خود را توسط TCP پیاده سازی می کند . برای پیاده سازی پروتکل های TCP و UDP ، لایه میزبان به میزبان شامل API هایی (Application Programming Interfaces) برای بهره گیری از آنها می باشد .
لایه سرویس های کاربردی : لایه سرویس های کاربردی لایه دیگری است که به راحتی با مدل OSI مطابقت نمی کند . آن شامل قسمتهائی از لایه جلسه ، لایه نمایش و لایه کاربردی و بعلاوه فضای بالای پشته OSI که اصولاً برای فضای برنامه های کاربردی سیستم درنظر گرفته می باشد .

لایه سرویسهای کاربردی شامل پروتکلهای سطح بالایی برای استفاده از پروتکلهای سطح پایین تر مثل TCP و UDP است . این سرویسها از آن پروتکلها برای ایجاد سرویسهای اینترنتی مثل موارد زیر استفاده می کنند :
▪ شبیه سازی پایانه یا (Telnet) Terminal Emulation
▪ انتقال فایل یا (FTP , TFTP) File Transfer
▪ مدیریت پست الکترونیکی یا (SMTP) Mail Management
▪ سرویس های WWW یا (HTTP) World Wide Web
▪ دسترسی به پوسته دور یا (RSH) Remote Shell Access

پشته و صف
ساختارهای خطی داده‌ها
آرایه
صف‌گشایی
توده
لیست پیوندی
صف
پشته
پياده سازي پشته (stack) يكي از سر فصل هاي رايج در درس ساختمان داده ها و غيره مي باشد از اين رو برنامه موجود برنامه انبار داري است كه به زبان پاسكال و سي و سي پلاس پلاس پياده سازي شده است بدين صورت كه شماره سريال - نوع كالا و نام كالا را از ورودي دريافت مي كند .

در كل اين برنامه شامل مراحل زير است :

1 - چاپ پشته به صورت جدول بندي شده به دو رنگ زرد و سفيد براي درك و خوانايي بالاتر
2 - اضافه كردن كالاي جديد (Push)
3 - حذف كردن كالا (Pop)

4-جستجو بر اساس شماره سريال
5 -مرتب سازي پشته به صورت صعودي
6 - نمايش آخرين مقدار پشته (TOP)
7 – خروج

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

FIFO و LIFO چیستند؟
LIFO کوتاه‌شدهٔ عبارت Last In First Out (آخرین ورودی از همه زودتر خارج می‌شود) است. این سیاست اساس کار پشته‌ها را تشکیل می‌دهد و به مفهوم آن است که آخرین دادهٔ ذخیره شده در پشته، نخستین داده‌ای است که بازیابی می‌شود.
FIFO کوتاه‌شدهٔ عبارت First In First Out (اولین ورودی از همه زودتر خارج می‌شود) است. این سیاست اساس کار صف‌ها را تشکیل می‌دهد و به مفهوم آن است که اولین دادهٔ ذخیره شده در صف، نخستین داده‌ای نیز هست که بازیابی می‌شود.
با توجه به آن‌چه گفته شد، روشن است که در سیاست LIFO، ورود و خروج داده‌ها، از یک سمت صورت می‌گیرد (در واقع تنها یک سمت تودهٔ داده‌ها باز است) در حالی که در سیاست FIFO، ورود و خروج داده‌ها، از دو سمت صورت می‌گیرد (یک سمت برای ورودی و یک سمت برای خروجی) و ما به دو سر تودهٔ داده‌ها دست‌رسی خواهیم داشت (یکی برای ورود و دیگری برای خروج).
مثال‌ها


تصوير بالا، یك صف (داده‌های در انتظار پردازش در CPU؛ ورود و خروج داده‌ها در جهت مشخص شده انجام می‌شود و عدد 1 ورودی و عدد 0 خروجی هستند) و تصوير پايين یك پشته (دستهٔ كاغذها روی ميز؛ تنها به كاغذ رويی دست‌رسی داريم) را نشان می‌دهند
• دستهٔ کاغذها روی میز، مثالی خوب از پشته‌است. در این حا

لت ما تنها می‌توانیم بر روی دستهٔ کاغذها، کاغذی بگذاریم و از طرفی تنها می‌توانیم از روی دستهٔ کاغذها، کاغذی برداریم (یعنی ورود و خروج از یک سمت انجام می‌گیرد). روشن است که در این حالت آخرین کاغذی که روی دستهٔ کاغذها قرار داده شده، نخستین کاغذی است که برداشته می‌شود و اولین کاغذی که روی میز گذاشته شده، آخر از همه برداشته خواهد ش
• صف نانوایی، مثالی خوب از صف است. در این حالت، برخلاف پشته، آدم‌ها به ته صف اضافه می‌شوند و از سر صف خارج می‌شوند (یعنی ورود و خروج از دو سمت متمایز انجام می‌گیرد). به این ترتیب روشن است که آخرین کسی که وارد صف شده، آخرین کسی است که نان دریافت می‌کند و اولین کسی که وارد صف شده، نخستین فردی است که نان می‌گیرد.

پیاده‌سازی
پشته‌ها ممکن است با هر یک از انواع داده‌ساختارهایی مثل آرایه ، لیست پیوندی و... پیاده‌سازی شوند. صرف‌نظر از این‌که از کدام‌یک استفاده می‌کنیم، پیاده‌سازی دو تابع Push (برای گذاشتن داده) و Pop (برای برداشتن داده) بسیار مهم است. نکتهٔ مهم دیگر در پیاده‌سازی پشته، نگه‌داشتن اشاره‌گری به آخرین داده‌ است که اصطلاحاً به آن Top گفته می‌شود. اگر فرض کنیم که پشته با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Push و Pop به صورت زیر خواهد بود:


شمايی از افزودن یک عنصر به پشته (Push)


شمايی از برداشتن یک عنصر از پشته (Pop)
procedure Push(data d)
begin
stack[top]:=d; //here "stack" is the array that stores data
top:=top+1; //here "top" is a pointer to above of top element
end;

function Pop: data
begin

top:=top-1; //here "top" is a pointer to above of top element
result:=stack[top]; //here "stack" is the array that stores data
end;
مشابه پشته‌ها، صف‌ها نیز می‌توانند با انواع داده‌ساختارهایی مثل آرایه یا لیست‌ پیوندی پیاده‌سازی شوند. باز هم، صرف‌نظر از این که از کدام داده‌ساختار استفاده می‌کنیم، پیاده‌سازی دو تابع Enqueue (صف‌افزایی، افزودن به ته صف) و Dequeue (صف‌گشایی، خروج از سر صف) ضرورت دارد. اگر فرض کنیم که صف با آرایه پیاده‌سازی شده باشد، شبه‌کد تابع‌های Enqueue و Dequeue به این صورت خواهد بود:
procedure Enqueue(data d)
begin
endofqueue:=endofqueue+1; //"endofqueue" indicates the number of queue elements
for i:=2 to endofqueue do
begin
queue[i]:=queue[i-1]; //shi

fting; here "queue" is the array that stores data
end;
queue[1]:=d;
end;