Smaller Python数据结构：自己动手实现队列

"""
目标：实现队列，使其具有方法：入队列（push_queue）、出队列（pop_queue）、
取队列首元素（get_top）、取队列尾元素（get_tail）、判断队列是否为空（is_empty）、
获取队列中元素个数（size）
为后面操作打基础
Goal: To implement the queue, there are methods: push queue, pop queue,
 get top, get tail, judge whether the queue is empty, and get the number 
 of elements in the queue
Lay a foundation for later operations
"""

"""
Method One : 数组（列表）实现队列
核心思想：以数组（列表）作为存储队列数据的数据结构，Python里本身
对列表有着丰富的内置操作，比如pop,append,len等等，列表是顺序
存储，并且在Python初始化一个列表时，不一定非要指定列表长度，这
使得Python列表实现起来非常简单和方便。
注意：一般在C、Java中初始化数组(列表)时，是必须声明数组（列表）
长度的，而在Python中，可以不限定，但append添加的效率很明显要比
直接赋值（比如：list[1] = "Python"）的低很多。
问题：用数组实现队列最大的问题就是，当出队列时，front是只向后移的，
所以会浪费前面的空间，对于这个问题，我们可以把数组看成一个环状的空
间，我记得当时我学数据结构的时候是固定数组长度，然后取余来判断数组
队列是否溢出或者该循环了。
Method one: array (list) implementation queue
Core idea: Taking array (list) as the data structure of queue data storage,
 python itself has rich built-in operations on list, such as pop, append, 
 len, etc. list is sequential storage, and when Python initializes a list, 
 it is not necessary to specify the length of list, which makes Python list 
 implementation very simple and convenient.
Note: when initializing arrays (lists) in C and Java, the length of arrays
 (lists) must be declared. In Python, there is no limit, but the efficiency
 of adding append is obviously lower than that of direct assignment (for 
 example: list [1] = "Python").
 Problem: the biggest problem of using array to realize queue
 is that when out of queue, front only moves backward, so it 
 will waste the previous space. For this problem, we can regard 
 array as a circular space. I remember that when I studied data 
 structure, I fixed the length of array, and then took the remainder 
 to judge whether the array queue overflowed or the cycle was over.
"""

class ListQueue:
    def __init__(self):
        self.queue = []
        self.front = 0  # 队列头
        self.rear = 0  # 队列尾
    # 新元素进入队列
    def queue_push(self, x):
        self.queue.append(x)  # 入队列
        self.rear += 1  # 有新数据进队列，尾元素往后一个位置后移一位
        print("********入队列成功********")
    # 删除队头元素
    def queue_pop(self):
        if self.front < self.rear:
            self.front += 1  # 出队列，把队首元素记录位置后移一位
            print("********出队列成功********")
        else:
            print("********队列已空********")
    # 获取队列首元素
    def get_queue_top(self):
        if self.front == self.rear:
            print("********空队列********")
            return None
        else:
            return self.queue[self.front]
    # 获取队列尾元素
    def get_queue_tail(self):
        if self.front == self.rear:
            print("********空队列********")
            return None
        else:
            return self.queue[self.rear - 1]
    # 判断队列是否为空
    def queue_is_empty(self):
        if self.front == self.rear:
            return True
        else:
            return False
    # 队列长度
    def queue_len(self):
        return self.rear - self.front

"""
Method Two : 链表实现队列
核心思想：以链表作为存储队列数据的数据结构，Python里本身
是不含链表这种数据结构的，所以需要我们自己去写对链表的基
本操作，当然在上一章中我们已经非常熟悉链表了，所以操作起
来还是很简单。
注意：Python内置的数据结构里没有链表，我们一般用引用实现
链表这一数据结构，创建一个类LinkNode，包含两个属性，data
为数据域，存放当前结点数据，next为指针域。存放下一个结点的
地址（指针）。
Method two: linked list implementation queue
Core idea: take linked list as the data structure to store queue data.
 Python itself does not contain linked list, so we need to write the
  basic operation of linked list. Of course, in the previous chapter, 
  we are very familiar with linked list, so the operation is very simple.
Note: there is no linked list in Python's built-in data structure. Generally,
 we use reference to implement the linked list data structure. We create a 
 linknode class, which contains two attributes. Data is the data field, which 
 stores the current node data, and next is the pointer field. Store the 
 address (pointer) of the next node.
"""

class LinkNode:
    def __init__(self, x):
        self.data = x  # 数据域
        self.next = None  # 指针域
class LinkQueue:
    def __init__(self):
        self.pHead = None  # 队列头指针
        self.pEnd = None  # 队列尾指针
    # 入队列
    def queue_push(self, x):
        node = LinkNode(x)  # 新建一个结点
        if not self.pHead:  # 第一次有元素入队列
            self.pHead = node
            self.pEnd = node
        else:
            self.pEnd.next = node  # 添加队列末尾
            self.pEnd = node  # 尾指针后移
        print("********入队列成功********")
    # 出队列
    def queue_pop(self):
        if self.pHead:
            self.pHead = self.pHead.next
            print("********出队列成功********")
        else:
            print("********队列已空********")
    # 获取队列顶元素
    def get_queue_top(self):
        if not self.pHead:
            print("********空队列********")
            return None
        else:
            return self.pHead.data
    # 判断队列是否为空
    def queue_is_empty(self):
        if not self.pHead:
            return True
        else:
            return False
    # 获取队列尾元素
    def get_queue_tail(self):
        if not self.pHead:
            print("********空队列********")
            return None
        else:
            return self.pEnd.data
    # 队列长度
    def queue_len(self):
        link_len = 0
        cur_node = self.pHead
        while cur_node:  # 遍历计算链表长，即队列长
            cur_node = cur_node.next
            link_len = link_len + 1
        return link_len

# 当然，也许还有别的方法，比如建一个辅助的链表
# 欢迎你说出你的想法
# 程序入口，测试函数功能
if __name__ == "__main__":
    # 初始化一个队列
    # my_queue = ListQueue()  # 列表队列测试
    my_queue = LinkQueue()  # 链表队列测试
    # 入队列
    my_queue.queue_push(1)
    my_queue.queue_push(2)
    my_queue.queue_push(4)
    # 获取队列顶
    print("当前队列顶为：", my_queue.get_queue_top())
    # 获取队列尾
    print("当前队列尾为：", my_queue.get_queue_tail())
    # 出队列
    my_queue.queue_pop()
    # 判断队列是否为空
    if my_queue.queue_is_empty():
        print("********队列已空********")
    else:
        print("********队列没空********")
    # 队列长
    print("队列长为：", my_queue.queue_len())
    # 出队列
    my_queue.queue_pop()
    my_queue.queue_pop()
    # 判断队列是否为空
    if my_queue.queue_is_empty():
        print("********队列已空********")
    else:
        print("********队列没空********")