栈节点按学院排序入队列异常：仅2个节点入队问题排查

我在一个小型项目中实现栈与队列功能，客户将节点存入栈，卖家需将栈中节点按学院名称排序后转入队列：所有college为"kdoj"的节点优先入队，随后是college为"kdse"的节点。我使用两个for循环实现排序，但栈中节点数超过2个时，仅有2个节点能成功入队，卡在此处许久。

输入示例 #

name : david
ic num: 123
phone num: 123
college: kdse
quantity: 1
size: m

name : jojo
ic num: 123
phone num: 123
college: kdse
quantity: 1
size: m

name : zoro
ic num: 123
phone num: 123
college: kdoj
quantity: 1
size: m

完整可运行代码 #

#include <iostream>
#include <cstring>
#include<iomanip>
#include <conio.h>
#include<string>

using namespace std;

//nodes
struct customerNode {
    string name, id, college;
    int phoneNum,quantity;
    char size;
    public:
    customerNode* next;
    customerNode(string name, string id, int phoneNum,string college, int quantity, char size)
    {
        name = name;
        id = id;
        phoneNum = phoneNum;
        college = college;
        quantity = quantity;
        size = size;
        next = NULL;
    }
};

//class customer
class Customer{
    public:
    customerNode *head = NULL;
    bool isEmpty(){
        return(head == NULL);
    }
    void pushStack(string name, string id, int phoneNum, string college, int quantity, char size){
        customerNode *newnode = new customerNode(name,id,phoneNum,college,quantity,size);
        
        newnode->name = name;
        newnode->id= id;
        newnode->phoneNum = phoneNum;
        newnode->college = college;
        newnode->quantity = quantity;
        newnode->size = size;
        
        if(isEmpty()){
            newnode->next = head;
            head = newnode;
            cout<<endl<<"created new stack."<<endl;
        }
        else{
            newnode->next = head;
            head = newnode;
            cout<<endl<<"added node into a stack."<<endl;
        }
    }
    
    //pop out node from stack
    void popStack(){
        customerNode *temp;
        
        temp = head; //temp variable
        head = temp->next;
        temp->next = NULL;
            cout<<endl<<"Order has been deleted!";
    }
    
    //push node into stack
    void enterOrder(){
         int phoneNum, quantity;
        char size;
        string name, id, college;
                cout<<endl<<"\tADDING YOUR ORDER.\n";
                cout<<"\tName: ";
                cin.ignore();
                getline(cin,name);
                cout<<"\tIC Num: ";
                cin>>id;
                cout<<"\tPhone Number: ";
                cin>>phoneNum;
                cout<<"\tCollege name: ";
                cin>>college;
                cout<<"\tQuantity: ";
                cin>>quantity;
                cout<<"\tSize (S/M/L/XL): ";
                cin>>size;
        pushStack(name, id, phoneNum,college, quantity, size);
        cin.get();
    }
    
    //see order and trigger popout funct
    void deleteorder(){
        char choice;
        cout<<"YOUR ODER."<<endl<<
        setw(10)<<left<<"ID"
        <<setw(20)<<left<<"NAME"
        <<setw(10)<<left<<"CONTACT"
        <<setw(20)<<left<<"COLLEGE"
        <<setw(10)<<left<<"QUANTITY"
        <<setw(5)<<left<<"SIZE";
        stackTop();
        cout<<endl;
        cout<<endl<<"Confirm to delete?: ";
        cin>>choice;
        if(choice == 'y' || choice == 'Y'){
            popStack();
        }
    }
    
    //display node at the top
    void stackTop(){
        customerNode *check;
        if(!isEmpty()){
        check = head;
        cout<<endl<<
        setw(10)<<left<<check->id
        <<setw(20)<<left<<check->name
        <<setw(10)<<left<<check->phoneNum
        <<setw(20)<<left<<check->college
        <<setw(10)<<left<<check->quantity
        <<setw(5)<<left<<check->size;
        }
        else{
            cout<<endl<<"Stack is an underflow.";
            getch();
        }
    }
    
