ساختارهای داده در جاوا - پشته و صف

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

پشته در جاوا

پشته یک ساختار داده شناخته شده است. این بسیار ساده است و بسیاری از اشیاء از زندگی روزمره ما به عنوان یک پشته "پیاده سازی" می شوند. یک موقعیت ساده را تصور کنید: شما در یک هتل زندگی می کنید و در طول روز نامه های تجاری دریافت می کنید. از آنجایی که شما در آن زمان در اتاق نبودید، کارمند هتل به سادگی نامه های دریافتی را روی میز شما قرار داد. ابتدا حرف اول را روی میز گذاشت. بعد دومی آمد و آن را روی اولی گذاشت. سومین حرفی را که رسید بالای حرف دوم و حرف چهارم را روی حرف سوم گذاشت. حالا به یک سوال ساده پاسخ دهید: وقتی به اتاق خود می آیید و پشته ای را روی میز می بینید، ابتدا چه نامه ای را می خوانید ؟ درست است، حرف بالا را خواهید خواند . یعنی اونی که در زمان آخر اومد . این دقیقاً نحوه عملکرد یک پشته است. این اصل عملیاتی 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 {

   //  колода
   private Stack<Card> deck;

   //  сброс
   private Stack<Card> graveyard;

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

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

   public Card lookTopCard() {

       return deck.peek();
   }

   //  ..геттеры, сеттеры и т.д.
}

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

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

در متدهای ما، متدهای کلاس نامیده می شوند Stack:

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

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

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       //  создаем колоду и добавляем в нее карты
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Рагнарос"));
       deck.push(new Card("Пират Глазастик"));
       deck.push(new Card("Сильвана Ветрокрылая"));
       deck.push(new Card("Миллхаус Манашторм"));
       deck.push(new Card("Эдвин ван Клифф"));

       //  создаем сброс
       Stack<Card> graveyard = new Stack<>();

       //  начинаем игру
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setGraveyard(graveyard);

       //  первый игрок берет 3 карты из колоды
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Какие карты достались первому игроку?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       //  первый игрок отправляет в сброс 3 своих карты
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("Какие карты находятся в сбросе?");
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
       System.out.println(game.getGraveyard().pop());
   }
}

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

Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}

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

Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}

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

صف

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

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

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

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

ها، پس دوست قدیمی ما اینجاست LinkedList! یعنی اینترفیس رو پیاده سازی میکنه Queue؟ اما او چگونه می تواند یک صف باشد؟ پس از همه 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 نداشته باشد. اگر به چنین ساختار داده ای برای برنامه خود نیاز داشته باشید، چه می کنید؟ البته باید خودم بنویسم. هنگام خواندن کتاب لافوره، اغلب این کاری است که شما انجام خواهید داد. با تشکر از این، درک شما از ساختارهای داده بسیار گسترده تر از مطالعه ساده تئوری خواهد بود :) ما با تئوری امروز تمام شده ایم، اما تئوری بدون عمل چیزی نیست! مشکلات خود به خود حل نمی شوند، بنابراین اکنون زمان رسیدگی به آنها است! :)