The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 38 Common Composite Data Types in Python – Implementing stack, Queue and Deque with Lists
In Python, a list is a highly flexible data structure that can be used to implement stack, queue and deque. Although these data structures follow different operation rules in use, all of them can be efficiently implemented via Python lists.
This document mainly introduces how to use Python for Object Oriented programming, which requires readers to have a basic understanding of Python syntax and microcontroller development. Compared with other blogs or books that explain Python Object Oriented programming, this document is more detailed and focuses on embedded host computer applications, taking the common serial port data transmission and reception, data processing, dynamic graph drawing and other functions between the host computer and the slave computer as application examples. Meanwhile, it uses the Sourcetrail code software to visualize the code for reading to facilitate readers' understanding.
The link to obtain the relevant sample code is as follows:
https://github.com/leezisheng/Python-OOP-Demo
Body Text
Implement a stack using a list
List methods make it very convenient to use a list as a stack, which is a specific data structure, where the first element added is the last one to be retrieved (last-in, first-out). You can add an element to the top of the stack using the append () method, and remove an element from the top of the stack using the pop () method without specifying an index.
You can also use a list as a queue, where the first element added to the queue is the first one to be retrieved; however, using a list for this purpose is not efficient. Adding or popping elements at the end of a list is fast, but inserting elements into the list or popping from the front is not fast (since all other elements have to be shifted one by one). The sample code is as follows:
class Queue(object):
'''
Implement a queue using a list
'''
def __init__(self):
'''
Initialization
'''
self.__list = []
def enqueue(self, item):
'''
Add an element to the queue
'''
self.__list.append(item)
def dequeue(self):
'''
Take an element from the head of the queue
'''
return self.__list.pop(0)
def is_empty(self):
'''
Check whether the list is empty
'''
return self.__list == []
def size(self):
'''
Return the size of the list
'''
return len(self.__list)
s = Queue()
s.enqueue(1)
s.enqueue(2)
s.enqueue(3)
s.enqueue(4)
print(s.__dict__)
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
print(s.dequeue())
The running results are as follows:
Implement a deque using a list
A deque (short for double-ended queue) is a data structure that exhibits properties of both queues and stacks. Elements in a deque can be popped from either end, and its insertion and deletion operations are restricted to the two ends of the linear structure. A deque allows elements to be enqueued and dequeued at either end of the queue.
Sample code for implementing a deque using a list is as follows:
class Deque(object):
'''
Double-ended queue
'''
def __init__(self):
'''
Initialize the list
'''
self.__list = []
def add_front(self, item):
'''
Add an element to the head of the queue
'''
self.__list.insert(0, item)
def add_rear(self, item):
'''
Add an element to the tail of the queue
'''
self.__list.append(item)
def pop_front(self):
'''
Delete an element from the head of the queue
'''
return self.__list.pop(0)
def pop_rear(self):
'''
Delete an element from the head of the queue
'''
return self.__list.pop()
def is_empty(self):
'''
Check whether the list is empty
'''
return self.__list == []
def size(self):
'''
Return the size of the list
'''
return len(self.__list)