首页 > itarticle > stack,queue and linked list

stack,queue and linked list

admin 11月 13, 2020 0

Stack

A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top.” The end opposite the top is known as the “base.”

The base of the stack is significant since items stored in the stack that are closer to the base represent those that have been in the stack the longest. The most recently added item is the one that is in position to be removed first. This ordering principle is sometimes called LIFO, last-in first-out. It provides an ordering based on length of time in the collection. Newer items are near the top, while older items are near the base.

1
2
3
4
5
6
7
8
9
10
11
12
 
def (nums):
    result=[]
    while nums!=0:
        result.insert(len(result)+1,nums%2)
        nums=nums//2
    binString = ""
    while len(result)>0:
        binString = binString + str(result.pop())
   
    return int(binString)
print(Dec_to_Bin(99))
print(Dec_to_Bin(37))
 
1100011
100101

Queue

A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front.” As an element enters the queue it starts at the rear and makes its way toward the front, waiting until that time when it is the next element to be removed.

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO, first-in first-out. It is also known as “first-come first-served.”

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
import random
class Queue():
    def __init__(self):
        self.list=[]
    def enqueue(self,name):
        self.list.insert(0,name)
    def dequeue(self):
        return self.list.pop()
    def size(self):
        return len(self.list)
    def judge(self):
        if len(self.list)>0:
            return True
        else:
            return False
        
class Task:
    def __init__(self,time):
        self.timestamp = time
        self.pages = random.randrange(1,21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages

    def waitTime(self, currenttime):
        return currenttime - self.timestamp
    
class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        if self.currentTask != None:
            self.timeRemaining = self.timeRemaining - 1
            if self.timeRemaining <= 0:
                self.currentTask = None

    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False

    def startNext(self,newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages() * 60/self.pagerate

def newPrintTask():
    num = random.randrange(1,181)
    if num == 180:
        return True
    else:
        return False
for i in range(20):
        pagesPerMinute=7
        labprinter = Printer(pagesPerMinute)
        printQueue = Queue()
        waitingtimes = []

        for currentSecond in range(7200):

              if newPrintTask():
                     task = Task(currentSecond)
                     printQueue.enqueue(task)

              if (not labprinter.busy()) and (printQueue.judge()):
                    nexttask = printQueue.dequeue()
                    waitingtimes.append( nexttask.waitTime(currentSecond))
                    labprinter.startNext(nexttask)

              labprinter.tick()

        averageWait=sum(waitingtimes)/len(waitingtimes)
        print("Average Wait %6.2f secs %3d tasks remaining."%(averageWait,printQueue.size()))
 
Average Wait  59.57 secs   0 tasks remaining.
Average Wait  65.32 secs   0 tasks remaining.
Average Wait  33.77 secs   0 tasks remaining.
Average Wait  45.81 secs   0 tasks remaining.
Average Wait  16.58 secs   0 tasks remaining.
Average Wait  46.65 secs   0 tasks remaining.
Average Wait 132.59 secs   1 tasks remaining.
Average Wait  36.56 secs   0 tasks remaining.
Average Wait  65.07 secs   0 tasks remaining.
Average Wait  66.28 secs   0 tasks remaining.
Average Wait  31.38 secs   1 tasks remaining.
Average Wait  71.24 secs   0 tasks remaining.
Average Wait  28.50 secs   0 tasks remaining.
Average Wait  29.76 secs   0 tasks remaining.
Average Wait  27.44 secs   0 tasks remaining.
Average Wait  16.71 secs   0 tasks remaining.
Average Wait  21.87 secs   0 tasks remaining.
Average Wait  36.16 secs   0 tasks remaining.
Average Wait  25.22 secs   0 tasks remaining.
Average Wait  69.79 secs   0 tasks remaining.
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能