Stack Abstract Data Type (With Implementation)

Reading Time: 5 minutes

Stacks

මුලින්ම මේ පාඩම් මාලාව හැඳින්වීමේදි අපි කතා කරා මොනවද මේ Data Structures කියන්නේ සහ ඇයි අපිට මේ දේවලි ඕන වෙන්නේ කියලා. ඒ ලිපිය බැලුවේ නැත්නම් මෙතනින් බලන්න.

හරි අපි අද කතා කරන්න යන්නේ අපේ පළවෙනි Data Type එක ගැන. stacks කියන්නේ එක්තරා විදියක Operations කිහිපයකට සීමා වෙලා තියෙන Data Type එකක්. ඒ කියන්නේ stack එක්ක අපිට කරන්න පුළුවන් වෙන්නේ Data ඇතුලට දාන එක, අන්තිමට දැම්ම Data එක ආපහු ගන්න එක හා අන්තිමට දැම්ම Data එක මොකද්ද කියලා බලන එක විතරයි. ඒකයි මේක ගොඩක්ම සරලම මට්ටමේ Data Type එකක් වෙන්නේ. මේ Data Type එකට Array එකකදි වගේ ඕන තැනකට Data දාන්නත් ඕන තැනකින් Data එළියට ගන්නත් බෑ. මේ Data Type එකට Data ගන්න සහ දාන්න පුළුවන් වෙන්නේ LIFO (Last In First out) කියන Method එකට අනුව. ඒ කියන්නේ ඔයාට මේ Data Type එකෙන් Data එකක් එළියට ගන්න ඕන නම් ගන්න පුළුවන් වෙන්නේ අන්තිමට ඇතුලට දැම්ම Data එක. තේරුනේ නැහැනේ? හරි අපි තව ටිකක් විස්තර ඇතිව බලමු.

FIFO කියන්නේ මොකක්ද?

සරලවම විස්තර කරන්න උදාහරණ කිහිපයක් කියන්නම්.

හිතන්න මේ වගේ පොත් ගොඩක් හදන්න වුනොත් ඔයාට පොත් ටික අරගෙන පිළිවෙලට පොත් එකින් එක අරගෙන ගොඩ ගහන්න වෙනවනේ. දැන් හිතන්න ඔයා ආපහු ඔය පිලිවෙලට හදපු පොත් ගොඩින් එකින් එක පොත් ආපහු ගන්නවා කියලා. ඒ කියන්නේ ඔයාට මුලින්ම ගන්න වෙන්නේ අන්තිමට තිබ්බ පොත. ඔයා මුලින්ම තිබ්බ පොත ආපහු ගන්න වෙන්නේ අන්තිමට. Stack එකත් මෙන්න මේ උදාහරණයට සමානයි. පොත් කියන්නේ හරියට ඔයාගෙ Stack එක ඇතුලේ තියෙන එක එක Data වගේ. පොත් ගොඩගහනවා වගේ ඔයා මේ Stack එකට Data දාන්න යන්නේ.

 

 

 

තවත් උදාහරණයක් තමයි හැමෝම වගේ දැකලා ඇති පුටු මේ විදියට එක උඩ එක අහුරලා තියෙන විදිය. හැමෝම මේක ප්‍රායෝගික ජීවිතේදි කරලත් ඇතිනේ. මේකෙදිත් වෙන්නේ උඩදි කිවුව පොත් උදාහරණෙ වුන කතාවම තමයි. අන්තිමට දැම්ම පුටුව තමයි ආපහු ගද්දී මුලින්ම ගන්න වෙන්නේ.

 

 

Stack Operations

මේ ලිපියේ මුලදිත් මම සඳහන් කරා Stack එකක තියෙන මූලිකම Operations ගැන. දැන් හදන්නේ ඒවා ගැන විස්තරාත්මකව කතා කරගෙන යන්න.

1. Push
2. Pop
3. Peek

1.PUSH

