Shulou(Shulou.com)06/01 Report--

This article mainly shows you "what are the exercises of the Python queue", which is easy to understand and well organized. I hope it can help you solve your doubts. Let the editor lead you to study and learn this article "what are the exercises of the Python queue?"

1. Use two stacks to implement a queue

[problem] given two stacks, only one queue is implemented using the basic operation of the stack.

[idea] the key to solving this problem lies in the reversal characteristic of the stack. A series of elements that enter the stack will return in the opposite order when going out of the stack. Therefore, using two stacks, elements can be returned in the same order (the original order is obtained when the inverted sequence of elements is reversed again). The specific operation is shown in the following figure:

[algorithm]

  joins the team enqueue:

    pushes elements onto the stack stack_1

  out of the team dequeue:

    if the stack stack_2 is not empty:

Elements at the top of the   stack_2 stack are unstacked

    otherwise:

  ejects all elements from stack_1 and presses them into stack_2 in turn

Elements at the top of the   stack_2 stack are unstacked

[code]

Class Queue: def _ init__ (self): self.stack_1 = Stack () self.stack_2 = Stack () def enqueue (self Data): self.stack_1.push (data) def dequeue (self): if self.stack_2.isempty (): while not self.stack_1.isempty (): self.stack_2.push (self.stack_1.pop ()) return self.stack_2.pop ()

[space-time complexity] the time complexity of joining the queue is O (1). If the stack stack_2 is not empty, then the time complexity of dequeuing is O (1). If the stack stack_2 is empty, then elements need to be transferred from stack_1 to stack_2. But because the number of elements transferred in stack_2 is equal to the number of elements out of the queue, the amortization time complexity of dequeuing is O (1).

two。 Use two queues to implement a stack

[question] given two queues, only one stack is implemented using the basic operation of the queue.

[idea] because the queue does not have the characteristic of reversing the order, the entry order is the out-of-queue order of the elements. So if you want to get the last element in the queue, you need to get all the previous elements out of the team first. So in order to use two queues to implement the stack, we need to use one queue store_queue to store elements and the other queue temp_queue to hold elements that are temporarily dequeued to get the last element. The push operation queues the given element to the storage queue store_queue; the pop operation first transfers all but the last element in the storage queue store_queue to the temporary queue temp_queue, and then stores the last element in the queue store_queue to dequeue and return. The specific operation is shown in the following figure:

[algorithm]

The running process of the   algorithm needs to always keep one of the queues empty and use it as a temporary queue.

  Stack push: inserts the element data in a non-empty queue.

    if the queue queue_1 is empty:

  inserts data into queue queue_2

    otherwise:

  inserts data into queue queue_1

  unstack pop: insert the first n − 1 element in the queue into another queue, delete and return the last element

    if the queue queue_1 is not empty:

  inserts the first n − 1 element of queue queue_1 into queue_2, and then the last element of queue_1 leaves the queue and returns

    if the queue queue_2 is not empty:

  inserts the first n − 1 element of queue queue_2 into queue_1, and then the last element of queue_2 leaves the queue and returns

[code]

Class Stack: def _ _ init__ (self): self.queue_1 = Queue () self.queue_2 = Queue () def isempty (self): return self.queue_1.isempty () and self.queue_2.isempty () def push (self Data): if self.queue_2.isempty (): self.queue_1.enqueue (data) else: self.queue_2.enqueue (data) def pop (self): if self.isempty (): raise IndexError ("Stack isempty") elif self.queue_2.isempty (): while not self.queue_1.isempty (): P = self.queue_1.dequeue () if self.queue_1.isempty (): return p self.queue_2.enqueue (p) else: while not self.queue_2.isempty (): P = self.queue_2.dequeue () If self.queue_2.isempty (): return p self.queue_1.enqueue (p)

[spatio-temporal complexity] the time complexity of push operation is O (1). Because all elements need to be transferred from one queue to another in pop operation, the time complexity is O (n).

3. Judgment of element continuity in stack

[problem] given a stack stack1, the elements in the stack are all integers, and determine whether each pair of consecutive numbers in the stack is a continuous integer (if there are odd elements in the stack, the elements at the top of the stack are excluded). For example, the input stack [1, 2, 5, 6,-5,-4, 11, 10, 55] is entered as True, because after excluding element 55 at the top of the stack, (1, 2), (5, 6), (- 5,-4), (11, 10) are all consecutive integers.

