3
\$\begingroup\$

Note: I do know that Python libraries provide a Linked List and Stack. This implementation has been done to practice Python and some of the data structures and Algorithms.

I have implemented Stack as a Singly Linked-List, feel free to make suggestions. Note: code works

Targeted Big O:

search: O(n), Push and Pop: O(1)

Methods:

push(value)- for insertion
pop()- for removing
is_empty()- to check if empty
peek()- look at what head holds without poping
stack_search(value)-find a value
length()-get size

Classes:

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

class Stack:
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, value):
        #make new node
        new_node = Node(value)
        self.count += 1

        if self.head is not None:
            #make new node point to the old node
            new_node.front = self.head
        # make head point to the new element
        self.head = new_node

    def is_empty(self):
        if self.head is None:
            return True
        else:
            return False

    def pop(self):
        if not self.is_empty():
            self.count -= 1
            temp = self.head.data
            # make head point to the node after the node that will be poped
            self.head = self.head.front
            return temp
        else:
            print("can not pop items from an empty list")

    def peek(self):
        return self.head.data

    def __iter__(self):
        # start from the node that head refers to
        node = self.head
        while node:
            yield node
            node = node.front

    def stack_search(self, value):
        # start from the head
        p = self.head
        while p is not None:
            # make p reference to next node
            if p.front is not None:
                if p.data == value:
                    print("Found value")
                    return p.data
                p = p.front
            else:
                print("fail")
                return 0

    def length(self):
        return self.count

Test:

from stack_Queue import Stack

def main():

    print("-------Test Stack----------")
    print("------Test push-------")
    my_stack = Stack()
    test_list = [1, 2, 3, 4, -2000000, 'a', 500000, 50]

    for i in test_list:
        my_stack.push(i)
    print("-------Push Done------")
    print("-------Dump stack-----")
    for i in my_stack:
        print(i.data)
    print("-----Dump stack Done---")
    print("----check count-------")
    print("should be: 8")
    print(my_stack.length())
    print("-----check count Done--")
    print("-------Test pop $ print remaining stack--------")

    my_stack.pop()
    for i in my_stack:
        print(i.data)
    print("-----Test pop Done-----")
    print("-----Test search-------")
    x = my_stack.stack_search('a')
    print(x)
    print("---Test search Done---")

    print("-----Test pop - full stack & print what is being poped-----")
    while my_stack.length() > 0:
        x = my_stack.pop()
        print(x)
    print("-----Test pop Done-----")
    print("-----Test Empty Stack-----")
    for i in my_stack:
        print(i.data)
    print("---------Done---------")

if __name__ == "__main__":
    main()

Result:

-------Test Stack----------
------Test push-------
-------Push Done------
-------Dump stack-----
50
500000
a
-2000000
4
3
2
1
-----Dump stack Done---
----check count-------
should be: 8
8
-----check count Done--
-------Test pop $ print remaining stack--------
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test search-------
Found value
a
---Test search Done---
-----Test pop - full stack & print what is being poped-----
500000
a
-2000000
4
3
2
1
-----Test pop Done-----
-----Test Empty Stack-----
---------Done---------

Process finished with exit code 0
\$\endgroup\$
1
\$\begingroup\$
  • Your stack_search function re-implements loop over your linked-list. Instead of that you can use your __iter__ itself to keep in DRY. Plus it should True or False instead of 1 and 0.

    The Pythonic way will be implement __contains__ to check if your container type contains an item. Then you could simply do 'a' in my_stack.

    def __contains__(self, value):
        return value in (node.data for node in self)
    
  • Instead of length method implement __len__. This will work with Python's built-in len().

    Plus after defining this you won't need the method is_empty either as __len__ can be used to check for falsyness: if my_stack: .... You could also define __bool__ based on self.head for checking falsiness instead of using __len__, but it would be redundant in my opinion.

  • pop() should raise an exception when the stack is empty, for example list.pop, dict.pop, deque.pop all raise some error for it.

  • Stack().peek() currently raises an AttributeError. Instead of that you should be raising some custom exception when the stack is empty.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.