Python基本数据类型（四）

5、双向队列(deque)函数说明

一个线程安全的双向队列，可进可出，可以从两端添加和删除元素；

class deque(object):
    """
    deque([iterable[, maxlen]]) --> deque object
    
    Build an ordered collection with optimized access from its endpoints.
    
    提供了两端都可以操作的序列，这意味着，可以在序列前后都执行添加或删除；
    """
    def append(self, *args, **kwargs): # real signature unknown
        """ Add an element to the right side of the deque. """
        pass
        '''
        在deque的右边添加一个元素；
        例如：
        >>> from collections import deque
        >>> d = deque()
        >>> d
        deque([])
        >>> d.append('a')
        >>> d
        deque(['a'])
        >>> d.append('b')
        >>> d
        deque(['a', 'b'])
        >>> d.append(['b','c'])
        >>> d
        deque(['a', 'a', ['b', 'c']])
        >>> d.append('b','c')
        Traceback (most recent call last):
          File "<stdin>", line 1, in <module>
        TypeError: append() takes exactly one argument (2 given)
        '''
    def appendleft(self, *args, **kwargs): # real signature unknown
        """ Add an element to the left side of the deque. """
        pass
        '''
        在deque的左边添加一个元素；
        例如：
        >>> d = deque('a')
        >>> d
        deque(['a'])
        >>> d.appendleft('b')
        >>> d
        deque(['b', 'a'])
        '''
    def clear(self, *args, **kwargs): # real signature unknown
        """ Remove all elements from the deque. """
        pass
        '''
        从deque中删除所有元素；
        例如：
        >>> d = deque(['a','b'])
        >>> d
        deque(['a', 'b'])
        >>> d.clear()
        >>> d
        deque([])
        '''
    def count(self, value): # real signature unknown; restored from __doc__
        """ D.count(value) -> integer -- return number of occurrences of value """
        return 0
        '''
        返回值的出现次数；
        例如：
        >>> d = deque(['a','a'])
        >>> d.count('a')
        2
        '''
    def extend(self, *args, **kwargs): # real signature unknown
        """ Extend the right side of the deque with elements from the iterable """
        pass
        '''
        使用可迭代的元素扩展deque的右侧，即一次性可添加多个元素；
        例如：
        >>> d = deque(['a','b'])
        >>> d
        deque(['a', 'b'])        
        >>> d.extend(['c','d','e'])
        >>> d
        deque(['a', 'b', 'c', 'd', 'e'])
        '''
    def extendleft(self, *args, **kwargs): # real signature unknown
        """ Extend the left side of the deque with elements from the iterable """
        pass
        '''
        使用可迭代的元素扩展deque的左侧，即一次性可添加多个元素；
        例如：
        >>> d = deque(['a','b'])
        >>> d
        deque(['a', 'b'])
        >>> d.extendleft(['c','d','e'])
        >>> d
        deque(['e', 'd', 'c', 'a', 'b'])
        '''
    def pop(self, *args, **kwargs): # real signature unknown
        """ Remove and return the rightmost element. """
        pass
        '''
        删除并返回最右侧的元素；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.pop()
        'e'
        '''
    def popleft(self, *args, **kwargs): # real signature unknown
        """ Remove and return the leftmost element. """
        pass
        '''
        删除并返回最左侧的元素；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.popleft()
        'a'
        '''
    def remove(self, value): # real signature unknown; restored from __doc__
        """ D.remove(value) -- remove first occurrence of value. """
        pass
        '''
        删除指定的一个值；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.remove()
        Traceback (most recent call last):
          File "<stdin>", line 1, in <module>
        TypeError: remove() takes exactly one argument (0 given)
        >>> d.remove('a')
        >>> d
        deque(['b', 'c', 'd', 'e'])
        >>> d.remove('c')
        >>> d
        deque(['b', 'd', 'e'])
        >>> d.remove('b','d')
        Traceback (most recent call last):
          File "<stdin>", line 1, in <module>
        TypeError: remove() takes exactly one argument (2 given)
        '''
    def reverse(self): # real signature unknown; restored from __doc__
        """ D.reverse() -- reverse *IN PLACE* """
        pass
        '''
        将元素反转；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.reverse()
        >>> d
        deque(['e', 'd', 'c', 'b', 'a'])
        '''
    def rotate(self, *args, **kwargs): # real signature unknown
        """ Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left. """
        pass
        '''
        将最后的n个元素向右反转（默认n = 1），如果n为负，则将最前的n个元素向左反转；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.rotate()
        >>> d
        deque(['e', 'a', 'b', 'c', 'd'])
        >>> d.rotate(2)
        >>> d
        deque(['c', 'd', 'e', 'a', 'b'])
        >>> d.rotate(-4)
        >>> d
        deque(['b', 'c', 'd', 'e', 'a'])
        '''
    def __copy__(self, *args, **kwargs): # real signature unknown
        """ Return a shallow copy of a deque. """
        pass
        '''
        浅拷贝；
        '''
    def __delitem__(self, y): # real signature unknown; restored from __doc__
        """ x.__delitem__(y) <==> del x[y] """
        pass
        '''
        删除元素，等同于del；
        例如：
        >>> d = deque(['a','b','c','d','e'])
        >>> d.__delitem__(1)
        >>> d
        deque(['a', 'c', 'd', 'e'])
        >>> del d[2]
        >>> d
        deque(['a', 'c', 'e'])
        '''
    def __eq__(self, y): # real signature unknown; restored from __doc__
        """ x.__eq__(y) <==> x==y """
        pass
        '''
        等同于判断，返回布尔值；
        例如：
        >>> x = deque(['a','b','c','d','e'])
        >>> y = deque(['a','b','c','d'])
        >>> x.__eq__(y)
        False
        >>> x == y
        False
        >>> y = deque(['a','b','c','d','e'])
        >>> x == y
        True
        '''
    def __getattribute__(self, name): # real signature unknown; restored from __doc__
        """ x.__getattribute__('name') <==> x.name """
        pass
    def __getitem__(self, y): # real signature unknown; restored from __doc__
        """ x.__getitem__(y) <==> x[y] """
        pass
        '''
        返回队列指定下标的值，下标值需指定并为整数型，否则报错；
        例如：
        >>> x = deque(['a','b','c','d','e'])
        >>> x.__getitem__(2)
        'c'
        >>> x[3]
        'd'
        '''
    def __ge__(self, y): # real signature unknown; restored from __doc__
        """ x.__ge__(y) <==> x>=y """
        pass
        '''
        大于等于判断，返回布尔值；
        例如：
        >>> x = deque(['a','b','c','d','e'])
        >>> y = deque(['a','b','c','d'])
        >>> x.__ge__(y)
        True
        >>> x >= y
        True
        '''
    def __gt__(self, y): # real signature unknown; restored from __doc__
        """ x.__gt__(y) <==> x>y """
        pass
        '''
        大于判断，返回布尔值；
        '''
    def __iadd__(self, y): # real signature unknown; restored from __doc__
        """ x.__iadd__(y) <==> x+=y """
        pass
        '''
        自加，相当于+=；
        '''
    def __init__(self, iterable=(), maxlen=None): # known case of _collections.deque.__init__
        """
        deque([iterable[, maxlen]]) --> deque object
        
        Build an ordered collection with optimized access from its endpoints.
        # (copied from class doc)
        """
        pass
        '''
        构造方法，执行x = deque()时自动调用deque函数；
        '''
    def __iter__(self): # real signature unknown; restored from __doc__
        """ x.__iter__() <==> iter(x) """
        pass
        '''
        在deque上返回一个迭代器；
        '''
    def __len__(self): # real signature unknown; restored from __doc__
        """ x.__len__() <==> len(x) """
        pass
        '''
        返回队列长度；
        例如：
        >>> x = deque(['a','b','c','d','e'])
        >>> x.__len__()
        5
        >>> len(x)
        5
        '''
    def __le__(self, y): # real signature unknown; restored from __doc__
        """ x.__le__(y) <==> x<=y """
        pass
        '''
        小于等于判断，返回布尔值；
        '''
    def __lt__(self, y): # real signature unknown; restored from __doc__
        """ x.__lt__(y) <==> x<y """
        pass
        '''
        小于判断，返回布尔值；
        '''
    @staticmethod # known case of __new__
    def __new__(S, *more): # real signature unknown; restored from __doc__
        """ T.__new__(S, ...) -> a new object with type S, a subtype of T """
        pass
    def __ne__(self, y): # real signature unknown; restored from __doc__
        """ x.__ne__(y) <==> x!=y """
        pass
        '''
        不等于判断，返回布尔值；
        '''
    def __reduce__(self, *args, **kwargs): # real signature unknown
        """ Return state infORMation for pickling. """
        pass
        '''
        返回pickling的状态信息；
        '''
    def __repr__(self): # real signature unknown; restored from __doc__
        """ x.__repr__() <==> repr(x) """
        pass
        '''
        转化为解释器可读取的形式，即转换为字符串格式；
        '''
    def __reversed__(self): # real signature unknown; restored from __doc__
        """ D.__reversed__() -- return a reverse iterator over the deque """
        pass
        '''
        在deque上返回一个反向迭代器；
        '''
    def __setitem__(self, i, y): # real signature unknown; restored from __doc__
        """ x.__setitem__(i, y) <==> x[i]=y """
        pass
        '''
        对队列里，指定的下标值进行修改，i需为整数，并且不能超过队列的下标范围；
        例如：
        >>> x = deque(['a','b','c','d','e'])
        >>> x.__setitem__(2,'f')
        >>> x
        deque(['a', 'b', 'f', 'd', 'e'])
        >>> x[4] = 'g'
        >>> x
        deque(['a', 'b', 'f', 'd', 'g'])
        >>> x[5] = 'h'
        Traceback (most recent call last):
          File "<stdin>", line 1, in <module>
        IndexError: deque index out of range
        '''
    def __sizeof__(self): # real signature unknown; restored from __doc__
        """ D.__sizeof__() -- size of D in memory, in bytes """
        pass
        '''
        获取内存中队列的大小，以字节为单位；
        '''
    maxlen = property(lambda self: object(), lambda self, v: None, lambda self: None)  # default
    """maximum size of a deque or None if unbounded"""
    __hash__ = None