මේ Method එකෙදි කරන්නේ Stack එකට Data දාන එක. ඒ කියන්නේ Data දාන්නේ Stack එකේ Top එකට. ඒක වෙන්නේ කොහොමද කියලා උඩ උදාහරණත් එක්ක ඔයාලට තේරෙනවා ඇති කියලා හිතනවා. Stack එකකට Data Insert කරන්න තියෙන එකම Method එක PUSH කරන එක.

2.PULL

මේ Method එක යොදාගෙන තමයි Stack එකේ උඩම තියෙන Data එක ආපහු එළියට ගන්න. ඒකෙදි වෙන්නේ Stack එකෙන් අයින් වෙලා Data එක එළියට එන එක.

3.PEEK

මේකෙදි කරන්නේ Stack එකෙන් Data එක එළියට ගන්නේ නැතුව උඩම තියෙන Data එක මොකද්ද කියලා බලන ඒක. මේකෙදි Stack එකෙන් Data එක අයින් වෙන්නේ නෑ. නිකත් උඩ තියෙන්නේ මොකද්ද කියලා බලන එක විතරයි.

Implementation

Python:

class Stack(object):

    def __init__(self):
        self._list = []

    def push(self, item):
        self._list.append(item)

    def pop(self):
        try:
            return self._list.pop()
        except IndexError:
            raise IndexError('pop from empty stack')
    def peek(self):
        try:
            print(_list[len(_list-1)])
        except IndexError:
            raise IndexError('empty stack')

def main():
    st = Stack()
    # Push and print
    for i in range(10):
        st.push(i)
        print("Pushed ", i)
    st.push('Hello World')

    # Pop
    print(st.pop())

    # Exceptions
    while True:  # Empty the stack
        try:
            st.pop()
        except Exception as e:
            print('Exception: {0}'.format(e))
            break


if __name__ == '__main__':
    main()

C:

#include 
#include 

typedef struct stack {
	void *data;
	struct stack *next;
} Stack;

Stack *new_stack_node(void *data) {
	Stack *new_node = (Stack*) malloc(sizeof(Stack));
	if (new_node == NULL) {
		return NULL;
	}
	new_node -> data = data;
	new_node -> next = NULL;
	return new_node;
}

int push(Stack **stack, void *data) {
	Stack *new_node = new_stack_node(data);
	if (new_node == NULL) {
		return 0;
	}
	new_node -> next = *stack;
	*stack = new_node;
	return 1;
}

void *pop(Stack **stack) {
	if (*stack == NULL) {
		return NULL;
	}
	Stack *temp = *stack;
	*stack = (*stack) -> next;
	temp -> next = NULL;
	void *data = temp -> data;
	free(temp);
	return data;
}

int main() {
	int a = 5;
	float b = 6.0;
	char c[] = "Hello World!";
	Stack *st = NULL;
	push(&st, (void*) (&a));
	push(&st, (void*) (&b));
	push(&st, (void*) (c));
	char *c_popped = (char*) pop(&st);
	float b_popped = *((float*) pop(&st));
	int a_popped = *((int*) pop(&st));
	printf("%d %f %s\n", a_popped, b_popped, c_popped);
	if (pop(&st) == NULL) {
		printf("Unable to pop from empty stack\n");
	}
	return 0;
}

තවත් Languages වලින් බලන්න මෙතනින් යන්න.

දැන් අපි මේ ලියපු Stack එක භාවිතා කරලා විසදන්න පුළුවන් ගැටළු මොනවද කියලා පොඩ්ඩක් බලමු.

1. Parenthesis 

මේ ප්‍රශ්ණය තමයි අපි මොකක් හරි String එකක් දුන්නහම ඒ දුන්න String එක ඇතුලේ තියන වරහන් Balance වෙලා තියෙනවද කියලා බලන එක. උදාහරණයක් විදියට (3*[5+2]) මේ කොටසේ වරහන් Balance වෙලා තියෙන්නේ කියලා පේනවනේ. හැබැයි මේ වගේ එකක් ගන්න. (5+(5]} මේක Balance වෙලා නෑ. අන්න ඒ දේ හඳුන ගන්න අපි කොහොමද මේ stack එක යොදා ගන්නේ.

