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.
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 forgot 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.