ساختار داده: پشته و صف

سلام! امروز ما در مورد چیزی صحبت خواهیم کرد که برای هر برنامه نویسی بسیار مهم است: ساختارهای داده. ویکی‌پدیا می‌گوید: « ساختار داده یک سازماندهی، مدیریت و قالب ذخیره‌سازی داده است که دسترسی و اصلاح کارآمد را امکان‌پذیر می‌سازد. به‌طور دقیق‌تر، ساختار داده مجموعه‌ای از مقادیر داده‌ها، روابط بین آن‌ها و توابع یا عملیاتی است که می‌تواند انجام شود. به داده ها اعمال شود." تعریف کمی گیج کننده است، اما اصل آن واضح است. ساختار داده نوعی مخزن است که در آن داده ها را برای استفاده در آینده ذخیره می کنیم. در برنامه نویسی، تنوع بسیار زیادی از ساختارهای داده وجود دارد. هنگام حل مسائل خاص، اغلب مهمترین چیز این است که مناسب ترین ساختار داده را برای مشکل انتخاب کنید. و شما در حال حاضر با بسیاری از آنها آشنا هستید! به عنوان مثال، شما در مورد آرایه ها می دانید. و همچنین با آن آشنا هستید Map(این ساختار داده ممکن است به عنوان "فرهنگ لغت" یا "آرایه انجمنی" نیز شناخته شود). درک این نکته بسیار مهم است که ساختارهای داده به زبان خاصی گره نخورده اند. آنها به سادگی "طرح های" انتزاعی هستند که هر زبان برنامه نویسی از آنها برای ایجاد کلاس ها یا پیاده سازی های خود از یک ساختار خاص استفاده می کند. به عنوان مثال، یکی از معروف ترین ساختارهای داده، لیست پیوندی است. می توانید به ویکی پدیا بروید و در مورد نحوه کار و مزایا و معایب آن مطالعه کنید. شاید تعریف آن برای شما آشنا به نظر برسد :) "لیست پیوندی مجموعه ای خطی از عناصر داده است که ترتیب آنها با قرارگیری فیزیکی آنها در حافظه مشخص نمی شود. در عوض، هر عنصر به عنصر بعدی اشاره می کند." این معشوق ما را توصیف می کند LinkedList، اینطور نیست؟ بله، و این همان چیزی است که هست :) در جاوا، ساختار داده "لیست پیوندی" توسط LinkedListکلاس پیاده سازی می شود. اما زبان های دیگر نیز لیست های پیوندی را پیاده سازی می کنند! در پایتون، این ساختار داده " llist" نامیده می شود. در اسکالا آن را " " می نامند LinkedList، درست مانند جاوا. لیست پیوندی یکی از ساختارهای داده رایج اساسی است، بنابراین خواهید دید که در هر زبان برنامه نویسی مدرن پیاده سازی شده است. همین موضوع در مورد آرایه های انجمنی نیز صادق است. در اینجا تعریف ویکی پدیا آمده است: "آرایه انجمنی، نقشه، جدول نمادها یا فرهنگ لغت یک نوع داده انتزاعی است که از مجموعه ای از جفت (کلید، مقدار) تشکیل شده است، به طوری که هر کلید ممکن حداکثر یک بار در مجموعه ظاهر شود." آیا این شما را به یاد چیزی می اندازد؟ :) بله. برای ما توسعه دهندگان جاوا، یک آرایه انجمنی استMapرابط. اما این ساختار داده در زبان های دیگر نیز پیاده سازی شده است! به عنوان مثال، برنامه نویسان سی شارپ آن را با نام "Dictionary" می شناسند. و در Ruby در کلاسی به نام Hash پیاده سازی می شود. خوب، متوجه نکته شدید: ساختارهای داده مفاهیمی جهانی در برنامه نویسی هستند و هر زبان برنامه نویسی آنها را به روش خود پیاده سازی می کند. امروز ما دو ساختار از این قبیل - پشته و صف - را مطالعه خواهیم کرد و خواهیم دید که چگونه آنها در جاوا پیاده سازی می شوند.

پشته ها در جاوا

