2
\$\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 Queue as a Single linked list. Feel free to make suggestions. Note: The code works.

Targeted Big O:

Search: O(n), EnQueue and DeQueue: O(1)

Methods:

en_queue(value): insert values
de_queue(): remove values
is_empty(): check to see if Queue is empty
peek_front(): look at what head points to without removing
peek_back(): look at what tail points to without removing
search(value): check to see if a value is in the Queue
length(): return size

Classes:

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



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

    def en_queue(self, value):
        new_node = Node(value)

        if self.tail is not None:
            # make the front attribute of old node point to new node
            self.tail.front = new_node

        else:
            # if first ever node in Queue both front and tail will point to it
            self.head = new_node

        self.tail = new_node
        self.count += 1

    def de_queue(self):
        if not self.is_empty():
            # point head to next node
            self.head = self.head.front
            print("sucess")
            self.count -= 1
        else:
            print("Empty QUEUE")

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.front

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

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

    def peek_back(self):
        return self.tail.data

    def queue_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 Queue


def main():

    print("-------Test Queue---------")
    print("-------Test En Queue------")
    my_queue = Queue()
    test_list = [1, 2, 3, 4, -2000000, 'a', 500000, 50]

    for i in test_list:
        my_queue.en_queue(i)
    print("-------En Queue Done-------")
    for i in my_queue:
        print(i.data)
    print("------Queue Print Done-----")
    print("------Queue Print Done-----")
    print(my_queue.peek_back())
    print(my_queue.peek_front())
    print("----------De Queue---------")
    my_queue.de_queue()
    print("--------De Queue Done------")
    for i in my_queue:
        print(i.data)
    print("-----Queue Print Done------")
    print("-----Test search-------")
    x = my_queue.queue_search('a')
    print(x)
    print("-------Full De Queue-------")
    while my_queue.length() != 0:
        my_queue.de_queue()
    print("--------De Queue Done------")
    for i in my_queue:
        print(i.data)
    print("-----Queue Print Done------")

if __name__ == "__main__":
    main()

Result:

-------Test Queue---------
-------Test En Queue------
-------En Queue Done-------
1
2
3
4
-2000000
a
500000
50
------Queue Print Done-----
------Queue Print Done-----
50
1
----------De Queue---------
sucess
--------De Queue Done------
2
3
4
-2000000
a
500000
50
-----Queue Print Done------
-----Test search-------
Found value
a
-------Full De Queue-------
sucess
sucess
sucess
sucess
sucess
sucess
sucess
--------De Queue Done------
-----Queue Print Done------

Process finished with exit code 0
\$\endgroup\$
2
  • 1
    \$\begingroup\$ My points from my other answer will be applicable to this as well. I am not sure about posting it here again. \$\endgroup\$ Commented Aug 25, 2017 at 4:33
  • 1
    \$\begingroup\$ yes yes indeed and i will implement them to this as well, i just did not want to create clutter, and taught since they are a bit different to post them separate \$\endgroup\$ Commented Aug 25, 2017 at 4:47

2 Answers 2

Reset to default
2
\$\begingroup\$

In addition to the points I had mentioned in my previous answer to your Stack implementation.

Your Queue is not introspectable right now as it lacks __repr__ method. Due to this you won't be able to view its items easily. Hence you could add __repr__ to both Node and Queue class(same applicable to your Stack class in other question).

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

    def __repr__(self):
        return repr(self.data)


class EmptyQueueException(Exception):
    pass


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

    def en_queue(self, value):
        new_node = Node(value)

        if self.tail is not None:
            # make the front attribute of old node point to new node
            self.tail.front = new_node
        else:
            # if first ever node in Queue both front and tail will point to it
            self.head = new_node

        self.tail = new_node
        self.count += 1

    def de_queue(self):
        if self:
            # point head to next node
            self.head = self.head.front
            self.count -= 1
        else:
            raise EmptyQueueException()

    def peek_front(self):
        if self:
            return self.head.data
        raise EmptyQueueException()

    def peek_back(self):
        if self:
            return self.tail.data
        raise EmptyQueueException()

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.front

    def __bool__(self):
        return not (self.head is None and self.tail is None)

    def __contains__(self, value):
        return value in (node.data for node in self)

    def __len__(self):
        return self.count

    def __repr__(self):
        return 'Queue<{nodes}>'.format(nodes=', '.join(repr(node) for node in self))

Demo:

>>> my_queue
Queue<1, 2, 3, 4, -2000000, 'a', 500000, 50>
>>> my_queue.de_queue()  # Probably want to return the value as well?
>>> my_queue
Queue<2, 3, 4, -2000000, 'a', 500000, 50>
>>> my_queue.peek_back()
50
>>> 'a' in my_queue
True
>>> 'spam' in my_queue
False
>>> bool(my_queue)
True
>>> len(my_queue)
7
>>> len(Queue())
0    
>>> bool(Queue())
False
>>> Queue().peek_back()
---------------------------------------------------------------------------
EmptyQueueException                       Traceback (most recent call last)
...
\$\endgroup\$
1
\$\begingroup\$

In en_queue(), the pythonic way to express if self.tail is not None: is if self.tail:

\$\endgroup\$
1
  • 3
    \$\begingroup\$ If the intention is to explicitly check against None then is not None is fine. \$\endgroup\$ Commented Aug 25, 2017 at 4:31

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.