(Nachdruck aus Blog-Artikel)
Eine der wichtigen Datenstrukturen ist Stack and Queue, aber wir werden uns mit dem Problem ihrer Implementierung befassen.
Wie in Dieser Kommentarartikel gezeigt, können Stapel und Warteschlangen jedoch durch Arrays dargestellt werden. Dies ist eine spezielle Datenstruktur. Ist nicht. Der wichtige Unterschied ist die folgende Verwendung.
Extrahieren Sie das zuletzt gepusste Element in der Stapeldatenstruktur Extrahieren Sie das erste Push-Element in der Warteschlangendatenstruktur
Implementieren Sie die Stapelklasse und die Warteschlangenklasse mit den oben genannten Funktionen.
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).
Zunächst aus der Implementierung des Stacks. Wie Sie im Problemtitel sehen können, müssen Sie den Stapel mithilfe der Warteschlange implementieren.
Die Verwendung einer Warteschlange begrenzt die Operationen, die ausgeführt werden können. Push ist auf die Rückseite und Pop auf die Vorderseite beschränkt, da nur Push nach hinten, Peek / Pop von vorne, Größe und leere Operationen gültig sind.
Wenn Sie dies tun, wird der Test auch dann bestanden, wenn Sie die Absicht des Problems ignorieren und den Stapel verwenden. Aber es macht natürlich keinen Sinn, einen Stapel mit Stapel zu erstellen. In Python zeigt die Liste das Verhalten des Stapels.
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
Für dieses Problem müssen Sie den Stapel mithilfe der Warteschlange implementieren, der Punkt ist jedoch Pop. Wiederum ruft der Stapel das zuletzt gepusste Element ab, während die Warteschlange das erste gepusste Element abruft.
In Python können Sie das erste Push-Element mit "queue.popleft ()" abrufen. Die folgende Lösung besteht darin, die Warteschlange mit popleft so zu sortieren, dass das später gepusste Element beim Ausführen von push zuerst angezeigt wird.
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
Es kostet $ O (n) $ für Push und $ O (1) $ für Pop.
Übrigens kann es nicht unter der Anforderung dieses Problems verwendet werden, aber wie im folgenden Artikel beschrieben, gibt es in "collection.deque ()" auch eine "pop" -Methode, und der Zeitberechnungsbetrag beträgt $ O (1) $ von hinten. Es ist möglich, Elemente abzurufen und zu löschen.
[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).
Als nächstes folgt die Implementierung von Queue. Jetzt werden Sie aufgefordert, die Warteschlange mithilfe des Stapels zu implementieren.
Dies schränkt auch die möglichen Operationen ein. Nur nach oben drücken, von oben spähen / platzen, Größe und leer Operationen sind gültig. Mit anderen Worten, für Push, Peek und Pop sind nur "list.append (x)", "list [-1]" und "list.pop ()" zulässig.
Die folgende Lösung besteht darin, zwei Stapel vorzubereiten, sie beim Drücken im inStack zu speichern und einen outStack vorzubereiten, in dem die Elemente des inStacks in umgekehrter Reihenfolge für Peek and Pop gespeichert werden, und die Verarbeitung durchzuführen.
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