• Two-way queue:
  A double-ended queue is an ordered data set. Data items can be added from the head of the queue or from the tail of the queue, and data items can also be deleted from both ends; in a sense, the double-ended queue integrates stack and Queue capacity.
  However, double-ended queues do not have inherent LIFO and FIFO characteristics. If double-ended queues are used to simulate stacks and queues, users need to maintain the consistency of operations by themselves.
  • The operation of the two-way queue:
    deque() creates an empty deque
    addfront(item) adds item to the front of the team
    addrear(item) adds item to the end of the queue
    removefront() removes the data item from the front of the team, the return value is the removed data item
    removerear() removes the data item from the end of the queue, the return value is the removed data item
    isempty() returns whether the deque is empty
    size() returns the number of data items contained in the deque**
    For example:
    
    Implemented in code as:

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

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

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

    def add_rear(self, item):
        self.items.insert(0, item)

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

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

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

• Application of Bidirectional Queue – Palindrome Detection
  "Palindrome" is a string with the same forward reading and reverse reading (both in Chinese or English).
  Algorithm idea:
  It is easy to solve the palindrome problem by using a double-ended queue. First, the words to be determined are added to the deque from the end of the queue, and then the characters are removed from both ends to determine whether they are the same, until there are 0 or 1 characters left in the deque.
  (Consider the case where the number of words in the palindrome is odd and even)
  Write it yourself as:

def palchecker(astring):
    deque = Deque()
    wordchecker = True
    for i in astring:
        deque.addrear(i)

    while deque.size() > 1 and wordchecker :
        temp1 = deque.removerear()
        temp2 = deque.removefront()
        if temp1 != temp2:
            wordchecker = False

    return wordchecker

print(palchecker('aialblaia'))
print(palchecker('word'))

The disadvantage is that the variable names used are not accurate enough, and the code self-explanatory notes are poor.
The standard code is

def palchecker(aString):
    chardeque = Deque()

    for ch in aString:
        chardeque.addrear(ch)

    stillEqual = True
    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removefront()
        last = chardeque.removerear()
        if first != last:
            stillEqual = False
    return stillEqual

print(palchecker("lsdkjfskf"))
print(palchecker("radar"))

• UnorderedList implemented by linked list −

  • What is an unordered table?
    Although the list data structure requires to maintain the relative positions of the data items before and after, the maintenance of the front and rear positions does not require the data items to be sequentially stored in a continuous storage space.
    As shown in the figure below, there are no rules for the storage location of data items, but if you establish links between data items, you can maintain their relative positions before and after. The first and last data items need to be displayed and marked, one is the head of the team, the other is the tail of the team, and there is no data behind. It is an unordered list.

 - linked list implementation node Node: 

	The most basic element of a linked list implementation is the node Node，Each node must contain at least two pieces of information: the data item itself, and a reference to the next node. Notice next for None The meaning is that there is no next node.
Linked list implements unordered list UnorderedList
 An unordered table can be implemented by constructing a dataset by linking nodes.

• Linked list implements unordered list UnorderedList

The first and last nodes of the linked list are the most important. If you want to visit all the nodes in the linked list, you must start from a node and traverse along the link.
Therefore, the unordered table must have reference information to the first node, set up an attribute head to save the reference to the first node, and the head of the empty table is None.
With the addition of data items, the head of the unordered list always points to the first node of the chain, and the unordered list mylist object itself does not contain data items (data items are in nodes). The head contained in it is only a reference to the first node Node, and isEmpty() for judging an empty table is easy to implement.
The unordered list implements the add method. Considering the performance of the implementation, it should be added to the position where it is easiest to add, that is, the header, the first position of the entire linked list.
As shown below:

 - linked list implementation size
 from the head of the linked list head Start traversing to the end of the table and use the variable to accumulate the number of nodes passed through.
 

 - linked list implementation search
 from the head of the linked list head Start traversing to the end of the table, and at the same time determine whether the data item of the current node is the target.

Key point: linked list implementation: remove(item) method
First find the item. This process is the same as search, but when deleting nodes, special skills are required.
current points to the node that currently matches the data item, and deletion needs to point the next node of the previous node to the next node of the current, so we need to maintain the reference of the previous (previous) node while searching for the current.

After the item is found, current points to the item node, previous points to the previous node, and the deletion starts. There are two situations that need to be distinguished: current is the first node; or a node located in the middle of the chain.

There is no overall standard code, and it is modified locally to

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

class UnorderedList:
    def __init__(self):
        self.head = None

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    def search(self,item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

• Implementing OrderedList with Linked List
  When implementing an ordered list, you need to remember the relative position of the data items, depending on the "size" comparison between them, the Node definition is the same, and the OrderedList also sets a head to hold a reference to the linked list header.
  For isEmpty(), size(), remove() methods are independent of node order, and their implementation is the same as UnorderedList.
  The search and add methods need to be modified.
  • Ordered table implementation: search method:
    In the search of an unordered list, if the data item to be searched does not exist, the entire linked list will be searched until the end of the list.
    For an ordered list, the orderly arrangement of the nodes in the linked list can be used to save the search time when there is no data item for the search. Once the data item of the current node is larger than the data item to be searched, it means that there is no more data item to be searched after the linked list, and False can be returned directly.
  • Ordered table implementation: add method
    The add method must ensure that the added data items are added in the proper position to maintain the order of the entire linked list.
    Find the first data item larger than the added item from scratch, and insert the added item before the data item.
    Similar to the remove method, a previous is introduced, which follows the current node current.

The same code as above:

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

class OrderedList:
    def __init__(self):
        self.head = None

    def search(self,item):
        current = self.head
        found = False
        stop = False
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)