1. Stack (LIFO, LIFO)

A stack (sometimes called a “stack”) is an ordered collection of items. Both add and remove items occur on the same “end”. This end is often called the “top”. The top of the other end is called the bottom.

Abstract data types of stacks Abstract data types of stacks are defined by the following structures and operations. A stack is structured. As described above, a stack is an ordered set of items, with the ends of items added and removed called “tops”. Stack commands are last in, first out. Stack operations are as follows:

Stack() creates a new empty Stack. It takes no arguments and returns an empty stack. Push(item) adds a new item to the top of the stack. It takes the argument item and has no return value. Pop () removes items from the top of the stack. It takes no arguments and returns item. The stack is modified. Peek () returns the item at the top of the stack without removing it. It takes no arguments. The stack is not modified. IsEmpty () tests to see if the stack isEmpty. It takes no arguments and returns a Boolean value. Size () returns the number of items on the stack. It takes no arguments and returns an integer.Copy the code

2. Queue (first-in, first-out, FIFO)

A Queue is a collection of sequential elements. New elements are added at one end of the Queue (rear), and removal of existing elements takes place at the other end (front). When an element is added to the queue, it moves from the back of the queue to the front until it becomes the next element to be removed from the queue.

Abstract data types of queues Abstract data types queues are defined by the following structures and operations. As mentioned earlier, a queue consists of an ordered series of elements that enter the queue at one end called the tail and are removed from the queue at the other end called the head. Queues maintain a “first in, first out” nature. Here are some operations on queues:

Queue() creates an empty Queue object, no arguments, and returns an empty Queue; Enqueue (item) Adds data items to the end of the queue, with no return value; Dequeue () removes an item from the queue head, no argument, and returns the item as the queue head; IsEmpty () tests whether it is an empty queue, takes no arguments and returns a Boolean value; Size () returns the number of data items in the queue without arguments.Copy the code

To realize the Queue

class Queue: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items) q = Queue() q.enqueue(4) q.enqueue('dog') q.enqueue(True) print(q.size()) print(q.isEmpty()) Q.e nqueue (8.4) print (q.d equeue ()) print (q.s considering ())Copy the code

3. Double-endian queues

A deque or double-ended queue is similar to a queue and is an ordered combination of a series of elements. The two ends are called front (front) and rear (rear), and the element remains in a two-ended queue until it reaches the two ends. Unlike queues, dual-ended queues have less stringent restrictions on the addition and removal of elements, which can be inserted and removed from both ends. It can be said that a hybrid linear data structure, a double-endian queue, has all the functionality that stacks and queues have separately.

Abstract data types Deque Abstract data types DeQUES are defined by the following structures and operations. As mentioned earlier, a two-ended queue is organized as a series of ordered elements that can be inserted or removed from the front or back of the queue. Here are some operations on a two-ended queue.

· Deque() creates an empty double-ended queue with no arguments and returns a Deque object. · addFront(item) Inserts an element at the beginning of the queue. The parameter is the element to be inserted and has no return value. · removeFront() removes an element at the beginning of the queue, with no arguments, and returns the element. The two - end queue will be changed. · removeRear() removes an element at the end of the queue with no arguments and returns the element. The two - end queue will be changed. · isEmpty() checks whether the double-ended queue isEmpty with no parameter and returns a Boolean value. · size() returns the number of data items in the dual-end queue, with no argument and an integer value.Copy the code

Implement a Deque

class Deque: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def addFront(self, item): self.items.append(item) def addRear(self, item): self.items.insert(0,item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) if __name__ == '__main__': d=Deque() print(d.isEmpty()) d.addRear(4) d.addRear('dog') d.addFront('cat') d.addFront(True) print(d.size()) Da ddRear print (d.i sEmpty ()) (8.4) print (d.r emoveRear ()) print (d.r emoveFront ())Copy the code

An anemone is a word that reads the same in front and back, such as radar, toot and Madam. We want to write an algorithm that checks if the string we put in is a phric.

from Deque import Deque 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 if __name__ == '__main__': print(palchecker("lsdkjfskf")) print(palchecker("aba"))Copy the code

4, list

A list is a collection of elements, each with a different relative position from the others. More specifically, we call this type of list an unordered list. We can think of lists as having the first item, the second, the third… You can also index to the beginning of the list (the first item) or the end of the list (the last item). For simplicity, let’s assume that the list cannot contain duplicates.

