[ Python 常見問題 ] Python Datatype for a fixed-length FIFO

Source From Here
Question
I would like to know if there is a native datatype in Python that acts like a fixed-length FIFO buffer. For example, I want do create a length-5 FIFO buffer that is initialized with all zeros. Then, it might look like this:

[0,0,0,0,0]

Then, when I call the put function on the object, it will shift off the last zero and put the new value, say 1, into the left side:

[1,0,0,0,0] // The right most 0 is being removed

If I put a 2, it would then shift and put to look like this:

[2,1,0,0,0] // The right most 0 is being removed

...and so on. The new value goes at the front and the oldest one is shifted off. I understand that this would be very easy to implement myself, but I would like to use native python datatypes if at all possible. Does anyone know which datatype would be best for this?

How-To
See the docs for more about collections.deque; the method you call push is actually called appendleft in that type:

>>> import collections
>>> x = collections.deque(range(5), 5) // Create a queue with max size 5
>>> x
deque([0, 1, 2, 3, 4], maxlen=5)
>>> x.appendleft(6) // Similar to operation push of queue
>>> x
deque([6, 0, 1, 2, 3], maxlen=5)
>>> x[-1] // Get the last element without removing it
3
>>> x.pop() // Remove the last element
3
>>> x
deque([6, 0, 1, 2], maxlen=5)
>>> x.append(7) // Add the element to the end
>>> x
deque([6, 0, 1, 2, 7], maxlen=5)

Note. The second parameter (maxlen, giving the maximum lengths) was added in Python 2.6; if you're using older versions of Python, it won't be available.

One simple implementation as below in case your Python version doesn't support above approach:

view plaincopy to clipboardprint?

1. class FQueue(object):  
2.     def __init__(self, l=2):  
3.         self.l = l  
4.         self.data = []  
5.   
6.     def put(self, v):  
7.         r'''  
8.         Put element into queue  
9.         '''  
10.         ov = v  
11.         if len(self.data) >= self.l:  
12.             ov = self.data.pop(0)  
13.         self.data.append(v)  
14.         return self  
15.   
16.     def push(self, v):  
17.         return self.put(v)  
18.   
19.     def add(self, v):  
20.         return self.put(v)  
21.   
22.     def pop(self):  
23.         if len(self.data) > 0:  
24.             return self.data.pop(0)  
25.         else:  
26.             return None  
27.   
28.     def clear(self):  
29.         r'''  
30.         Remove all element(s)  
31.         '''  
32.         self.data.clear()  
33.   
34.     def size(self):  
35.         r'''  
36.         Return the size of queue  
37.         '''  
38.         return len(self.data)  
39.   
40.     def full(self):  
41.         r'''  
42.         Return True if the queue is full  
43.         '''  
44.         return len(self.data) >= self.l  
45.   
46.     def tstr(self, sep='_'):  
47.         r'''  
48.         Return the string representation  
49.         '''  
50.         data = [str(e) for e in self.data]  
51.         return sep.join(data)  
52.   
53.     def __str__(self):  
54.         return self.tstr()  
55.   
56.     def __repr__(self):  
57.         return self.tstr()  

Demonstration:

>>> q = FQueue(5)
>>> for i in range(10):
... print("%s" % q.push(i))
...
0
0_1
0_1_2
0_1_2_3
0_1_2_3_4
1_2_3_4_5
2_3_4_5_6
3_4_5_6_7
4_5_6_7_8
5_6_7_8_9