- 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:
- The operation of the two-way queue:
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.
- What is an unordered table?
- 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.
- Ordered table implementation: search method:
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)