6、单向队列(Queue)函数说明

Queue是python标准库中的线程安全的队列FIFO（先进先出）实现，提供了一个适用于多线程编程的先进先出的数据结构，即队列，用来在生产者和消费者线程之间的信息传递；

class Queue:
    '''Create a queue object with a given maximum size.
    If maxsize is <= 0, the queue size is infinite.
    '''
    '''
    Queue提供了一个基本的FIFO容器，使用方法很简单,maxsize是个整数，指明了队列中能存放的数据个数的上限。一旦达到上限，插入会导致阻塞，直到队列中的数据被消费掉。如果maxsize小于或者等于0，队列大小没有限制。
    '''
    def __init__(self, maxsize=0):
        self.maxsize = maxsize
        self._init(maxsize)
        # mutex must be held whenever the queue is mutating.  All methods
        # that acquire mutex must release it before returning.  mutex
        # is shared between the three conditions, so acquiring and
        # releasing the conditions also acquires and releases mutex.
        self.mutex = threading.Lock()
        # Notify not_empty whenever an item is added to the queue; a
        # thread waiting to get is notified then.
        self.not_empty = threading.Condition(self.mutex)
        # Notify not_full whenever an item is removed from the queue;
        # a thread waiting to put is notified then.
        self.not_full = threading.Condition(self.mutex)
        # Notify all_tasks_done whenever the number of unfinished tasks
        # drops to zero; thread waiting to join() is notified to resume
        self.all_tasks_done = threading.Condition(self.mutex)
        self.unfinished_tasks = 0
        '''
        构造函数，执行x = queue()时自动调用Queue函数；
        '''
    def task_done(self):
        '''Indicate that a formerly enqueued task is complete.
        Used by Queue consumer threads.  For each get() used to fetch a task,
        a subsequent call to task_done() tells the queue that the processing
        on the task is complete.
        If a join() is currently blocking, it will resume when all items
        have been processed (meaning that a task_done() call was received
        for every item that had been put() into the queue).
        Raises a ValueError if called more times than there were items
        placed in the queue.
        '''
        with self.all_tasks_done:
            unfinished = self.unfinished_tasks - 1
            if unfinished <= 0:
                if unfinished < 0:
                    raise ValueError('task_done() called too many times')
                self.all_tasks_done.notify_all()
            self.unfinished_tasks = unfinished
        '''
        意味着之前入队的一个任务已经完成；
        由队列的消费者线程调用。每一个get()调用得到一个任务，接下来的task_done()调用告诉队列该任务已经处理完毕。
        如果当前一个join()正在阻塞，它将在队列中的所有任务都处理完时恢复执行（即每一个由put()调用入队的任务都有一个对应的task_done()调用）。
        如果调用的次数比在队列中放置的项目多，则引发ValueError；
        '''
    def join(self):
        '''Blocks until all items in the Queue have been Gotten and processed.
        The count of unfinished tasks goes up whenever an item is added to the
        queue. The count goes down whenever a consumer thread calls task_done()
        to indicate the item was retrieved and all work on it is complete.
        When the count of unfinished tasks drops to zero, join() unblocks.
        '''
        with self.all_tasks_done:
            while self.unfinished_tasks:
                self.all_tasks_done.wait()
        '''
        阻塞调用线程，直到队列中的所有任务被处理掉；
        只要有数据被加入队列，未完成的任务数就会增加；
        当消费者线程调用task_done()（意味着有消费者取得任务并完成任务），未完成的任务数就会减少；
        当未完成的任务数降到0，join()解除阻塞；
        '''
    def qsize(self):
        '''Return the approximate size of the queue (not reliable!).'''
        with self.mutex:
            return self._qsize()
        '''
        返回队列的大致大小（不可靠！）
        '''
    def empty(self):
        '''Return True if the queue is empty, False otherwise (not reliable!).
        This method is likely to be removed at some point.  Use qsize() == 0
        as a direct substitute, but be aware that either approach risks a race
        condition where a queue can grow before the result of empty() or
        qsize() can be used.
        To create code that needs to wait for all queued tasks to be
        completed, the preferred technique is to use the join() method.
        '''
        with self.mutex:
            return not self._qsize()
        '''
        如果队列为空，返回True，否则返回False（不可靠！）；
        这种方法很可能在某个时候被删除。并由qsize() == 0来替代，但是要注意，不管是使用empty()还是qsize()，都有可能会在队列产生风险；
        要创建需要等待所有排队任务完成的代码，首选的技术是使用join()方法；
        '''
    def full(self):
        '''Return True if the queue is full, False otherwise (not reliable!).
        This method is likely to be removed at some point.  Use qsize() >= n
        as a direct substitute, but be aware that either approach risks a race
        condition where a queue can shrink before the result of full() or
        qsize() can be used.
        '''
        with self.mutex:
            return 0 < self.maxsize <= self._qsize()
        '''
        如果队列已满，返回True，否则返回False（不可靠！）；
        这种方法很可能在某个时候被删除。并由qsize() >= n来替代，但是要注意，不管是使用full()还是qsize()，都有可能会在队列产生风险；
        '''
    def put(self, item, block=True, timeout=None):
        '''Put an item into the queue.
        If optional args 'block' is true and 'timeout' is None (the default),
        block if necessary until a free slot is available. If 'timeout' is
        a non-negative number, it blocks at most 'timeout' seconds and raises
        the Full exception if no free slot was available within that time.
        Otherwise ('block' is false), put an item on the queue if a free slot
        is immediately available, else raise the Full exception ('timeout'
        is ignored in that case).
        '''
        with self.not_full:
            if self.maxsize > 0:
                if not block:
                    if self._qsize() >= self.maxsize:
                        raise Full
                elif timeout is None:
                    while self._qsize() >= self.maxsize:
                        self.not_full.wait()
                elif timeout < 0:
                    raise ValueError("'timeout' must be a non-negative number")
                else:
                    endtime = time() + timeout
                    while self._qsize() >= self.maxsize:
                        remaining = endtime - time()
                        if remaining <= 0.0:
                            raise Full
                        self.not_full.wait(remaining)
            self._put(item)
            self.unfinished_tasks += 1
            self.not_empty.notify()
        '''
        将项目放入队列；
        如果可选的参数block为true，并且参数timeout为None（默认值）时，则表示队列需直到空闲时才可用；
        如果参数timeout为一个非负数，则表示它最多阻塞“超时”多少秒，并且如果在那个时间内队列没有空余槽，则引发Full异常；
        而当参数block为false时，则队列有空余槽时，就立即向项目放入队列中，否则引发Full异常（这种情况下，参数timeout不起作用）
        '''
    def get(self, block=True, timeout=None):
        '''Remove and return an item from the queue.
        If optional args 'block' is true and 'timeout' is None (the default),
        block if necessary until an item is available. If 'timeout' is
        a non-negative number, it blocks at most 'timeout' seconds and raises
        the Empty exception if no item was available within that time.
        Otherwise ('block' is false), return an item if one is immediately
        available, else raise the Empty exception ('timeout' is ignored
        in that case).
        '''
        with self.not_empty:
            if not block:
                if not self._qsize():
                    raise Empty
            elif timeout is None:
                while not self._qsize():
                    self.not_empty.wait()
            elif timeout < 0:
                raise ValueError("'timeout' must be a non-negative number")
            else:
                endtime = time() + timeout
                while not self._qsize():
                    remaining = endtime - time()
                    if remaining <= 0.0:
                        raise Empty
                    self.not_empty.wait(remaining)
            item = self._get()
            self.not_full.notify()
            return item
        '''
        从队列中删除并返回项目；
        如果可选的参数block为true，并且参数timeout为None（默认值）时，则表示队列需直到有项目时才可用；
        如果参数timeout为一个非负数，则表示它最多阻塞“超时”多少秒，并且如果在那个时间内没有可用的项目，则引发Empty异常；
        而当参数block为false时，则项目可用就立即返回结果，否则引发Empty异常（这种情况下，参数timeout不起作用）
        '''
    def put_nowait(self, item):
        '''Put an item into the queue without blocking.
        Only enqueue the item if a free slot is immediately available.
        Otherwise raise the Full exception.
        '''
        return self.put(item, block=False)
        '''
        没有阻塞时将项目放入队列；
        只有当队列有空余槽时，才将项目入列；
        否则引发Full异常；
        '''
    def get_nowait(self):
        '''Remove and return an item from the queue without blocking.
        Only get an item if one is immediately available. Otherwise
        raise the Empty exception.
        '''
        return self.get(block=False)
        '''
        没有阻塞时，从队列中删除并返回项目；
        只有当队列有可用项目时，才获取项目；
        否则引发Empty异常；
        '''
    # Override these methods to implement other queue organizations
    # (e.g. stack or priority queue).
    # These will only be called with appropriate locks held
    # Initialize the queue representation
    def _init(self, maxsize):
        self.queue = deque()
        '''
        初始化队列；
        '''
    def _qsize(self):
        return len(self.queue)
    # Put a new item in the queue
    def _put(self, item):
        self.queue.append(item)
        '''
        将新项目放入队列；
        '''
    # Get an item from the queue
    def _get(self):
        return self.queue.popleft()
        '''
        从队列中获取项目
        '''