Hello I have an implementation of stack class in C++ language by using a singly linked list. The code also contains operations such as constructor, destructor, pop, push, top, displaying the stacks and checking if a stack is empty or not. Additionally, there is a part for displaying intersection, union and difference of two stacks by using these listed operations. While intersection and union parts works well in the code and provides wanted output, there is a problem with displaying difference of two stacks that I could not figure it out. For this part I want to display elements that S1 has and S2 has not. I would appreciate it if you could help me out.

Here is my two stacks:

S1 = {apple, banana, cherry}

S2 = {banana, cherry, date}

Expected Output for Difference:

S5 (Difference) = {apple}

But instead of that I am getting this output:

S5 (Difference) = {apple, banana, cherry}

#include <iostream>
#include <string>
using namespace std;

// Node structure for singly linked list
struct Node {
    string data;
    Node* next;
};

// Stack class implementation using singly linked list
class Stack {
private:
    Node* top;

public:
    // Constructor
    Stack() : top(nullptr) {}

    // Destructor
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // Push operation
    void push(const string& data) {
        Node* newNode = new Node{data, top};
        top = newNode;
    }

    // Pop operation
    string pop() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return "";
        }
        string data = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return data;
    }

    // Top operation
    string getTop() const {
        if (isEmpty()) {
            return "";
        }
        return top->data;
    }

    // Display all elements in the stack
    void displayStack() const {
        Node* current = top;
        while (current) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    // Check if stack is empty
    bool isEmpty() const {
        return top == nullptr;
    }

    // Find operation
    bool find(const string& data) const {
        Node* current = top;
        while (current) {
            if (current->data == data) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

// Function to compute intersection of two stacks
Stack intersection(Stack& s1, Stack& s2) {
    Stack result;
    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        if (s2.find(element)) {
            result.push(element);
        }
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    return result;
}

// Function to compute union of two stacks
Stack unionStacks(Stack& s1, Stack& s2) {
    Stack result;

    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        result.push(element);
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    while (!s2.isEmpty()) {
        string element = s2.pop();
        if (!result.find(element)) {  // Avoid duplicate entries
            result.push(element);
        }
    }

    return result;
}

Stack difference(Stack& s1, Stack& s2) {
    Stack result;

    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        if (s2.find(element)) {
            continue;
        }
        else {
            result.push(element);
        }
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    return result;
}

// Main function to test functionality
int main() {
    Stack s1, s2;

    // Push elements into stacks S1 and S2
    s1.push("apple");
    s1.push("banana");
    s1.push("cherry");

    s2.push("banana");
    s2.push("cherry");
    s2.push("date");

    cout << "Stack S1: ";
    s1.displayStack();

    cout << "Stack S2: ";
    s2.displayStack();

    // Intersection of S1 and S2
    Stack s3 = intersection(s1, s2);
    cout << "Intersection (S3): ";
    s3.displayStack();

    // Union of S1 and S2
    Stack s4 = unionStacks(s1, s2);
    cout << "Union (S4): ";
    s4.displayStack();
    
    // Difference of S1 and S2
    Stack s5 = difference(s1, s2);
    cout << "Difference (S5): ";
    s5.displayStack();

    return 0;
}

In order the find elements that S1 has and S2 has not (this is what I am trying to do), I tried to put elements into a another stack.

Hello I have an implementation of stack class in C++ language by using a singly linked list. The code also contains operations such as constructor, destructor, pop, push, top, displaying the stacks and checking if a stack is empty or not. Additionally, there is a part for displaying intersection, union and difference of two stacks by using these listed operations. While intersection and union parts works well in the code and provides wanted output, there is a problem with displaying difference of two stacks that I could not figure it out. For this part I want to display elements that S1 has and S2 has not. I would appreciate it if you could help me out.

Here is my two stacks:

S1 = {apple, banana, cherry}

S2 = {banana, cherry, date}

Expected Output for Difference:

S5 (Difference) = {apple}

But instead of that I am getting this output:

S5 (Difference) = {apple, banana, cherry}

#include <iostream>
#include <string>
using namespace std;

// Node structure for singly linked list
struct Node {
    string data;
    Node* next;
};

// Stack class implementation using singly linked list
class Stack {
private:
    Node* top;

public:
    // Constructor
    Stack() : top(nullptr) {}

    // Destructor
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    // Push operation
    void push(const string& data) {
        Node* newNode = new Node{data, top};
        top = newNode;
    }

    // Pop operation
    string pop() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return "";
        }
        string data = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return data;
    }

    // Top operation
    string getTop() const {
        if (isEmpty()) {
            return "";
        }
        return top->data;
    }

    // Display all elements in the stack
    void displayStack() const {
        Node* current = top;
        while (current) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    // Check if stack is empty
    bool isEmpty() const {
        return top == nullptr;
    }

    // Find operation
    bool find(const string& data) const {
        Node* current = top;
        while (current) {
            if (current->data == data) {
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

// Function to compute intersection of two stacks
Stack intersection(Stack& s1, Stack& s2) {
    Stack result;
    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        if (s2.find(element)) {
            result.push(element);
        }
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    return result;
}

// Function to compute union of two stacks
Stack unionStacks(Stack& s1, Stack& s2) {
    Stack result;

    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        result.push(element);
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    while (!s2.isEmpty()) {
        string element = s2.pop();
        if (!result.find(element)) {  // Avoid duplicate entries
            result.push(element);
        }
    }

    return result;
}

Stack difference(Stack& s1, Stack& s2) {
    Stack result;

    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        if (s2.find(element)) {
            continue;
        }
        else {
            result.push(element);
        }
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    return result;
}

// Main function to test functionality
int main() {
    Stack s1, s2;

    // Push elements into stacks S1 and S2
    s1.push("apple");
    s1.push("banana");
    s1.push("cherry");

    s2.push("banana");
    s2.push("cherry");
    s2.push("date");

    cout << "Stack S1: ";
    s1.displayStack();

    cout << "Stack S2: ";
    s2.displayStack();

    // Intersection of S1 and S2
    Stack s3 = intersection(s1, s2);
    cout << "Intersection (S3): ";
    s3.displayStack();

    // Union of S1 and S2
    Stack s4 = unionStacks(s1, s2);
    cout << "Union (S4): ";
    s4.displayStack();
    
    // Difference of S1 and S2
    Stack s5 = difference(s1, s2);
    cout << "Difference (S5): ";
    s5.displayStack();

    return 0;
}

In order the find elements that S1 has and S2 has not (this is what I am trying to do), I tried to put elements into a another stack.

• c++
• data-structures

• 9 See: What is a debugger and how can it help me diagnose problems?. – wohlstad Commented Mar 28 at 14:05
• 2 using namespace std; + names that are very similar to names from std kills readability. – 463035818_is_not_an_ai Commented Mar 28 at 14:06
• 2 Looking at the code for difference() my guess is s2 no longer contains the items you expect because one of the previous functions destroyed it. Edit: Looks like unionStacks destroys s2. If you used a debugger or just put s2.displayStack(); before the call of Stack s5 = difference(s1, s2); you should have seen this problem instantly. I mention this because good debugging is essential to successful programming. – drescherjm Commented Mar 28 at 14:11
• I noticed that C++ already comes with all this functionality as part of the language. Is there a reason you are "reinventing this wheel" that is already provided by C++? – Eljay Commented Mar 28 at 15:23
• @Eljay Homework from school maybe? Some concepts are best understood if you implement them yourself. All program languages have sort algorithms included in their standard libraries. Nonetheless, for educational purposes, students have to reimplement them ... – derpirscher Commented Mar 28 at 15:27

1 Answer 1

Your problem is not the difference function but the unionStacks function which clears s2. Ie try outputting s1 and s2 after each operation, and you will see, that s2 is empty after you did the unionStacks.

Thus of course, when you do difference(s1, s2) none of the elements from s1 will be found in s2 and therefore all elements from s1 are added to the difference ...

Why is s2 empty after unionStacks? Because you recrate s1 from temp, but you fot to recreate s2 from temp in unionStacks ...

The following will solve your issue. See the addtional code marked with /***********/

Stack unionStacks(Stack& s1, Stack& s2) {
    Stack result;

    Stack temp;  // Temporary stack to preserve s1 during traversal

    while (!s1.isEmpty()) {
        string element = s1.pop();
        temp.push(element);
        result.push(element);
    }

    // Restore original stack s1
    while (!temp.isEmpty()) {
        s1.push(temp.pop());
    }

    while (!s2.isEmpty()) {
        string element = s2.pop();
        /*************************/
        temp.push(element); 
        if (!result.find(element)) {  // Avoid duplicate entries
            result.push(element);
        }
    }

    /***************************/
    // Restore original stack s2
    while (!temp.isEmpty()) {
        s2.push(temp.pop());
    }


    return result;
}

BTW I'd suggest to add an additonal method to walk through your stack without popping the elements. This way you would not need to always create a temp stack and restore the original stack from that temp.