(Réimprimé de Article de blog)
L'une des structures de données importantes est Stack et Queue, mais nous aborderons le problème de leur mise en œuvre.
Cependant, comme indiqué dans Cet article de commentaire, les piles et les files d'attente peuvent être représentées par des tableaux, qui sont une structure de données spéciale. N'est pas. La différence importante est l'utilisation suivante.
Extraire le dernier élément poussé dans la structure de données de la pile Extraire le premier élément poussé dans la structure de données de la file d'attente
Implémentez la classe Stack et la classe Queue avec les fonctions ci-dessus.
Implement Stack using Queues
[https://leetcode.com/problems/implement-stack-using-queues/]
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.
Example:
MyStack stack = new MyStack();
stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
Tout d'abord, de la mise en œuvre de stack. Comme vous pouvez le voir dans le titre du problème, vous devez implémenter la pile à l'aide de la file d'attente.
L'utilisation d'une file d'attente limite les opérations pouvant être effectuées. Le push est limité à l'arrière et le pop est limité à l'avant, car seules les opérations push to back, peek / pop de l'avant, taille et vide sont valides.
Si vous le faites, le test réussira même si vous ignorez l'intention du problème et utilisez stack. Mais, bien sûr, il ne sert à rien de créer une pile en utilisant stack. En python, la liste montre le comportement de la pile.
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.stack.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.stack.pop()
def top(self) -> int:
"""
Get the top element.
"""
return self.stack[-1]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.stack) == 0
Ce problème vous oblige à implémenter la pile à l'aide de la file d'attente, mais le point est pop. Là encore, stack récupère le dernier élément poussé, tandis que queue récupère le premier élément poussé.
En python, vous pouvez récupérer le premier élément poussé avec queue.popleft (). La solution suivante consiste à utiliser popleft pour trier la file d'attente afin que l'élément qui a été poussé plus tard arrive en premier lorsque vous exécutez push.
class MyStack:
def __init__(self):
self.queue = collections.deque()
def push(self, x: int) -> None:
q = self.queue
q.append(x)
for _ in range(len(q)-1):
q.append(q.popleft())
def pop(self) -> int:
return self.queue.popleft()
def top(self) -> int:
return self.queue[0]
def empty(self) -> bool:
return len(self.queue) == 0
Il en coûte $ O (n) $ pour le push et $ O (1) $ pour le pop.
À propos, il ne peut pas être utilisé à la demande de ce problème, mais comme décrit dans l'article suivant, il existe également une méthode pop dans collections.deque (), et le montant du calcul du temps est de $ O (1) $ à l'arrière. Il est possible de récupérer et de supprimer des éléments.
[https://note.nkmk.me/python-collections-deque/:embed:cite]
Implement Queue using Stacks
[https://leetcode.com/problems/implement-queue-using-stacks/]
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
Vient ensuite l'implémentation de Queue. Vous êtes maintenant invité à implémenter la file d'attente à l'aide de stack.
Cela limite également les opérations possibles. seules les opérations push to top, peek / pop from top, size et is empty sont valides. En d'autres termes, pour push, peek et pop, seuls list.append (x), list [-1] et list.pop () sont autorisés.
La solution suivante consiste à préparer deux piles, à les stocker dans l'inStack lors de la poussée, et à préparer un outStack qui stocke les éléments de l'inStack dans l'ordre inverse pour peek et pop, et effectuer le traitement.
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.inStack, self.outStack = [], []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.inStack.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
self.peek()
return self.outStack.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if(self.outStack == []):
while(self.inStack != []):
self.outStack.append(self.inStack.pop())
return self.outStack[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.inStack) == 0 and len(self.outStack) == 0
Recommended Posts