    int getNumberNodes(){
        customerNode  *check;
        check = head;
        int counter = 0;
        while(check!= NULL){
            counter++;
            check = check->next;
        }
        return counter;
    }
    
    
};

//Customer main menu    
void customerMenu(Customer &c){
    int choice;
    do{cout    
    <<endl<<"CUSTOMER MENU"
    <<endl<<"Please choose your task."
    <<endl<<"1. Insert Order"
    <<endl<<"2. Delete Order"
    <<endl<<"3. Check Order"
    <<endl<<"4. Exit"
    <<endl<<"Your Choice: ";
    cin>>choice;

        //customer task
        switch(choice){
            case 1: c.enterOrder();
            break; 
            case 2: c.deleteorder();
            break;
            case 3:
                    cout<<"\nYOUR ODER."<<endl<<
                    setw(10)<<left<<"ID"
                    <<setw(20)<<left<<"NAME"
                    <<setw(10)<<left<<"CONTACT"
                    <<setw(20)<<left<<"COLLEGE"
                    <<setw(10)<<left<<"QUANTITY"
                    <<setw(5)<<left<<"SIZE";
                    c.stackTop();
                    cout<<endl;
            break;
        }
    }while(choice != 4);
    
};



//SELLER CLASS
class Seller{
    string id;
    string password;
    
    public:
    customerNode *backPtr, *frontPtr;
    
    //constructor seller
    Seller(){
        id = "12345";
        password = "12345";
        backPtr = NULL;
        frontPtr = NULL;
    }
    
    //check queue empty
    bool queueEmpty(){
        return (backPtr == NULL && frontPtr == NULL);
    }
    

    
    //display all nodes in stack
    void getStack(Customer &c){
        customerNode *check;
        if(!c.isEmpty()){
        check = c.head;
        while(check!=NULL){
        cout<<endl<<
        setw(10)<<left<<check->id
        <<setw(20)<<left<<check->name
        <<setw(10)<<left<<check->phoneNum
        <<setw(20)<<left<<check->college
        <<setw(10)<<left<<check->quantity
        <<setw(5)<<left<<check->size;
        check=check->next;
        }
        }
        else{
            cout<<endl<<"Stack is an underflow.";
            getch();
        }
    }
    
    
    //will trigger getStack() 
    void displayStack(Customer &c){
        cout<<"\nCUSTOMER FULL ORDERLIST."<<endl<<
        setw(10)<<left<<"ID"
        <<setw(20)<<left<<"NAME"
        <<setw(10)<<left<<"CONTACT"
        <<setw(20)<<left<<"COLLEGE"
        <<setw(10)<<left<<"QUANTITY"
        <<setw(5)<<left<<"SIZE";
        getStack(c);
        cout<<endl;
    }


    //display all nodes in queue
    void getQueue(){
        customerNode *check;
        if(!queueEmpty()){
            check = frontPtr;
                while(check!=NULL){
                cout<<endl<<
                setw(10)<<left<<check->id
                <<setw(20)<<left<<check->name
                <<setw(10)<<left<<check->phoneNum
                <<setw(20)<<left<<check->college
                <<setw(10)<<left<<check->quantity
                <<setw(5)<<left<<check->size;
                check=check->next;
                }
        }
        else{
            cout<<endl<<"Stack is an underflow.";
            getch();
        }
    }
    
    //display node in queue 
    void displayQueue(){
        cout<<"\nSORTED CUSTOMER FULL ORDERLIST."<<endl<<
        setw(10)<<left<<"ID"
        <<setw(20)<<left<<"NAME"
        <<setw(10)<<left<<"CONTACT"
        <<setw(20)<<left<<"COLLEGE"
        <<setw(10)<<left<<"QUANTITY"
        <<setw(5)<<left<<"SIZE";
        getQueue();
        cout<<endl;
    }
    