An UNORDEREDLIST structure is a collection of elements in which each element has a relative position that is different from the others. Some of the methods available for unordered lists are as follows.

* list() creates a new empty list. It takes no arguments and returns an empty list. *add(item) adds a new item to the list without returning a value. Assume the element is not in the list. *remove(item) Removes an element from the list. A parameter is required and the list is modified. This assumes that the elements are in the list. *search(item) Searches for elements in the list. Takes an argument and returns a Boolean value. *isEmpty() checks if the list isEmpty. Takes no arguments and returns a Boolean value. *size() returns the number of elements in the list. Takes no arguments and returns an integer. *append(item) Adds a new element to the end of the list. It takes one argument and has no return value. Assume that the item is not in the list. *index(item) Returns the position of the element in the list. It takes an argument and returns the location index value. This assumes that the element was originally in the list. *insert(pos,item) Adds a new element at the specified position. It takes two arguments and has no return value. Assume that the element does not exist in the list and that the list is long enough for the index provided by the argument. *pop() removes an element from the end of the list and returns it. It takes no arguments and returns an element. Assume that the list has at least one element. *pop(pos) removes the list element from the specified position and returns it. It takes a positional argument and returns an element. Assume that the element is in the list.Copy the code

Using linked lists to implement unordered list classes: NODE NODE The basic module implemented with linked lists is the NODE. Each node object must hold at least two pieces of information. First, the node must contain the list element itself. We call this the node’s “data field.” In addition, each node must maintain a reference to the next node.

# -* -coding: utF-8 -* -class Node: # def __init__(self,initdata): Self. data = initdata self.next = None def getData(self): return self.data (self) Def setData(self,newdata): self.data = newdata Def __init__(self): self. Head = None def isEmpty(self): Return 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()) if __name__ == '__main__': temp = Node(93) print(temp.getData()) mylist = UnorderedList() mylist.add(31) mylist.add(77) mylist.add(17) mylist.add(93) mylist.add(26) mylist.add(54) print(mylist.search(17)) mylist.remove(17) print(mylist.search(17))Copy the code

Abstract Data types: Ordered Lists Now, we consider a class of lists called ordered lists. For example, if the list of integers shown above was an ordered list (ascending), it could be written as 17,26,31,54,77, and 93. Since 17 is the smallest, it is the first element in the list. Again, because 93 is the largest element, its position in the list is last.

OrderedList() : creates a new empty OrderedList. It returns an empty ordered list and does not need to pass any arguments. Add (item): Adds a new element to the list in the same order. The new element is passed as an argument to the function without returning a value. Assume that this element does not originally exist in the list. Remove (item): Removes an element from a list. The element to be deleted is taken as an argument and the original list is modified. Assume that there are elements in the original list that you want to delete. Search (item) : Searches for an element in the list, taking the searched element as an argument and returning a Boolean value. IsEmpty () : tests whether the list isEmpty, takes no arguments and returns a Boolean value. Size () : Returns the number of elements in the list. Returns an integer without arguments. Index (item) : Returns the position of the element in the list. The element to be searched is entered as a parameter and the index value of this element is returned. Let's say this element is in the list. Pop () : Deletes and returns the last item in the list. Returns the deleted element without arguments. Assume there is at least one element in the list. Pop (pos) : Removes and returns the index POS specified item. The index value of the element to be deleted is required as an argument and the element is returned. Assume that the element is in the list.Copy the code

Implementing ordered lists When we consider the methods for ordered lists, we should note that the isEmpty and Size methods are implemented the same as unordered lists, because they only deal with the number of nodes in the list and not the actual value of the node. Similarly, the remove method doesn’t need to be changed, because we still need to find a node and remove it. But the remaining two methods, search and add, need some modification.

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.get_data() == item: found = True else: if current.get_data() > item: stop = True else: current = current.get_next() return found def add(self, item): current = self.head previous = None stop = False while current ! = None and not stop: if current.get_data() > item: stop = True else: previous = current current = current.get_next() temp = Node(item) if previous == None: temp.set_next(self.head) self.head = temp else: temp.set_next(current) previous.set_next(temp)Copy the code