لایه دسترسی شبکه عملیات لایه فیزیکی و لایه پیوند داده مدل 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 را با هم تلفیق می کند .
ولی در بعضی از پشته ها این دسترسی به روشهای متفاوتی پیاده سازی خواهد شد .
▪ لایه ارتباطات اینترنتی لایه ارتباطات اینترنتی مسئول ایجاد ارتباط بین میزبانها است ، بدون توجه به لایه دسترسی به شبکه ای که بکار گرفته شده است .
بعلاوه لایه ارتباطات اینترنتی مسئول فراهم آوردن همه اطلاعات لازم برای لایه دسترسی به شبکه به مـنـظور فرستادن فریمهایش به مقـصـد مـحـلی است ( یا مقـصد میـزبـان دیـگری یا مسیـریـاب) .
بـنـابرایـن ، ایـن لایـه بـایـد پروتکل ARP ( Address Resolution Protocol) را هم در بر داشته باشد .
بعلاوه این لایه می بایست قادر به مسیریابی داده ها از طریق Internetwork به مقصدهای خود باشد .
همچنین لایه ارتباطات اینترنت شامل قابلیتهایی برای میزبانها به منظور تبادل اطلاعات درباره مشکلات یا خطا ها در شبکه می باشد .
این فرآیند توسط پروتکل (Internet Group Management Protocol) پشتیبانی می شود.
لایه ارتباطات میزبان به میزبان : لایه ارتباطات میزبان به میزبان سرویسهای مورد نیاز برای ایجاد ارتباطات قابل اعتماد بین میزبانهای شبکه را پیاده سازی می کند و مطابق با لایه حمل و قسمتی از لایه جلسه مدل OSI است و در ضمن در برگیرنده قسمتی از کارهای لایه های نمایش و کاربردی نیز می باشد .
آن شامل ویژگیهای زیر می باشد : ▪ قسمت بندی داده ها به بسته (Packets) ▪ ساخت رشته های داده از بسته ها ▪ دریافت تائید ▪ سرویس های سوکت برای ایجاد چندین ارتباط با چندین پورت روی میزبانهای دور ▪ بازبینی بسته و کنترل خطا ▪ کنترل جریان انتقال داده ▪ مرتب سازی و ترتیب بندی بسته سرویس های TCP سرویس های ارتباط گرای قابل اعتمادی با قابلیتهای زیبای کشف خطا ها و مشکلات را فراهم می کنند .
پروتکل دوم در لایه میزبان به میزبان ،UDP (User Datagram Protocol) نام دارد .
هـر چند که این لایه هم مدیریت بسته و سرویس های مرتب سازی را ارائه می دهد ولی UDP نیاز به سرویس های قدرتمند ارتباط گرای TCP مثل تائید ، کنترل جریان داده و مرتب سازی مجدد بسته ها برای انجام کارهای خود را دارد .
لایه سرویس های کاربردی : لایه سرویس های کاربردی لایه دیگری است که به راحتی با مدل 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]; //shifting; here "queue" is the array that stores data end; queue[1]:=d; end; function Dequeue: data begin result:=queue[endofqueue]; endofqueue:=endofqueue-1; end; شمایی از ورود یک عنصر به صف (Enqueue) شمایی از خروج یک عنصر از صف (Dequeue) البته این کدها به ساده‌ترین صورت ممکن نوشته شده‌اند و حالت‌های خاص را در آنها در نظر نگرفته‌ایم.
پیچیدگی زمانی در پیاده‌سازی آرایه‌ای پیچیدگی زمانی اضافه کردن یک عنصر به یک پشته یا برداشتن یک عنصر از روی یک پشته با پیاده‌سازی آرایه‌ای، از (O(1 است.
این موضوع با توجه به شبه‌کد نمونه‌ای که در قسمت قبل برای پیاده‌سازی با آرایه طرح شده‌است، کاملاً قابل توجیه‌است.
با این حال، پیچیدگی زمانی افزودن عنصری به صف در پیاده‌سازی آرایه‌ای، با پیچیدگی زمانی خروج عنصری از صف تفاوت دارد.
در مورد افزودن یک عنصر، از (O(n است که n نشان‌دهندهٔ تعداد عنصرهای موجود در صف است.
علت این امر آن است که با ورود هر عنصر به ته صف، همهٔ عنصرهای دیگر باید به اندازهٔ یکی جابه‌جا شوند تا جا برای این عنصر تازه باز شود.
این در حالی است که خروج یک عنصر از صف دارای پیچیدگی زمانی از (O(1 است.
می‌بینیم که در پیاده‌سازی آرایه‌ای، پیچیدگی زمانی افزودن و برداشتن عنصرها از/به صف و پشته، با هم متفاوت است.
با این وجود اگر صف و پشته را با لیست‌های پیوندی پیاده‌سازی کنیم، به علت ساختار خاص این لیست‌ها، هردوی این اعمال برای هم صف و هم پشته، دارای پیچیدگی زمانی از (O(1 خواهد بود.
چند حالت نامطلوب هنگام پیاده‌سازی پشته، باید حالت‌های خاص زیر را هم در نظر گرفت: هنگام صداکردن تابع Push در پشته‌ها، در صورتی که پشته پر باشد، خطای سرریز رخ خواهد داد.
البته این اتفاق در صورتی می‌افتد که ظرفیت پشته تعیین‌شده باشد و نتوانیم آن را افزایش دهیم.
برای مثال، خطای Stack Overflow در زمانی که حافظهٔ در نظرگرفته شده برای برنامه کافی نباشد، از طرف سیستم‌عامل تولید می‌شود.
هنگام صداکردن تابع Pop در پشته‌ها، در صورتی که پشته خالی باشد، خطای پاریز رخ می‌دهد.
هنگام صداکردن تابع Enqueue در صف، اگر صف پر باشد، خطای سرریز رخ خواهد داد.
البته این خطا در صورتی اتفاق می‌افتد که ظرفیت پشته تعیین‌شده و محدود باشد و نتوانیم آن را افزایش دهیم.
هنگام صداکردن تابع Dequeue در صف، اگر صف خالی باشد، خطای پاریز اتفاق می‌افتد.
کاربردها پشته‌ها در زمینه‌های بسیاری به کار می‌روند که البته در هر زمینه کارایی مشابهی هم دارند.
پشته‌ها برای محاسبهٔ یک عبارت ریاضی به طوری که ابتدا عملوندها و سپس عملگرها در پشته قرار می‌گیرند، به کار می‌روند.
علاوه بر این، برای مدیریت حافظهٔ موردنیاز برنامه، نگه‌داری روند فراخوانی تابع‌های مختلف در برنامه، برای پیاده‌سازی الگوریتم جست‌وجوی عمق اول و...
نیز از پشته‌ها استفاده می‌شود.
از صف‌ها در کاربری‌هایی که در آنها، اشیاء، پدیده‌ها و روی‌دادها در انتظارند تا پردازش شوند، بیشتر استفاده می‌شود.
مدیریت پیام‌ها در سیستم‌عاملی مثل ویندوز، مدیریت فهرست کارهایی که باید به ترتیب انجام شوند، پیاده‌سازی الگوریتم جست‌وجوی سطح اول و...
از جمله مواردی است که در آنها از صف‌ها استفاده می‌شود.
روند توسعه در سیستم‌هایی که به شدت به پشته‌ها وابسته‌اند، علاوه بر تابع‌هایی که گفته شد، تابع‌های دیگری نیز برای آسان‌تر شدن کار پیاده‌سازی می‌شوند و به این ترتیب پشته‌ها توسعه پیدا می‌کنند.
برخی از این اعمال را در زیر شرح می‌دهیم: مشابه‌سازی: با یک بار Pop کردن و دوبار Push کردن بالاترین دادهٔ پشته، این داده به دو دادهٔ مشابه تبدیل می‌شود (به عبارت دیگر تکثیر می‌شود).
برداشت: بالاترین داده Pop می‌شود ولی اشاره‌گر Top تغییر نمی‌کند؛ به عبارت دیگر، داده به دست ما می‌رسد ولی کماکان در پشته هم وجود دارد.
جابه‌جایی: بالاترین دو دادهٔ پشته، با هم جابه‌جا می‌شوند.
جابه‌جایی کلی: همه عناصر پشته یکی به سمت پایین جابه‌جا می‌شوند و پایین‌ترین داده در جای بالاترین داده قرار می‌گیرد.
علاوه بر این‌ها، از ترکیب صف و پشته، داده‌ساختار جدیدی هم ایجاد شده‌است که هم امکان افزودن عنصرها را از دوسوی تودهٔ داده‌ها می‌دهد و هم امکان برداشتن آنها را.
ساختارهای خطی داده‌هاآرایه صف‌گشایی توده لیست پیوندی صف پشته