پشته یک ساختار داده شناخته شده است. بسیار ساده است. تعداد کمی از آیتم ها در زندگی روزمره ما به صورت پشته "پیاده سازی" می شوند. این وضعیت ساده را تصور کنید: شما در یک هتل اقامت دارید و در طول روز چند نامه تجاری دریافت کرده اید. شما در آن زمان در اتاق خود نبودید، بنابراین منشی هتل به سادگی نامه های دریافتی را روی میز شما گذاشت. ابتدا حرف اول را روی میز گذاشت. سپس نامه دوم رسید و آن را بالای نامه اول گذاشت. حرف سوم را روی حرف دوم و حرف چهارم را روی حرف سوم گذاشت. و حالا به یک سوال ساده پاسخ دهید: وقتی به اتاق خود برگردید و پشته روی میز را ببینید ابتدا چه نامه ای را می خوانید ؟ درست است، شما بالاترین حرف را خواهید خواند . یعنی همانی که اخیراً وارد شده است . این دقیقاً نحوه عملکرد یک پشته است. این اصل "آخرین در اولین خروج" (LIFO) نامیده می شود . پشته ها برای چه چیزهایی خوب هستند؟ خب، فرض کنید در حال ایجاد نوعی بازی ورق در جاوا هستید. یک دسته کارت روی میز قرار دارد. کارت های بازی شده کنار گذاشته می شوند. شما می توانید از دو پشته برای اجرای هر دو عرشه قرعه کشی و شمع دور ریختن استفاده کنید. بازیکنان کارت های خود را از بالای عرشه می گیرند، همان اصل را که در نامه های تجاری شما انجام می شود. وقتی بازیکنان کارت‌هایی را در شمع دور انداخته می‌گذارند، کارت‌های تازه دور انداخته شده روی کارت‌های قدیمی قرار می‌گیرند. در اینجا اولین تلاش ما در این بازی است که بر اساس یک پشته پیاده سازی شده است:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

همانطور که قبلاً گفتیم، ما دو پشته داریم: یک عرشه قرعه کشی و یک شمع دور ریختن. در جاوا، ساختار داده پشته در java.util.Stackکلاس پیاده سازی می شود. بازی کارتی ما دارای 3 روش است که اقدامات بازیکنان را توصیف می کند:

• یک کارت از عرشه بگیرید ( getCardFromDeck()روش)
• دور انداختن کارت ( discard()روش)
• به کارت بالا نگاه کنید ( lookAtTopCard()روش). بیایید بگوییم که این یک جایزه "هوشمندی" است که به بازیکن اجازه می دهد بفهمد کدام کارت بعدی در بازی قرار می گیرد.

در داخل متدهای خود، متدهای زیر کلاس Stack را فراخوانی می کنیم:

• push()- یک مورد را به بالای پشته اضافه می کند. وقتی کارتی را به شمع دور ریختن می فرستیم، به بالای شمع می رود
• pop()- عنصر بالایی را از پشته حذف می کند و آن را برمی گرداند. این روش برای اجرای اقداماتی که در آن بازیکن کارت می کشد بسیار مناسب است.
• peek()- عنصر بالای پشته را برمی گرداند، اما آن را از پشته حذف نمی کند

بیایید ببینیم بازی ما چگونه کار خواهد کرد:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

ما پنج کارت به عرشه خود اضافه کردیم. بازیکن اول 3 تا از آنها را گرفت. او کدام کارت ها را گرفت؟ خروجی کنسول:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

به ترتیب نمایش کارت ها روی کنسول دقت کنید. کارت "ادوین ونکلیف" آخرین بار به عرشه رفت (این کارت پنجم بود) و این کارتی بود که بازیکن اول آن را کشید. "Millhouse" در عرشه دوم شد و بازیکن دوم آن را کشید. "سیلواناس" سومین بار از بالا وارد عرشه شد و این سومین کارتی بود که بازیکن گرفت. بعد، بازیکن کارت ها را دور می اندازد. اول، او ادوین، سپس میلهاوس، سپس سیلواناس را دور می اندازد. سپس کارت‌های موجود در شمع دور انداختن خود را یکی یکی نمایش می‌دهیم: خروجی کنسول:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

یک بار دیگر، ما می بینیم که چگونه یک پشته کار می کند! در بازی ما، شمع دور انداختن نیز یک پشته است (درست مانند عرشه قرعه کشی). ابتدا «ادوین ونکلیف» کنار گذاشته شد. دومین کارت حذف شده Millhouse Manastorm بود و در بالای ادوین در شمع دور انداختن قرار گرفت. سپس Sylvanas دور انداخته شد و این کارت در بالای Millhouse قرار گرفت. همانطور که می بینید، هیچ چیز پیچیده ای در مورد پشته وجود ندارد. با این حال، شما باید این ساختار داده را بشناسید - اغلب در طول مصاحبه های شغلی در مورد آن سوال می شود، و اغلب مبنایی برای ایجاد ساختارهای داده پیچیده تر است.

صف در جاوا

صف یکی دیگر از ساختارهای داده رایج است. علاوه بر پشته ها، بسیاری از زبان های برنامه نویسی، از جمله جاوا، ساختار داده صف را نیز پیاده سازی می کنند. تفاوت بین صف و پشته چیست؟ یک صف بر اساس اصل LIFO نیست، بلکه بر اساس اصل FIFO ("اول وارد، اولین خروج") است. این اصل با در نظر گرفتن مثلاً یک خط یا صف معمولی در زندگی واقعی آسان است! به عنوان مثال، یک خط در فروشگاه مواد غذایی. اگر پنج نفر در صف باشند، اولین نفری که به او سرویس داده می شود، کسی است که اول وارد خط شده است . اگر شخص دیگری (علاوه بر پنج نفری که قبلاً در صف هستند) بخواهد چیزی بخرد و در صف قرار گیرد، آخرین سرویس می شود، یعنی ششم. هنگام کار با صف، عناصر جدیدی به دم (پشت) اضافه می شود و اگر بخواهید یک عنصر بگیرید، از سر (جلو) گرفته می شود. این اصل اصلی است که باید در مورد نحوه عملکرد یک صف به خاطر بسپارید. عملیات یک صف بسیار بصری است، زیرا ما اغلب صف ها را در زندگی واقعی پیدا می کنیم. شایان ذکر است که در جاوا یک صف نه با یک کلاس، بلکه توسط یک رابط نمایش داده می شود: صف. علاوه بر این، پیاده سازی های زیادی از این رابط صف در جاوا وجود دارد. اگر به مستندات اوراکل نگاه کنیم، خواهیم دید که 4 رابط مختلف و همچنین لیستی بسیار چشمگیر از کلاس ها، رابط Queue را به ارث می برند:

