ডেটা স্ট্রাকচার: স্ট্যাক এবং সারি

ওহে! আজ আমরা এমন একটি বিষয়ে কথা বলব যা যেকোনো প্রোগ্রামারের জন্য অত্যন্ত গুরুত্বপূর্ণ: ডেটা স্ট্রাকচার। উইকিপিডিয়া বলে: "একটি ডেটা স্ট্রাকচার হল একটি ডেটা সংস্থা, ব্যবস্থাপনা, এবং স্টোরেজ ফর্ম্যাট যা দক্ষ অ্যাক্সেস এবং পরিবর্তন করতে সক্ষম করে৷ আরও সঠিকভাবে, একটি ডেটা স্ট্রাকচার হল ডেটা মানগুলির একটি সংগ্রহ, তাদের মধ্যে সম্পর্ক, এবং ফাংশন বা ক্রিয়াকলাপ যা হতে পারে৷ ডেটাতে প্রয়োগ করা হয়েছে।" সংজ্ঞাটি কিছুটা বিভ্রান্তিকর, তবে এর সারাংশ পরিষ্কার। ডাটা স্ট্রাকচার হল এক ধরনের রিপোজিটরি যেখানে আমরা ভবিষ্যৎ ব্যবহারের জন্য ডেটা সঞ্চয় করি। প্রোগ্রামিং-এ, ডাটা স্ট্রাকচারের বিশাল বৈচিত্র্য রয়েছে। নির্দিষ্ট সমস্যাগুলি সমাধান করার সময়, প্রায়শই সবচেয়ে গুরুত্বপূর্ণ বিষয় হল সমস্যার জন্য সবচেয়ে উপযুক্ত ডেটা কাঠামো বেছে নেওয়া। এবং আপনি ইতিমধ্যে তাদের অনেকের সাথে পরিচিত! উদাহরণস্বরূপ, আপনি অ্যারে সম্পর্কে জানেন। এবং আপনিও পরিচিতMap(এই ডেটা স্ট্রাকচারকে "অভিধান" বা "অ্যাসোসিয়েটিভ অ্যারে" হিসাবেও উল্লেখ করা যেতে পারে)। এটা বোঝা খুবই গুরুত্বপূর্ণ যে ডেটা স্ট্রাকচার কোনো নির্দিষ্ট ভাষার সাথে আবদ্ধ নয়। এগুলি কেবল বিমূর্ত "ব্লুপ্রিন্ট" যা প্রতিটি প্রোগ্রামিং ভাষা একটি নির্দিষ্ট কাঠামোর নিজস্ব ক্লাস বা বাস্তবায়ন তৈরি করতে ব্যবহার করে। উদাহরণস্বরূপ, সবচেয়ে বিখ্যাত ডেটা স্ট্রাকচারগুলির মধ্যে একটি হল একটি লিঙ্ক করা তালিকা। আপনি উইকিপিডিয়ায় যেতে পারেন এবং এটি কীভাবে কাজ করে এবং এর কী কী সুবিধা এবং অসুবিধা রয়েছে সে সম্পর্কে পড়তে পারেন। সম্ভবত এটির সংজ্ঞা আপনার কাছে পরিচিত বলে মনে হবে :) "একটি লিঙ্কযুক্ত তালিকা হল ডেটা উপাদানগুলির একটি রৈখিক সংগ্রহ, যার ক্রম মেমরিতে তাদের শারীরিক অবস্থান দ্বারা দেওয়া হয় না৷ পরিবর্তে, প্রতিটি উপাদান পরের দিকে নির্দেশ করে৷" এটা আমাদের প্রিয় বর্ণনা করে LinkedList, তাই না? হ্যাঁ, এবং এটি ঠিক তাই :) জাভাতে, "লিঙ্কড তালিকা" ডেটা স্ট্রাকচার ক্লাস দ্বারা প্রয়োগ করা হয় LinkedList। কিন্তু অন্যান্য ভাষাও সংযুক্ত তালিকা বাস্তবায়ন করে! পাইথনে, এই ডেটা স্ট্রাকচারকে " llist" বলা হয়। স্কালায় একে " LinkedList" বলা হয়, ঠিক জাভাতে। একটি লিঙ্ক করা তালিকা হল মৌলিক সাধারণ ডেটা স্ট্রাকচারগুলির মধ্যে একটি, তাই আপনি দেখতে পাবেন যে এটি যেকোনো আধুনিক প্রোগ্রামিং ভাষায় প্রয়োগ করা হয়। একই জিনিস সহযোগী অ্যারে সত্য. এখানে উইকিপিডিয়া থেকে সংজ্ঞা দেওয়া হল: "একটি সহযোগী অ্যারে, মানচিত্র, প্রতীক টেবিল, বা অভিধান হল একটি বিমূর্ত ডেটা টাইপ যা (কী, মান) জোড়ার সংগ্রহের সমন্বয়ে গঠিত, যাতে প্রতিটি সম্ভাব্য কী সংগ্রহে একবারে একবারে উপস্থিত হয়।" যে কিছু মনে করিয়ে দেয়? :) হ্যাঁ। আমাদের জাভা ডেভেলপারদের জন্য, একটি সহযোগী অ্যারে হলMapইন্টারফেস. কিন্তু এই ডাটা স্ট্রাকচার অন্য ভাষায়ও বাস্তবায়িত! উদাহরণস্বরূপ, C# প্রোগ্রামাররা এটিকে "অভিধান" নামে চেনেন। এবং রুবিতে, এটি "হ্যাশ" নামে একটি শ্রেণীতে প্রয়োগ করা হয়। ঠিক আছে, আপনি পয়েন্টটি পেয়েছেন: ডেটা স্ট্রাকচারগুলি প্রোগ্রামিংয়ের সর্বজনীন ধারণা, এবং প্রতিটি প্রোগ্রামিং ভাষা তাদের নিজস্ব উপায়ে প্রয়োগ করে। আজ আমরা এই ধরনের দুটি কাঠামো অধ্যয়ন করব — স্ট্যাক এবং কিউ — এবং দেখব কীভাবে সেগুলি জাভাতে প্রয়োগ করা হয়।

