我正在嘗試使用標準庫為我的代碼的某些部分創建佇列。對于抽象的想法，我的佇列將有前、后指標，它們指向佇列中的前和后元素。因此，當我推送某些東西時 Back ptr 將指向已推送的新值。當我彈出某些東西時，前面的 ptr 將指向下一個前面的值。
例如：首先我們宣告它是空的，Front Back都指向nullptr，
[] - 前 = nullptr，后 = nullptr
推(5)
[5] - 前 = 5，后 = 5
推(7)
[7 , 5] - 前 = 5，后 = 7
推(4)
[4, 7, 5] - 前 = 5，后 = 4
流行音樂（）
[4, 7] - 前 = 7，后 = 4
流行音樂（）
[4] - 前 = 4，后 = 4
流行音樂（）
[] - 前 = nullptr，后 = nullptr
class Queue
{
private:
struct node
{
int value;
node* next;
node(int value, node* next = nullptr)
{
this->value = value;
this->next = next;
}
};
node* front, * back;
public:
//Constructor
Queue()
{
front = nullptr;
back = nullptr;
}
//Class methods:
void push(int num);
int pop();
bool isEmpty();
};
方法定義：
void Queue::push(int num)
{
back = new node(num, back);
}
int Queue::pop()
{
int num = front->value;
node * temp = front;
front = front->next;
delete temp;
return num;
}
bool Queue::isEmpty()
{
if (front == nullptr)
{
return true;
}
else
{
return false;
}
}
現在我從 pop() 得到運行時錯誤，并且 pop() 沒有洗掉前面的值。
uj5u.com熱心網友回復：
我重寫你的代碼：
#include <iostream>
using namespace std;
class Queue
{
private:
struct node
{
int value;
node* next;
node(int value, node* next = nullptr)
{
this->value = value;
this->next = next;
}
};
node* front, * back;
public:
//Constructor
Queue()
{
front = nullptr;
back = nullptr;
}
//Class methods:
void push(int num);
int pop();
bool isEmpty() { return (front == nullptr); }
void print();
};
void Queue::print()
{
node* tmp = this->front;
cout << "[ ";
while(tmp != nullptr) {
cout << tmp->value << " ";
tmp = tmp->next;
}
cout << "]";
}
void Queue::push(int num)
{
node* tmp = new node(num, nullptr);
if(!isEmpty()) { // if not empty
back->next = tmp;
back = tmp;
return;
}
// if list is empty
front = tmp;
back = tmp;
}
int Queue::pop()
{
if (isEmpty()) return 0;
int num = front->value;
if (front->next == nullptr) { // if list have only one element
delete front;
front = nullptr;
back = nullptr;
return num;
}
node * temp = front;
front = front->next;
delete temp;
return num;
}
int main() {
Queue q;
q.push(5);
q.push(2);
q.push(2);
q.push(5);
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.push(5);
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.push(5);
q.print();
return 0;
}
print()由于測驗，我添加了一個方法，變得isEmpty()更干凈，并添加了一些條件來檢查特殊情況。
如果串列為空并且pop()被呼叫，則無需執行任何操作。
如果串列為空并且push()被呼叫back并且front需要指向同一個物件。
如果串列只有一個元素并且pop()被稱為串列需要清除，front并且back需要nullptr
uj5u.com熱心網友回復：
我注意到新節點總是有next == nullptr并且它們總是附加到串列的末尾。那么為什么不在建構式中這樣做呢？使用Node **是一個眾所周知的技巧，可以避免為空串列和非空串列使用單獨的代碼路徑。
我將成員變數的初始化更改為使用帶有大括號的現代行內初始化Node* next{nullptr};。在 Queue 的情況下，您甚至不再需要建構式。
隨著對 and 方法的更改Node **back可以push簡化pop一點。
#include <iostream>
class Queue
{
private:
struct Node
{
int value;
Node* next{nullptr};
// prev is the end of the list this Node should be attached to
// specifically the address of the Node*, not the Node
Node(Node **prev, int value_) : value(value_) {
*prev = this;
}
};
Node *front{nullptr};
// back is the end of the list to attach new Nodes
// specifically the address of the Node*, not the Node
// this allows it to be eigther &front or &node.next
Node **back{&front};
public:
//Class methods:
void push(int num);
int pop();
bool isEmpty() { return (front == nullptr); }
void print();
};
void Queue::print()
{
Node* tmp = this->front;
std::cout << "[ ";
while(tmp != nullptr) {
std::cout << tmp->value << " ";
tmp = tmp->next;
}
std::cout << "]";
}
void Queue::push(int num)
{
// Nodes automatically attach to the back
new Node(back, num);
// just needs back to be advanced
back = &((*back)->next);
}
int Queue::pop()
{
if (isEmpty()) return 0;
int num = front->value;
Node * temp = front;
// advance front
front = front->next;
delete temp;
if (front == nullptr) {
// empty list now so back has become invalid
// reset it to point at front
back = &front;
}
return num;
}
int main() {
Queue q;
q.push(5);
q.push(2);
q.push(2);
q.push(5);
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.push(5);
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.pop();
q.print();
q.push(5);
q.print();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/475360.html