Angenommen, wir haben zwei Stapel und keine andere temporäre Variable.
Ist es möglich, eine Warteschlangen-Datenstruktur nur mit den beiden Stapeln zu "konstruieren"?
Angenommen, wir haben zwei Stapel und keine andere temporäre Variable.
Ist es möglich, eine Warteschlangen-Datenstruktur nur mit den beiden Stapeln zu "konstruieren"?
Zwei Stapel in der Warteschlange sind definiert als Stapel1 y Stapel2 .
Einreihen: Die euqueued-Elemente werden immer in die Stapel1
Aus der Warteschlange: Die Spitze des Stapel2 kann herausgenommen werden, da es das erste in die Warteschlange eingefügte Element ist, wenn Stapel2 nicht leer ist. Wenn Stapel2 leer ist, werden alle Elemente aus Stapel1 und schieben sie in Stapel2 einen nach dem anderen. Das erste Element in einer Warteschlange wird an den unteren Rand von Stapel1 . Es kann direkt nach dem Einschlagen und Drücken herausgezogen werden, da es sich auf der Oberseite des Stapel2 .
Der folgende Code ist ein C++-Beispiel:
template <typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
};
template<typename T> void CQueue<T>::appendTail(const T& element) {
stack1.push(element);
}
template<typename T> T CQueue<T>::deleteHead() {
if(stack2.size()<= 0) {
while(stack1.size()>0) {
T& data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
if(stack2.size() == 0)
throw new exception("queue is empty");
T head = stack2.top();
stack2.pop();
return head;
}
Diese Lösung ist entlehnt aus mein Blog . Eine detailliertere Analyse mit schrittweisen Betriebssimulationen finden Sie auf meiner Blog-Webseite.
Eine Implementierung einer Warteschlange mit zwei Stapeln in Swift:
struct Stack<Element> {
var items = [Element]()
var count : Int {
return items.count
}
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element? {
return items.removeLast()
}
func peek() -> Element? {
return items.last
}
}
struct Queue<Element> {
var inStack = Stack<Element>()
var outStack = Stack<Element>()
mutating func enqueue(_ item: Element) {
inStack.push(item)
}
mutating func dequeue() -> Element? {
fillOutStack()
return outStack.pop()
}
mutating func peek() -> Element? {
fillOutStack()
return outStack.peek()
}
private mutating func fillOutStack() {
if outStack.count == 0 {
while inStack.count != 0 {
outStack.push(inStack.pop()!)
}
}
}
}
Sie werden zwar viele Beiträge zur Implementierung einer Warteschlange mit zwei Stapeln erhalten: 1. Entweder indem man den enQueue-Prozess sehr viel kostspieliger macht 2. Oder indem man den deQueue-Prozess sehr viel kostspieliger macht
https://www.geeksforgeeks.org/queue-using-stacks/
Eine wichtige Möglichkeit, die ich aus dem obigen Beitrag herausgefunden habe, war die Konstruktion einer Warteschlange nur mit der Stack-Datenstruktur und dem Rekursionsaufruf-Stack.
Man kann zwar argumentieren, dass buchstäblich immer noch zwei Stapel verwendet werden, aber im Idealfall wird nur eine Stapeldatenstruktur verwendet.
Nachstehend finden Sie eine Erklärung des Problems:
Deklarieren Sie einen einzigen Stack für das EnQueuing und DeQueing der Daten und schieben Sie die Daten in den Stack.
beim DeQueueing eine Basisbedingung haben, bei der das Element des Stacks gepoppt wird, wenn die Größe des Stacks 1 ist. Damit wird sichergestellt, dass es während der DeQueue-Rekursion keinen Stack-Überlauf gibt.
Beim DeQueueing werden die Daten zuerst vom obersten Stapel entfernt. Im Idealfall ist dies das Element, das sich oben auf dem Stapel befindet. Sobald dies geschehen ist, rufen Sie rekursiv die Funktion deQueue auf und schieben dann das oben gepoppte Element zurück auf den Stapel.
Der Code wird wie folgt aussehen:
if (s1.isEmpty())
System.out.println("The Queue is empty");
else if (s1.size() == 1)
return s1.pop();
else {
int x = s1.pop();
int result = deQueue();
s1.push(x);
return result;
Auf diese Weise können Sie eine Warteschlange mit einer einzigen Stack-Datenstruktur und dem Rekursionsaufruf-Stack erstellen.
**Einfache JS-Lösung **
Anmerkung: Ich habe Ideen aus den Kommentaren anderer Leute übernommen.
/*
enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it.
*/ class myQueue { constructor() { this.stack1 = []; this.stack2 = []; }
push(item) {
this.stack1.push(item)
}
remove() {
if (this.stack1.length == 0 && this.stack2.length == 0) {
return "Stack are empty"
}
if (this.stack2.length == 0) {
while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2.pop()
}
peek() {
if (this.stack2.length == 0 && this.stack1.length == 0) {
return 'Empty list'
}
if (this.stack2.length == 0) {
while (this.stack1.length != 0) {
this.stack2.push(this.stack1.pop())
}
}
return this.stack2[0]
}
isEmpty() {
return this.stack2.length === 0 && this.stack1.length === 0;
}
}
const q = new myQueue(); q.push(1); q.push(2); q.push(3); q.remove()
console.log(q)
Ich werde diese Frage in Go beantworten, weil Go nicht viele Sammlungen in seiner Standardbibliothek hat.
Da ein Stapel wirklich einfach zu implementieren ist, dachte ich, ich würde versuchen, zwei Stapel zu verwenden, um eine Warteschlange mit zwei Enden zu erreichen. Um besser zu verstehen, wie ich zu meiner Antwort gekommen bin, habe ich die Implementierung in zwei Teile aufgeteilt. Der erste Teil ist hoffentlich einfacher zu verstehen, aber er ist unvollständig.
type IntQueue struct {
front []int
back []int
}
func (q *IntQueue) PushFront(v int) {
q.front = append(q.front, v)
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[0]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
q.back = q.back[1:]
}
}
func (q *IntQueue) PushBack(v int) {
q.back = append(q.back, v)
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[0]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
q.front = q.front[1:]
}
}
Es handelt sich im Grunde um zwei Stapel, bei denen wir zulassen, dass der untere Teil des Stapels von dem anderen manipuliert wird. Ich habe auch die STL-Namenskonventionen verwendet, bei denen die traditionellen Push-, Pop- und Peek-Operationen eines Stapels ein Präfix vorne/hinten haben, unabhängig davon, ob sie sich auf den vorderen oder hinteren Teil der Warteschlange beziehen.
Das Problem mit dem obigen Code ist, dass er den Speicher nicht sehr effizient nutzt. Tatsächlich wächst er endlos, bis der Platz ausgeht. Das ist wirklich schlecht. Die Lösung für dieses Problem ist die Wiederverwendung des unteren Teils des Stapelspeichers, wann immer dies möglich ist. Wir müssen einen Offset einführen, um dies zu verfolgen, da ein Slice in Go nach dem Schrumpfen nicht mehr nach vorne wachsen kann.
type IntQueue struct {
front []int
frontOffset int
back []int
backOffset int
}
func (q *IntQueue) PushFront(v int) {
if q.backOffset > 0 {
i := q.backOffset - 1
q.back[i] = v
q.backOffset = i
} else {
q.front = append(q.front, v)
}
}
func (q *IntQueue) Front() int {
if len(q.front) > 0 {
return q.front[len(q.front)-1]
} else {
return q.back[q.backOffset]
}
}
func (q *IntQueue) PopFront() {
if len(q.front) > 0 {
q.front = q.front[:len(q.front)-1]
} else {
if len(q.back) > 0 {
q.backOffset++
} else {
panic("Cannot pop front of empty queue.")
}
}
}
func (q *IntQueue) PushBack(v int) {
if q.frontOffset > 0 {
i := q.frontOffset - 1
q.front[i] = v
q.frontOffset = i
} else {
q.back = append(q.back, v)
}
}
func (q *IntQueue) Back() int {
if len(q.back) > 0 {
return q.back[len(q.back)-1]
} else {
return q.front[q.frontOffset]
}
}
func (q *IntQueue) PopBack() {
if len(q.back) > 0 {
q.back = q.back[:len(q.back)-1]
} else {
if len(q.front) > 0 {
q.frontOffset++
} else {
panic("Cannot pop back of empty queue.")
}
}
}
Es sind viele kleine Funktionen, aber von den 6 Funktionen sind 3 nur Spiegelungen der anderen.
@melpomene OK, wenn Sie genauer hinsehen, werden Sie feststellen, dass die einzigen Operationen, die ich durchführe, das Hinzufügen/Entfernen des letzten Elements im Array ist. Mit anderen Worten, Pushing und Popping. Im Grunde handelt es sich um Stapel, die aber mit Arrays implementiert sind.
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
0 Stimmen
Um zu lachen, implementieren Sie beide Stapel in ein einziges Array, wobei einer von jedem Ende aus zu dem anderen wächst. Vergleichen Sie die Reihenfolge der Top-of-Stapel mit einer direkten Array-Implementierung der Warteschlange.