জাভাতে স্ট্যাক

একটি স্ট্যাক একটি সুপরিচিত ডেটা কাঠামো। এটা খুব সহজ. আমাদের দৈনন্দিন জীবনে বেশ কিছু আইটেম একটি স্ট্যাক হিসাবে "বাস্তবায়িত" হয়। এই সাধারণ পরিস্থিতিটি কল্পনা করুন: আপনি একটি হোটেলে অবস্থান করছেন এবং দিনের মধ্যে আপনি কিছু ব্যবসায়িক চিঠি পেয়েছেন। আপনি তখন আপনার ঘরে ছিলেন না, তাই হোটেলের ক্লার্ক কেবল আপনার ডেস্কে আগত চিঠিগুলি রেখেছিলেন। প্রথমে, তিনি প্রথম চিঠিটি ডেস্কে রাখলেন। তারপর একটি দ্বিতীয় চিঠি এল, এবং তিনি এটি প্রথমটির উপরে রাখলেন। তিনি তৃতীয় অক্ষরটি দ্বিতীয়টির উপরে এবং চতুর্থটি তৃতীয়টির উপরে রাখলেন। এবং এখন, একটি সহজ প্রশ্নের উত্তর দিন: আপনি যখন আপনার ঘরে ফিরে আসবেন এবং টেবিলে স্ট্যাক দেখতে পাবেন তখন আপনি প্রথমে কোন চিঠিটি পড়বেন ? ঠিক আছে, আপনি শীর্ষে পড়বেনচিঠি. যে, সবচেয়ে সম্প্রতি আগত এক . এই ঠিক কিভাবে একটি স্ট্যাক কাজ করে. এই নীতিটিকে "লাস্ট ইন ফার্স্ট আউট" (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()পদ্ধতি)। ধরা যাক এটি একটি "বুদ্ধিমত্তা" বোনাস যা খেলোয়াড়কে গেমের পরবর্তী কার্ডটি খুঁজে বের করতে দেয়৷

