详解python循环队列和链队列

209 阅读 0 评论 138 点赞

我是靠谱客的博主友好泥猴桃，这篇文章主要介绍详解python循环队列和链队列，现在分享给大家，希望可以做个参考。

1.循环队列：实际上为顺序表，把它认为是循环结构。如下图所示，初始时，first与rear两个指针指向同一块空间，当入队时，从first指向的位置插入值，然后rear指针后移，设M表示队列的长度，则rear=(rear+1)%M,判断队列是否已满：(rear+1)%M==first.此时，rear指向空的一块空间，这时认为队列已满，留出一块空的空间为了与队列为空时做区分；当出队时，从队首出队（即从first指针指向的空间出队），然后first指针后移，first指针每次指向队列中存在的第一个元素，而rear每次指向队尾元素的后一个空间，first指针的移动遵从first=(first+1)%M.判断队列是否为空：first==rear.

复制代码

#循环队列
class Queue():
    
    #maxvalue表示最大存储空间
    def __init__(self,maxvalue):
        self.maxvalue = maxvalue
        self.queuelist = [None]*self.maxvalue
        #first与rear都指向下标0
        self.first = 0
        self.rear = 0
   
    #入队
    def enqueue(self,data):
        #判断队满
        if (self.rear+1)%self.maxvalue == self.first:
            print("已队满")
        else:
            self.queuelist[self.rear] = data
            self.rear = (self.rear+1)%self.maxvalue
    
    #出队
    def dequeue(self):
        #判断队空
        if self.first == self.rear:
            print("已队空")
        else:
            data = self.queuelist[self.first]
            self.queuelist[self.first] = None
            self.first = (self.first+1)%self.maxvalue
            return data
    
    #遍历队列
    def travel(self):
        #q为下标
        q = self.first
        #当队列不为空时
        if not self.first==self.rear:
            while q!=self.rear:
                print(self.queuelist[q],end=",")
                q = (q+1)%self.maxvalue
        else:
            return None
   
    #求队列中元素的个数
    def length(self):
        if self.first == self.rear:
            return None
        else:
            return (self.rear-self.first+self.maxvalue)%self.maxvalue

if __name__ == "__main__":
    queue = Queue(6)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.enqueue(40)
    queue.enqueue(50)
    
    print(queue.dequeue(),end=",")
    print(queue.dequeue())
    
    queue.travel()
    print(queue.length())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#循环队列
class Queue():
    
    #maxvalue表示最大存储空间
    def __init__(self,maxvalue):
        self.maxvalue = maxvalue
        self.queuelist = [None]*self.maxvalue
        #first与rear都指向下标0
        self.first = 0
        self.rear = 0
   
    #入队
    def enqueue(self,data):
        #判断队满
        if (self.rear+1)%self.maxvalue == self.first:
            print("已队满")
        else:
            self.queuelist[self.rear] = data
            self.rear = (self.rear+1)%self.maxvalue
    
    #出队
    def dequeue(self):
        #判断队空
        if self.first == self.rear:
            print("已队空")
        else:
            data = self.queuelist[self.first]
            self.queuelist[self.first] = None
            self.first = (self.first+1)%self.maxvalue
            return data
    
    #遍历队列
    def travel(self):
        #q为下标
        q = self.first
        #当队列不为空时
        if not self.first==self.rear:
            while q!=self.rear:
                print(self.queuelist[q],end=",")
                q = (q+1)%self.maxvalue
        else:
            return None
   
    #求队列中元素的个数
    def length(self):
        if self.first == self.rear:
            return None
        else:
            return (self.rear-self.first+self.maxvalue)%self.maxvalue

    
if __name__ == "__main__":
    queue = Queue(6)
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.enqueue(40)
    queue.enqueue(50)
    
    print(queue.dequeue(),end=",")
    print(queue.dequeue())
    
    queue.travel()
    print(queue.length())

输出：

2.链队列：实际上为一个单链表，只是头指针head改成了包含两部分（first和rear），first指针指向头结点，rear指针指向尾结点。之所以在头指针位置多加了一个rear指针，是为了方便在链表尾部添加结点，时间复杂度为 $Oleft ( 1 right )$ ；如果不加rear,那么每次在尾部添加结点时需要遍历链表，时间复杂度为 $Oleft ( n right )$ 。注意：入队时需要判断队是否为空；出队时需要判断队是否为空以及队中是否只有一个结点。

复制代码

#链队列
#头指针
class Headnode():
    def __init__(self):
        self.first = None
        self.rear = None

#数据结点
class Datanode():
    def __init__(self,data):
        self.data = data
        self.next = None

class LinkQueue():
    def __init__(self):
        self._head = Headnode()
    
    #判断队列是否为空
    def is_empty(self):
        return self._head.first == None
    
    #入队
    def enqueue(self,data):
        #构建数据结点
        s = Datanode(data)
        #当队列为空时
        if self.is_empty():
            self._head.first = s
            self._head.rear = s
        else:
            self._head.rear.next = s
            self._head.rear = s
    
    #出队
    def dequeue(self):
        #当队列为空时
        if self.is_empty():
            return None    
        else:
            data = self._head.first
            #当队列中只有一个数据结点时
            if self._head.first == self._head.rear:            
                self._head.first = None
                self._head.rear = None
            else:
                #出队时只能从头结点删除               
                self._head.first = self._head.first.next
        return data
    
if __name__=="__main__":
    queue = LinkQueue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.enqueue(40)
    #出队
    while not queue.is_empty():
        p = queue.dequeue()
        print(p.data，end=",")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#链队列
#头指针
class Headnode():
    def __init__(self):
        self.first = None
        self.rear = None

#数据结点
class Datanode():
    def __init__(self,data):
        self.data = data
        self.next = None

class LinkQueue():
    def __init__(self):
        self._head = Headnode()
    
    #判断队列是否为空
    def is_empty(self):
        return self._head.first == None
    
    #入队
    def enqueue(self,data):
        #构建数据结点
        s = Datanode(data)
        #当队列为空时
        if self.is_empty():
            self._head.first = s
            self._head.rear = s
        else:
            self._head.rear.next = s
            self._head.rear = s
    
    #出队
    def dequeue(self):
        #当队列为空时
        if self.is_empty():
            return None    
        else:
            data = self._head.first
            #当队列中只有一个数据结点时
            if self._head.first == self._head.rear:            
                self._head.first = None
                self._head.rear = None
            else:
                #出队时只能从头结点删除               
                self._head.first = self._head.first.next
        return data
    
if __name__=="__main__":
    queue = LinkQueue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    queue.enqueue(40)
    #出队
    while not queue.is_empty():
        p = queue.dequeue()
        print(p.data，end=",")