විසඳුම:

• අපි කරන්නේ අපිට Open Bracket({[() එකක් හම්බෙන හැම වෙලාවකම ඒක අපි Stack එකක් ඇතුලට දාගන්නවා.
• Close Bracket එකක් හම්බුණොත් අපි Stack එකෙන් එක පාරක් POP කරලා හම්බෙන Open Bracket එක අපේ Close Bracket එකට සමානයිද කියලා Check කරනවා. සමාන වුණොත් තවත් මේ විදියට ඉස්සරහට Check කරගෙන යනවා. නැත්නම් Program එක Close කරනවා ගැලපෙන්නේ නෑ කියලා.
• Bracket හැර හම්බෙන අනිත් හැම Character එකක්ම අපි නොසලකා හරිනවා.

වැඩේ තේරුණේ නෑ වගේ නම් ආපහු මේ Image එක දිහා බලන්න.

Implementation:

class Stack():
    def __init__(self):
        self.items=[]

    def isEmpty(self):
        return self.items==[]

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

x=str(input("Enter the Statement"))
s1=Stack()

u=0
d=0
for k in x:
    if k=='[' or k=='(' or k=='{':
        s1.push(k)
        d+=1

    elif k==']' or k==')' or k=='}':
        a=s1.pop()
        print(a,k)
        if (a=='(' and k==')') or (a=='[' and k==']') or (a=='{' and k=='}'):
            u+=1
            
        else:
            print("Not a Parantheses")

if u==d:
    print("This is a Parantheses")

 

2. Palindrome

මේ ප්‍රශ්ණෙ තමයි මුල ඉඳලා අගට කියෙවුවත් අග ඉඳලා මුලට කියෙවුවත් සමාන විදියට ශබ්ද වෙන වචන හොයන එක. උදාහරණයක් විදියට MADAM වගේ.

විසඳුම:

මේ ප්‍රශ්නෙ විසඳන්න අපි කරන්නේ මේ වගේ වැඩක්. අපිට දෙන String එක Stack එකකට දාගෙන ඒකෙන් POP කරගෙන තවත් Stack එකක් හදා ගන්නවා. ඒ කියන්නේ මේකෙදි Stacks දෙකක් යොදා ගන්න වෙනවා.  ඊට පස්සේ පළවෙනි Stack එකට ආපහු අර String එක දාගෙන මේ Stack දෙකෙන් POP කර කර බලනවා හැම element එකක්ම සමාන වෙනවද කියලා. POP කරන හැම සැරේකම Elements සමාන වෙනවා කියන්නේ මේක Palindrome එකක් වෙනවා.

Implementation: 

මේකෙ Implementation එක මම කරලා තියෙන්නේ Stack Class එකටමයි. එහෙම නැතුව වෙනම කරන්නත් පුළුවන් අවුලක් නැතුව.

class Stack(object):
    def __init__(self,items):
        self.items=[]
        for e in items:
            self.push(e)

    def push(self,item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def __repr__(self):
        return str(self.items)  

    def isPalindrome(self):
        tr=Stack([])
        t=Stack(self.items)
        while t.items:
            tr.push(t.pop())
        t=Stack(self.items)    
        while t.items and tr.items:
            c1=t.pop()
            c2=tr.pop()
            print c1,c2
            if c1!=c2: return False
        return True    

තවත් මේ Stack එක භාවිතා කරලා විසඳන්න පුළුවන් ප්‍රශ්ණ තියෙනවා Post Fix Expressions වගේ ගැටළු. ඒවාට පුළුවන්නම් උත්සාහ කරලා බලන්න. Code එකේ මොනවා හරි ප්‍රශ්ණයක් තිබුණොත් Comment කරන්න උදව් කරන්නම්…

ඊළඟ පාඩම QUEUES.