All known subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All known implementing classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

چه لیست بزرگی! اما، البته، در حال حاضر نیازی به حفظ تمام این کلاس‌ها و رابط‌ها ندارید - ممکن است سرتان منفجر شود :) ما فقط چند نکته مهم و جالب را در نظر می‌گیریم. ابتدا، بیایید به یکی از چهار "زیرواسط" Queue توجه کنیم: Deque . چه چیزی آن را اینقدر خاص میکند؟ A Dequeیک صف دو سر است. عملکرد یک صف معمولی را گسترش می دهد و به شما امکان می دهد عناصر را به هر دو انتها (در سر و دم) اضافه کنید و عناصر را از هر دو انتهای صف بگیرید. صف های دو سر به طور گسترده ای در توسعه نرم افزار استفاده می شود. به لیستی از کلاس های صف که در بالا ارائه کردیم توجه کنید. لیست بسیار طولانی است، اما آیا چیز آشنای در آن وجود دارد؟

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ها! اینجا دوست قدیمی ماست LinkedList! بنابراین، رابط Queue را پیاده سازی می کند؟ اما چگونه می تواند یک صف باشد؟ پس از همه، a LinkedListیک لیست پیوندی است! درست است، اما این مانع از صف بودن آن نمی‌شود :) در اینجا لیستی از تمام رابط‌هایی که پیاده‌سازی می‌کند آمده است:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

همانطور که می بینید، اینترفیس LinkedListرا پیاده سازی می کند Deque(باز هم این به معنای صف دو طرفه است). چرا این مورد نیاز است؟ این به ما اجازه می دهد تا عناصر را از ابتدا و انتهای یک LinkedList. همچنین به ما این امکان را می دهد که عناصر را به ابتدا و انتهای آن اضافه کنیم. در اینجا روش هایی وجود دارد که LinkedListاز Dequeرابط دریافت می شود:

• peekFirst()— اولین عنصر را برمی گرداند (اما آن را از صف حذف نمی کند).
• peekLast()— آخرین عنصر را برمی گرداند (اما آن را از صف حذف نمی کند).
• pollFirst()- اولین عنصر را از صف برمی گرداند و آن را حذف می کند.
• pollLast()— آخرین مورد را از صف برمی گرداند و آن را حذف می کند.
• addFirst()- یک مورد جدید به جلوی صف اضافه می کند.
• addLast()- یک مورد را به انتهای صف اضافه می کند.

همانطور که می بینید، LinkedListعملکرد یک صف دو طرفه را به طور کامل پیاده سازی می کند! و شما به چنین عملکردی در برنامه خود نیاز دارید، می دانید که آن را کجا پیدا کنید :) درس امروز به پایان می رسد. در پایان، من به شما چند لینک برای مطالعه بیشتر می دهم. ابتدا به این مقاله در مورد PriorityQueue توجه کنید . این یکی از جالب ترین و کاربردی ترین Queueپیاده سازی ها است. برای مثال، فرض کنید 50 نفر در صف فروشگاه شما هستند و 7 نفر از آنها مشتریان VIP هستند. یک PriorityQueue به شما اجازه می دهد ابتدا به آنها خدمت کنید! چیزهای بسیار مفیدی است، درست است؟ :) دوم، بد نیست یک بار دیگر به کتاب رابرت لافور "ساختارهای داده و الگوریتم ها در جاوا" اشاره کنیم . با خواندن این کتاب، نه تنها بسیاری از ساختارهای داده (از جمله پشته و صف) را یاد خواهید گرفت، بلکه بسیاری از آنها را خودتان نیز پیاده سازی خواهید کرد! به عنوان مثال، اگر جاوا کلاس Stack نداشته باشد چه می شود؟ اگر به چنین ساختار داده ای برای برنامه خود نیاز داشته باشید، چه می کنید؟ البته باید خودت بنویسی همانطور که کتاب لافور را می خوانید ، اغلب این کار را انجام می دهید. در نتیجه، درک شما از ساختارهای داده بسیار عمیق تر از آن چیزی خواهد بود که از یک مطالعه ساده این نظریه به دست می آورید :) ما در حال جمع بندی نظریه برای امروز هستیم، اما نظریه بدون عمل چیزی نیست! کارها خود به خود حل نمی شوند، پس وقت آن است که با آنها مقابله کنید! :)