    //insert queuee
    void insertQueue(customerNode *newNode){
        if(!queueEmpty()){
            newNode->next = NULL;
            backPtr->next = newNode;
            backPtr = newNode;
            cout<<endl<<"inserted node into queue."<<endl;
        }
        else{
            frontPtr = newNode;
            backPtr = newNode;
        }
    }
    
    
    
    void sortOrder(Customer &c){
            for(customerNode *node = c.head; node!=NULL; node = node->next){
                if(node->college == "kdoj"){
                    cout<<endl<<node->college;
                    insertQueue(node);
                }
            }

            for(customerNode *node = c.head; node!=NULL; node = node->next){
                if(node->college == "kdse"){
                    cout<<endl<<node->college;
                    insertQueue(node);
                }
            }
            
        displayQueue();
    }
};

//seller main menu
void sellerMenu(Customer &c, Seller &s){
    int choice;
    do{cout    
    <<endl<<"SELLER MENU"
    <<endl<<"Please choose your task."
    <<endl<<"1. Display OrderList"
    <<endl<<"2. Sort OrderList"
    <<endl<<"4. Exit"
    <<endl<<"Your Choice: ";
    cin>>choice;
        //choose task
        switch(choice){
            case 1: s.displayStack(c);
            break; 
            case 2: s.sortOrder(c);
            break;
            case 3: 
            break;
        }
    }while(choice != 4);
    
}



void menu(Customer &c, Seller &s){ //main menu function
    int choice;
    do{
    cout
    <<endl<<"Welcome to HotspotPrinting!"
    <<endl<<"Please choose your role."
    <<endl<<"1. Customer"
    <<endl<<"2. Seller"
    <<endl<<"3. Exit"
    <<endl<<"Your Choice: ";
    cin>>choice;
        switch(choice){
            case 1: customerMenu(c);
            break;
            case 2: sellerMenu(c,s);
            break;
        }
    }while(choice != 3);
}

int main()
{
    Customer c;
    Seller s;
    menu(c,s);
    cout<<endl<<"Thank You For Using Our Service :)!";
    return 0;
}

核心问题 #

直接将栈内节点指针插入队列时，insertQueue方法中执行了newNode->next = NULL，这会修改原栈中节点的next指针，破坏了栈的链表结构。第一次循环插入"kdoj"节点后，该节点的next被置空，第二次循环遍历栈时，到这个节点就会终止，导致后续节点无法被遍历到，最终只有部分节点入队。

解决方法 #

推荐采用复制节点插入队列的方案：不复用原栈节点，而是创建新的customerNode对象，复制原节点的数据后插入队列，避免修改原栈的链表结构。

修改后的sortOrder方法 #

void sortOrder(Customer &c){
    // 优先处理kdoj学院的节点
    for(customerNode *node = c.head; node!=NULL; node = node->next){
        if(node->college == "kdoj"){
            cout<<endl<<node->college;
            // 创建新节点并复制原节点数据
            customerNode *newNode = new customerNode(node->name, node->id, node->phoneNum, node->college, node->quantity, node->size);
            insertQueue(newNode);
        }
    }

    // 处理kdse学院的节点
    for(customerNode *node = c.head; node!=NULL; node = node->next){
        if(node->college == "kdse"){
            cout<<endl<<node->college;
            customerNode *newNode = new customerNode(node->name, node->id, node->phoneNum, node->college, node->quantity, node->size);
            insertQueue(newNode);
        }
    }
    
    displayQueue();
}

额外优化 #

原customerNode构造函数存在参数名与成员变量名冲突的问题，name = name这类代码实际是将参数赋值给自己，并未初始化成员变量。需修改构造函数：

customerNode(string name, string id, int phoneNum,string college, int quantity, char size)
{
    this->name = name;
    this->id = id;
    this->phoneNum = phoneNum;
    this->college = college;
    this->quantity = quantity;
    this->size = size;
    next = NULL;
}

内容的提问来源于stack exchange，提问作者Woppy