Queue and Stack are common data structures that are widely used in computer science. The stack is a Last-In-First-Out (LIFO) data structure, while the queue is a First-In-First-Out (FIFO) data structure. Generally, queue operations include enqueue and dequeue operations, while stack operations include push and pop operations.
In Python, you can use a list to implement a stack, but using a stack to implement a queue requires some clever operations.
Basic operations of queues
Queues have two basic operations: enqueue and dequeue. The enqueue operation adds an element to the end of the queue, while the dequeue operation removes the first element from the queue and returns it.
Enqueue operation
The enqueue operation adds an element to the end of the queue. In Python, you can use the append() method to implement the enqueuing operation.
queue = [] queue.append(1) #Enqueue element 1 queue.append(2) #Enqueue element 2
At this time, the elements in the queue are [1, 2], with 1 at the front of the queue and 2 at the back of the queue.
Dequeue operation
The dequeue operation removes the first element from the queue and returns it. In Python, you can use the pop(0) method to implement the dequeue operation.
if queue:
front_element = queue.pop(0) # Dequeue
print("Dequeue element:", front_element)
else:
print("Queue is empty")
This removes the first element from the queue and returns that element’s value. If the queue is empty, exceptions need to be handled.
Use stack to implement queue
To implement a queue using stacks, two stacks are required: one for enqueuing operations and one for dequeuing operations. We will call these two stacks the enqueue stack and the dequeue stack.
Enqueue stack
The enqueuing stack is used to perform enqueuing operations. When we want to enqueue an element, we push the element onto the enqueuing stack.
enqueue_stack = [] enqueue_stack.append(1) #Enqueue element 1 enqueue_stack.append(2) #Enqueue element 2
At this time, the elements in the queued stack are [1, 2], with 1 at the bottom of the stack and 2 at the top of the stack.
Dequeue stack
The dequeue stack is used to perform dequeue operations. When an element is to be dequeued, first check whether the dequeuing stack is empty. If the dequeue stack is empty, all elements of the enqueue stack will be popped out of the stack and pushed into the dequeue stack in order to perform the dequeue operation.
dequeue_stack = []
if not dequeue_stack:
while enqueue_stack:
element = enqueue_stack.pop()
dequeue_stack.append(element)
#The elements in the dequeue stack are [2, 1]
Now, perform the dequeue operation from the dequeue stack and return the first element of the queue.
if dequeue_stack:
front_element = dequeue_stack.pop() # Dequeue
print("Dequeue element:", front_element)
else:
print("Queue is empty")
Complete queue implementation
Here is the complete code to implement a queue using two stacks:
class QueueUsingStack:
def __init__(self):
self.enqueue_stack = [] #Enqueue stack
self.dequeue_stack = [] # Dequeue stack
def enqueue(self, element):
self.enqueue_stack.append(element)
def dequeue(self):
if not self.dequeue_stack:
while self.enqueue_stack:
element = self.enqueue_stack.pop()
self.dequeue_stack.append(element)
if self.dequeue_stack:
return self.dequeue_stack.pop()
else:
return None
#Create queue
my_queue = QueueUsingStack()
# Join the queue operation
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
# Dequeue operation
print(my_queue.dequeue()) # Dequeue element: 1
print(my_queue.dequeue()) # Dequeue elements: 2
print(my_queue.dequeue()) # Dequeue elements: 3
print(my_queue.dequeue()) # The queue is empty
This queue uses two stacks to implement queue enqueue and dequeue operations, which can effectively simulate the behavior of the queue.
Using a stack to implement a queue is a fun programming exercise that shows how basic data structures can be used to build more complex data structures. In actual programming, Python’s queue module is usually used to implement queues because it provides more functions and thread-safe operations.
———————————END——————- ——–
Digression
Thank you for watching until the end, I have prepared some benefits for everyone!
Interested friends will receive a complete set of Python learning materials, including interview questions, resume information, etc. See below for details.
CSDN gift package:The most complete “Python learning materials” on the Internet are given away for free! (Safe link, click with confidence)
1. Python learning routes in all directions
The technical points in all directions of Python have been compiled to form a summary of knowledge points in various fields. Its usefulness is that you can find corresponding learning resources according to the following knowledge points to ensure that you learn more comprehensively.
2. Essential development tools for Python
The tools have been organized for you, and you can get started directly after installation! 
3. Latest Python study notes
When I learn a certain basic and have my own understanding ability, I will read some books or handwritten notes compiled by my seniors. These notes record their understanding of some technical points in detail. These understandings are relatively unique and can be learned. to a different way of thinking.
4. Python video collection
Watch a comprehensive zero-based learning video. Watching videos is the fastest and most effective way to learn. It is easy to get started by following the teacher’s ideas in the video, from basic to in-depth.
5. Practical cases
What you learn on paper is ultimately shallow. You must learn to type along with the video and practice it in order to apply what you have learned into practice. At this time, you can learn from some practical cases.
6. Interview Guide
Resume template
CSDN gift package:The most complete “Python learning materials” on the Internet are given away for free! (Safe link, click with confidence)
If there is any infringement, please contact us for deletion.