[idea] because there may be odd elements in the stack, in order to judge correctly, it is necessary to reverse the elements in the stack for the first time, change the elements at the top of the stack into the bottom of the stack, and then go out of the stack in turn to make a judgment.

[algorithm]

All the elements in the   stack stack are removed from the stack in turn and inserted into the queue queue

All elements in the   queue queue dequeue and enter the stack stack

  while stack stack is not empty:

The top element E1 of the     stack is removed from the stack and inserted into the queue queue

    if the stack stack is not empty:

The element e2 at the top of the   stack is removed from the stack and inserted into the queue queue

  if | e1-e2 |! = 1:

  returns False and jumps out of the loop

All elements in the   queue queue dequeue and enter the stack stack

[code]

Def check_stack_pair (stack): queue = Queue () flag = True # reverses the element while not stack.isempty (): queue.enqueue (stack.pop ()) while not queue.isempty (): stack.push (queue.dequeue ()) while not stack.isempty (): E1 = stack.pop () queue.enqueue (E1) if not stack.isempty (): e2 = stack.pop () queue.enqueue (e2) if abs (e1-e2)! = 1: flag = False break while not queue.isempty (): stack.push (queue.dequeue ()) return flag

[space-time complexity] time complexity is O (n), space complexity is O (n).

4. Rearrange the order of elements in the queue

[problem] given an integer queue queue, rearrange elements by interleaving the first half of the queue with the second half of the queue. For example, if the input team is listed as [1, 2, 3, 4, 5, 6, 7, 8, 9], the output should be [1, 6, 2, 7, 3, 8, 4, 9, 5].

[idea] by getting the first half of the queue, and then making use of the reversal feature of the stack, you can rearrange the queue, as shown in the following figure:

[algorithm]

  if the number of elements in queue queue is even:

    half=queue.size//2

  otherwise:

    half=queue.size//2+1

1. The first half of the queue queue elements are sequentially dequeued and added to the stack stack.

two。 Elements in stack stack are taken out of stack and merged into team queue

3. Dequeue another part of the queue queue that was not out of line in step 1 and insert it at the end of the queue.

4. The first half of the queue queue elements are sequentially dequeued and added to the stack stack.

5. Alternately eject the elements in the stack stack and queue queue and join the queue

6. If the stack stack is not empty:

The elements in the     stack stack are added to the queue.

[code]

Def queue_order (queue): stack = Stack () size = queue.size if size% 2 = = 0: half = queue.size//2 else: half = queue.size//2 + 1 res = queue.size-half for i in range (half): stack.push (queue.dequeue ()) while not stack.isempty (): queue.enqueue (stack.pop () for i in range (res): queue.enqueue (queue.dequeue () for i in range (half): stack.push (queue.dequeue ()) for i in range (res): queue.enqueue (stack.pop ()) queue.enqueue (queue.dequeue ()) if not stack.isempty (): queue.enqueue (stack.pop ())

[space-time complexity] time complexity is O (n), space complexity is O (n).

5. Reverse the order of the first m elements in the queue

[problem] given an integer m and an integer queue queue, the order of the first k elements in the queue is reversed, while the other elements remain unchanged. For example, the team is listed as [1, 2, 3, 4, 5, 6, 7, 8, 9], and the algorithm output is [5, 4, 3, 2, 1, 6, 7, 8, 9].

[idea] combined with [question 4], we can find that this question is the first three steps of [question 4], as shown in the following figure:

[algorithm]

1. The first m elements of the queue queue are sequentially dequeued and added to the stack stack

two。 Elements in stack stack are taken out of stack and merged into team queue

3. Dequeue another part of the queue queue that was not out of line in step 1 and insert it at the end of the queue.

[code]

Def reverse_m_element (queue, m): stack = Stack () size = queue.size if queue.isempty () or m > size: return for i in range (m): stack.push (queue.dequeue ()) while not stack.isempty (): queue.enqueue (stack.pop ()) for i in range (size-m): queue.enqueue (queue.dequeue ())

[space-time complexity] time complexity is O (n), space complexity is O (n).

The above is all the contents of the article "what are the exercises for the Python queue?" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.