Pushing a stack containing ONLY unique values ​​in C

Question

I implemented a stack with pointers that works as intended. Now I need it to push the stack without pushing the duplicate. For example, if I push "2" onto the stack, pushing another "2" will still have only one "2" on the stack, as it already exists.

Below I will talk about how I tried to create a new push function. I know that I have to cross the stack and check it for the element I am adding, but I think I am doing it wrong? Can anyone help me out?

typedef struct Node { void *content; struct Node *next; } Node; typedef struct Stack { Node *head; int count; } Stack; void push(Stack *stack, void *newElem) { Node *newNode = (Node*) malloc(sizeof(Node)); if (stack->count > 0) { int i; for (i = 0, newNode = stack->head; i < stack->count; i++, newNode = newNode->next) { if (newNode->content == newElem) return; } } else { newNode->next = stack->head; newNode->content = newElem; stack->head = newNode; stack->count++; } } 

Answer 1

You already have a working

 void push(Stack *stack, void *newElem); 

right?

So why not write a new function

 int push_unique(Stack *stack, void *newElem) { if (find_value(stack, newElem) != NULL) { return 1; // indicate a collision } push(stack, newElem); // re-use old function return 0; // indicate success } 

Now you have reduced the problem to recording

 Node *find_value(Stack *stack, void *value); 

... can you do this?

Answer 2

 if (newNode->content == newElem) 

You are comparing two pointers. I think you want to check if their contents are equal:

 #include <string.h> if (memcmp(newNode->content, newElem, size) == 0) 

The value of size may be indicated by the caller. In your case, it should be sizeof(int) .

Also, once you go through the stack, you will not add an item to your data structure.

Answer 3

The problem is that if your stack is not empty and you do not find the item already on the stack, you are not doing anything. You need to get rid of the else keyword and make this code unconditional. You then allocate space for the new Node before you know if you need it or not, and, even worse, rewrite the newly allocated pointer to your iteration over the stack to make sure you need to click it or not. So move malloc down after the end } if

Answer 4

I'm not sure you understand this, but the proposed implementation does a linear search on a linked list. If you push 2000 items on the stack with an average of two duplicates of each item value, then 2000 searches of a linked list averages 500-750 links (it depends on when, IE: what order, duplicates are presented in the search function. This requires 1 million + comparison. Not very.

More efficient duplicate detection in find_value () above can use a hash table with O (1) lookup time or a tree with O (log N) lookup time. The first, if you know how many values ​​you potentially push on the stack, and the second, if the number is unknown, for example, when receiving data from a socket in real time. (if you could implement your stack in an array instead of a much slower and more detailed linked list)

In any case, to properly support the hash table, the pop () function must be paired with the hashpop () function of the hash table, which removes the corresponding value from the hash table.

With Hashtable, your stack can simply point to the value of the element sitting in its hash location - it returns from find_value (). However, using a tree with a balanced location, the node location and therefore the value of the element will change all the time, so you will need to save the value of the element on the stack and the tree. If you are not writing in a very compressed memory environment, the performance that the second data structure could provide would be modest in memory.