Stack হচ্ছে একধরনের লিনিয়ার ডাটা স্ট্রাকচার যেখানে ডাটাগুলো টপ পজিশন থেকে ইন্সার্ট ও ডিলিট হয়। অর্থাৎ , এটি LIFO Principal ফলো করে। LIFO → Last In First Out
অর্থাৎ , সবার শেষে যে ঢুকবে সেই সবার শেষে বের হবে। আরেকটু সহজ উদাহারন দিয়ে বুঝানো যাক। ধরো , তোমার বাসায় খাবার খাওয়ার সময় তোমার মা তোমাদেরকে বললো যার যার খাবার শেষে প্লেটগুলো একটার উপরে একটা সাজিয়ে রাখতে। পরে তিনি সেটা ওয়াশ করবেন। এখন সবাি খাবার পর একটার পর একটা প্লেট সাজিয়ে রাখলো। যে সবার শেষে খেয়ে উঠেছে তার প্লেটটি সবার উপরে এবং দেখা গেলো তার প্লেটটি সবার আগে ওয়াশ করা হয়েছে। একেই বলে Last In First Out🙂

Stack DS আমরা দুইভাবে ইমপ্লিমেন্ট করতে পারি। প্রথমত Array দিয়ে এবং দ্বিতীয়ত Linked List দিয়ে। দুইভাবে ইমপ্লিমেন্ট করা শিখবো আমরা🙂

Basic Structure of Array Based Stack

class Stack:
    def __init__(self , size):
        self.max_index = size - 1
        self.top = -1
        self.stack = [None]*size

এখানে Stack class এর নতুন অব্জেক্ট তৈরি করার সময় স্ট্যাক এর সাইজ কত হবে সেটি নেয়া হয়েছে এবং সেই সাইজের একটি স্ট্যাক তৈরি করা হয়েছে। যেহেতু , Array তে ইন্ডেক্সিং শুরু হয় ০ থেকে সেহেতু এই Array এর ম্যাক্সিমাম ইন্ডেক্স হবে size - 1 । ধরে নিলাম আপাদত স্ট্যাকে কোন ডাটা নেই। সেহেতু top = -1 সেট করা হয়েছে।

Push Algorithm

→ প্রথমে দেখতে হবে Stack overflow কিনা। যদি Stack জায়গা না থাকে এবং আমরা Stack এ ডাটা ইন্সার্ট করতে চাই তাহলে তাকে Stack Overflow বলবো।
→ যদি Stack এ জায়গা থাকে তাহলে top এর মান ১ বাড়িয়ে সেই ইন্ডেক্সে ডাটা ইন্সার্ট করবো।

def push(self , data):
    if self.top == self.max_index:
        print("Stack Overflow")
        return
    self.top += 1
    self.stack[self.top] = data

Pop Algorithm

→ প্রথমে দেখতে হবে Stack Underflow কিনা। যদি Stack ডাটা না থাকে এবং আমরা Stack থেকে ডাটা ডিলিট বা ডাটা নিতে চাই তাহলে তাকে Stack Underflow বলবো।
→ যদি Stack এ ডাটা থাকে তাহলে top index এ None সেট করে top এর মান ১ কমিয়ে দিতে হবে।

def pop(self):
    if self.top == -1:
        print("Stack Underflow")
        return
    data = self.stack[self.top]
    self.stack[self.top] = None
    self.top -= 1
    return data

Peek Operation

→ Peek করা মানে হলো স্ট্যাক থেকে সবচেয়ে উপরের ডাটা অর্থাৎ , stack[top] data রিটার্ন করা।

def peek(self):
    if self.top == -1:
        print("Stack Underflow")
        return
    return self.stack[self.top]

Basic Structure of Linked List Based Stack

class Node:
    def __init__(self , data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

এখানে top হলো Stack এর সবচেয়ে উপরের নোড। ইনিশিয়ালি ধরে নিলাম Stack এ কোন নোড নেই। সেহেতু top = None রাখা হয়েছে।

Push Operation

→ যেহেতু আমরা লিঙ্কড লিস্ট বেজড স্ট্যাক তৈরি করেছি সেহেতু এখানে Stack Overflow Condition কাজ হবে না। কারন , Array এর মতো Linked List এর কোন ফিক্সড সাইজ থাকে না। নতুন নোড তৈরি করলে মেমরি তে বিভিন্ন জায়গায় নোড সেভ হয় এবং প্রতিটি নোড লিঙ্কের মাধ্যমে চেইনিং করা থাকে।
→ প্রথমে চেক করতে হবে লিঙ্কড লিস্ট খালি কিনা। যদি খালি হয় তাহলে new_node = top হবে। আর যদি খালি না হয় তাহলে new_node→next = top এবং পরে top = new_node করতে হবে।

def push(self , data):
    new_node = Node(data)
    if self.top == None:
        self.top = new_node
    else:
        new_node.next = self.top
        self.top = new_node

Pop Operation

→ প্রথমে দেখতে হবে Stack Empty কিনা ! যদি খালি হয় তাহলে Stack Underflow দেখাতে হবে।
→ যদি খালি না হয় তাহলে top node টি অন্য কোন ভ্যারিয়েবলে স্টোর করে top = top.next করতে হবে।

def pop(self):
    if self.top == None:
        raise ValueError("Stack Underflow")
    popped_node = self.top
    self.top = self.top.next
    print(f"{popped_node.data} popped from stack ")

Traversing

def display(self):
        temp = self.top
        while temp:
            print(temp.data , end = "")
            temp = temp.next

→ সবার আগে temp variable এর মধ্যে top node কে স্টোর করে রাখা হয়েছে।
→ যদি temp থাকে তাহলে ডাটা প্রিন্ট করবে এবং temp = temp.next হবে।

Peek Operation

def peek(self):
    return self.top.data if self.top else "Stack is empty"

Test Code

stack = Stack()
for i in range(10):
    stack.push(i)
stack.display() # Output : 9876543210
for i in range(10):
    stack.pop()
stack.display() 
# Output
# 9 popped from stack 
# 8 popped from stack 
# 7 popped from stack 
# 6 popped from stack 
# 5 popped from stack
# 4 popped from stack 
# 3 popped from stack 
# 2 popped from stack 
# 1 popped from stack 
# 0 popped from stack 
print(stack.peek())
# Output : Stack is empty

এখানে শুধুমাত্র আমি Linked List based Stack এর টেস্ট কোড লিখেছি। একইভাবে Array based Stack ও কাজ করবে।