আমাদের পদ্ধতির ভিতরে, আমরা স্ট্যাক ক্লাসের নিম্নলিখিত পদ্ধতিগুলিকে কল করি:

• 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());
   }
}

আমরা আমাদের ডেকে পাঁচটি কার্ড যোগ করেছি। তাদের মধ্যে প্রথম খেলোয়াড় নেন ৩টি। তিনি কোন কার্ড পেয়েছেন? কনসোল আউটপুট:

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

কনসোলে কার্ডগুলি যে ক্রমে প্রদর্শিত হয় সেদিকে মনোযোগ দিন। "এডউইন ভ্যানক্লিফ" কার্ডটি শেষবার ডেকে গিয়েছিল (এটি ছিল পঞ্চম কার্ড), এবং এটিই ছিল সেই কার্ড যা খেলোয়াড় প্রথমে আঁকেন। "মিলহাউস" ডেকে শেষ হওয়ার জন্য দ্বিতীয় ছিল এবং খেলোয়াড় এটিকে দ্বিতীয় স্থানে আঁকেন। "সিলভানাস" শীর্ষ থেকে তৃতীয় ডেকে গিয়েছিলেন এবং এটি ছিল তৃতীয় কার্ড যা খেলোয়াড় ড্র করেছিল। এর পরে, প্লেয়ার কার্ডগুলি বাতিল করে দেয়। প্রথমে সে এডউইন, তারপর মিলহাউস, তারপর সিলভানাসকে পরিত্যাগ করে। তারপরে আমরা কার্ডগুলিকে আমাদের বাতিল স্তূপে একে একে প্রদর্শন করি: কনসোল আউটপুট:

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

আবার, আমরা একটি স্ট্যাক কিভাবে কাজ করে দেখুন! আমাদের গেমে, বাতিল গাদাটিও একটি স্ট্যাক (ঠিক ড্র ডেকের মতো)। "এডউইন ভ্যানক্লিফ" প্রথমে বাতিল করা হয়েছিল। দ্বিতীয় কার্ড বাতিল ছিল মিলহাউস ম্যানাস্টর্ম, এবং এটি বাতিলের স্তূপে এডউইনের উপরে রাখা হয়েছিল। তারপরে সিলভানাসকে বাতিল করা হয়েছিল এবং এই কার্ডটি মিলহাউসের উপরে স্থাপন করা হয়েছিল। আপনি দেখতে পাচ্ছেন, স্ট্যাক সম্পর্কে জটিল কিছু নেই। তবুও, আপনাকে এই ডেটা কাঠামোটি জানতে হবে — এটি প্রায়শই চাকরির সাক্ষাত্কারের সময় জিজ্ঞাসা করা হয় এবং এটি প্রায়শই আরও জটিল ডেটা কাঠামো তৈরির ভিত্তি।

জাভাতে সারি

একটি সারি আরেকটি সাধারণ ডেটা কাঠামো। স্ট্যাক ছাড়াও, জাভা সহ অনেক প্রোগ্রামিং ল্যাঙ্গুয়েজও কিউ ডেটা স্ট্রাকচার বাস্তবায়ন করে। একটি সারি এবং একটি স্ট্যাকের মধ্যে পার্থক্য কি? একটি সারি LIFO নীতির উপর ভিত্তি করে নয়, বরং FIFO নীতির উপর ভিত্তি করে ("ফার্স্ট ইন, ফার্স্ট আউট")। এই নীতিটি বিবেচনা করে বোঝা সহজ, উদাহরণস্বরূপ, একটি সাধারণ লাইন বা সারি, বাস্তব জীবনে! উদাহরণস্বরূপ, মুদি দোকানে একটি লাইন। যদি লাইনে পাঁচজন লোক থাকে, তবে প্রথম একজনকে পরিবেশন করা হবে যিনি প্রথমে লাইনে প্রবেশ করেছিলেন । যদি অন্য একজন (ইতিমধ্যে লাইনে থাকা পাঁচজন ছাড়াও) কিছু কিনতে চায় এবং লাইনে দাঁড়ায়, তাহলে তাকে শেষ পর্যন্ত সেবা দেওয়া হবে, অর্থাৎ ষষ্ঠ। একটি সারির সাথে কাজ করার সময়, লেজে (পিছনে) নতুন উপাদান যুক্ত করা হয় এবং আপনি যদি একটি উপাদান পেতে চান তবে এটি মাথা (সামনের) থেকে নেওয়া হবে। একটি সারি কীভাবে কাজ করে সে সম্পর্কে আপনাকে মনে রাখতে হবে এই মূল নীতি। একটি সারির অপারেশন খুবই স্বজ্ঞাত, যেহেতু আমরা প্রায়শই বাস্তব জীবনে সারি খুঁজে পাই। এটি আলাদাভাবে লক্ষ্য করার মতো যে জাভাতে একটি সারি একটি ক্লাস দ্বারা নয়, একটি ইন্টারফেস দ্বারা প্রতিনিধিত্ব করা হয়: সারি। আরও কি, জাভাতে এই সারি ইন্টারফেসের অনেকগুলি বাস্তবায়ন রয়েছে। আমরা যদি ওরাকল ডকুমেন্টেশনের দিকে তাকাই, আমরা দেখতে পাব যে 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 । কি এটাকে বিশেষ করেছে? A Dequeহল একটি ডবল-এন্ডেড কিউ। এটি একটি নিয়মিত সারির কার্যকারিতা প্রসারিত করে, আপনাকে উভয় প্রান্তে (মাথা এবং লেজে) উপাদান যুক্ত করতে এবং সারির উভয় প্রান্ত থেকে উপাদানগুলি নিতে দেয়। সফ্টওয়্যার বিকাশে ডাবল-এন্ডেড সারিগুলি ব্যাপকভাবে ব্যবহৃত হয়। আমরা উপরে দেওয়া সারি ক্লাসের তালিকায় মনোযোগ দিন। তালিকাটি বেশ দীর্ঘ, কিন্তু এতে কি পরিচিত কিছু আছে?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

হা! এখানে আমাদের পুরানো বন্ধু LinkedList! সুতরাং, এটি সারি ইন্টারফেস প্রয়োগ করে? কিন্তু কিভাবে এটি একটি সারি হতে পারে? সব পরে, একটি 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 জন ভিআইপি গ্রাহক। একটি অগ্রাধিকার সারি আপনাকে প্রথমে তাদের পরিবেশন করতে দেবে! খুব দরকারী জিনিস, তাই না? :) .. এই বইটি পড়ে, আপনি শুধুমাত্র অনেক ডেটা স্ট্রাকচার (স্ট্যাক এবং সারি সহ) শিখবেন না, তবে আপনি নিজেও তাদের অনেকগুলি বাস্তবায়ন করবেন! উদাহরণস্বরূপ, যদি জাভা একটি স্ট্যাক ক্লাস না থাকে? আপনার প্রোগ্রামের জন্য এই ধরনের ডেটা স্ট্রাকচারের প্রয়োজন হলে আপনি কী করবেন? আপনাকে অবশ্যই এটি লিখতে হবে। আপনি Lafore এর বই পড়ার সময় , আপনি প্রায়ই ঠিক তাই করবেন. ফলস্বরূপ, তত্ত্বের একটি সাধারণ অধ্যয়ন থেকে আপনি যা পাবেন তার চেয়ে ডেটা স্ট্রাকচার সম্পর্কে আপনার বোঝার অনেক গভীর হবে :) আমরা আজকের জন্য তত্ত্বটি গুটিয়ে নিচ্ছি, কিন্তু অনুশীলন ছাড়া তত্ত্ব কিছুই নয়! কাজগুলি নিজেরাই সমাধান করবে না, তাই তাদের মোকাবেলা করার সময়! :)