پشته در جاوا (Stack Implementation in Java)

در این جلسه تیم کدگیت را با آموزش پشته در جاوا همراهی کنید.پیش نیاز این جلسه شامل موارد زیر است:

  1. آشنایی با متد
  2. آشنایی با شی گرایی
  3. Generic
  4. آشنایی با constructor
  5. آشنایی با for
  6. آشنایی با if

پشته(stack)

پشته یکی از انواع داده‌ساختارها است و برای ذخیره و بازیابی دادهها کاربرد دارد. پشته به شما اجازه دسترسی به یک شی (object) را میدهد، آخرین شی که وارد پشته شده است. اگر ما آخرین شی را حذف کنیم میتوانیم به شی یکی مانده به آخر دسترسی داشته باشیم و همینطور تا آخر …… .ساختار پشته به صورت تصویر زیر است.

شته در جاوا

برای توضیح دادن پشته بهتر است یک مثال ساده بزنیم.مثال در مورد قرار دادن نامه(email هم میشود)است. فرض کنید ما نامه هایی که به دستمان میرسد را روی هم قرار میدهیم پس میتوان نتیجه گرفت نامه ای که بالاتر از همه قرار دارد همین اواخر و زودتر از بقیه به دست شما رسیده است. دومین نامه نسبت به نامه های زیری خود همین ویژگی را دارد.اگر نامه ای بیاید شما آن را در اول قرار می دهید و روی همه نامه های دیگر. معمولا ما با نامه هایی کار داریم که جدید هستند و نامه های قدیمی بعضی از آنها نگه میداریم بعضی از آنها را به زباله می اندازیم!!!

پشته در جاوا

این روند که توضیح داده شد تقریبا کاری است که پشته انجام میدهد. پشته مانند نامه ها اول خالی است سپس با آمدن نامه جدید به پشته یک عنصر وارد می شود. با مطالعه نامه میتوانید آن را دور بیندازید یا آن را سر جای قبلش قرار دهید در پشته شما می‌توانید دقیقا همین اعمال انجام دهید. خلاصه کارهایی که با پشته میشود انجام داد:

  1. Push: اضافه کردن عنصری به پشته.(آمدن نامه جدید)
  2. Pop: حذف بالاترین(جدیدترین) عنصر در پشته(دور انداختن نامه)
  3. Peek: دسترسی به بالاترین(جدیدترین) عنصر در پشته(بررسی نامه های جدید)
  4. Size: تعداد عناصر پشته (تعداد نامه ها )

برای پیاده سازی ما میتوانیم از دو راه استفاده کنیم:

  1. پیاده سازی پشته با لیست پیوندی
  2. پیاده سازی پشته با آرایه

پیاده سازی پشته با لیست پیوندی

برای پیاده سازی پشته با لیست پیوندی ابتدا باید با لیست پیوندی و انواع آن آشنا باشید. در آموزش های قبلی در مورد لیست پیوندی صحبت شده و پیشنهاد میشود ابتدا آن را مطالعه کنید سپس به ادامه این آموزش بپردازید.

پیاده سازی لیست پیوندی به طوری که ما را به هدف خودمان برساند بسیار ساده است. برای این کار ما از single linkedlist استفاده میکنیم و هر عنصر جدید(push) که وارد لیست ما شد ما آن را first قرار می دهیم.

پشته در جاوا

برای حذف یک عنصر(pop) ما اشاره گره first را به یک خانه جلوتر میبریم و تمام!!!!(به همین سادگی) برای peek صدا زدن ما فقط کافی است first را برگردانیم!!!! حال بهتر است کد توضیحات داده شده را بزنیم.ابتدا کلاس Node میسازیم(در لیست پیوندی توضیح داده شده است).

سپس کلاس دیگری به نام StackWithList میسازیم.در این کلاس stack را میسازیم.

کلاس iterator هم برای Stack خود مینویسیم.(کاملا مشابه لیست پیوندی)

یک main هم برای برنامه خود مینویسیم.

در متد main ما یک stack ساختیم و به آن سه string اضافه کردیم. سپس یک عنصر را pop کردیم(آخرین عنصر). سپس یک iterator ساختیم و کل stack را بعد از pop  چاپ میکند. خروجی به صورت زیر است.

پشته در جاوا

پیاده سازی پشته با آرایه

در این قسمت به پیاده سازی پشته توسط آرایه خواهیم پرداخت.ایده کار به این صورت است که ابتدا یک آرایه کوچک در نظر میگیریم(ابتدا به طول دو) و هر بار آرایه ما پر شد طول آن را دو برابر می کنیم. محتوای این آرایه object هایی است که به stack اضافه میشوند. کد زیر پیاده سازی این نوع stack را نشان میدهد.

در این جا چون آرایه استفاده میکنیم نیاز به یک iterator که از بالای Stack شروع به خواندن کند، داریم.اسم این کلاس reverseIterator میگذاریم.

متد main هم دقیقا شبیه پیاده سازی پشته با لیست پیوندی است.

پشورد: www.codegate.ir

 

دسته : java, جاوا, ساختمان داده در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz