Отправлено: 05.07.15 01:45. Заголовок: Queue using a linked list

so I am now doing a Queue using a linked list instead of a stack. a queue is basically similar but when you add. you add at the tail. tail insert.

here is the header file

#include "status.h"

struct my_queue_public;
typedef struct my_queue_public* MY_QUEUE;

struct my_queue_public
{
void(*destroy)(MY_QUEUE* phMy_queue);
Status(*service)(MY_QUEUE hMy_queue);
Status(*append)(MY_QUEUE hMy_queue, int item);
Bool(*empty)(MY_QUEUE hMy_queue);
int* (*front)(MY_QUEUE hMy_queue);
};

MY_QUEUE my_queue_init_default(void);
//service queue
//add to the queue
//init and destroy
//empty?
//look at the front element




here is the implementation



#include "my_queue.h"
#include <stdio.h>
#include <stdlib.h>
struct node;
typedef struct node Node;
typedef Node* Node_ptr;

struct node
{
int data;
Node_ptr next;

};

struct head_node;
typedef struct head_node Head_node;
typedef Head_node *Head_ptr;

struct head_node
{
struct my_queue_public methods;
Node_ptr head;
};

void destroy(MY_QUEUE queue);
Status append(MY_QUEUE queue, int item);
Status service(MY_QUEUE queue);
int* front(MY_QUEUE queue);
Bool empty(MY_QUEUE stack);

void init_functions(MY_QUEUE queue)
{
queue->destroy = destroy;
queue->empty = empty;
queue->service = service ;
queue->append = append;
queue->front = front;
}
MY_QUEUE my_queue_init_default(void)
{
Head_ptr head;

head = malloc(sizeof(Head_node));

if (head != NULL)
{
head->head = NULL;

init_functions((MY_QUEUE)head);
}


return (MY_QUEUE)head;
}

void destroy(MY_QUEUE queue)
{

/*Head_ptr head = (Head_ptr)queue;

Node_ptr tmp;

if (head == NULL) {

return;
}



for (Node_ptr current = head->head; current != NULL;)
{
tmp = current;
current = current->next;
free(tmp);
}

head->head = NULL;*/
}

Status append(MY_QUEUE queue, char item)
{
Node_ptr temp;

//create a new node
temp = (Node_ptr)malloc(sizeof(Node)); //allocates the space
if (temp == NULL)
{
printf("Failed to allocate node\n");
return FAILURE;
}

temp->data = item;
temp->next = NULL;



((Node_ptr)queue)->next = temp;

return SUCCESS;
}

Status service(MY_QUEUE queue)
{
Head_ptr head = (Head_ptr)queue;
Node_ptr tmp;

if (head == NULL || head->head == NULL)
{
return FAILURE;
}

tmp = head->head;
head->head = head->head->next;

free(tmp);

return SUCCESS;
}

int* front(MY_QUEUE queue)
{
Head_ptr head = (Head_ptr)queue;

if (head == NULL || head->head == NULL) {

return NULL;
}

return &(head->head->data);
}

Bool empty(MY_QUEUE stack)
{
Head_ptr head = (Head_ptr)stack;
return head == NULL || head->head == NULL;
}





this is not working. the problem is https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1975

i have the function for the problem working. because i have a vector implementation that works fine. but am required to do it with a linked list. btw the Destroy function crashes. and if i comment it out. i get wrong answers.

 Отправлено: 05.07.15 09:19. Заголовок: You need yo include ..

You need to include also data member tail and write method add. Also along with the method front there should be a method that removes a node from the head like pop_front

 Отправлено: 08.07.15 09:17. Заголовок: hello. its me hammod..

hello. its me hammodi. just different account i forgot old password.


this destroy function isn't working for the queue.



void destroy(MY_QUEUE queue)
{

Head_ptr head = (Head_ptr)queue;

Node_ptr tmp;

Node_ptr current;

if (head == NULL) {

return;
}



for ( current = head->head; current != NULL;)
{
tmp = current;
current = current->next;
free(tmp);
}

head->head = NULL;
}



any ideas

 Отправлено: 08.07.15 10:21. Заголовок: my insert tail funct..

my insert tail function isn't working either. for some reason the first item i enter is not in the list.

Status append(MY_QUEUE queue, int item)
{
Node_ptr temp;

Head_ptr head = (Head_ptr) queue;

//create a new node


temp = (Node_ptr)malloc(sizeof(Node)); //allocates the space
if (temp == NULL)
{
printf("Failed to allocate node\n");
return FAILURE;
}

temp->data = item;
temp->next = NULL;

while (1){
if (head->head == NULL){

head->head = temp;

break;
}
else if ((head->head)->next == NULL)
{
(head->head)->next = temp;



break;
}
head->head = (head->head)->next;
printf("a");

}




return SUCCESS;
}

 Отправлено: 08.07.15 20:33. Заголовок: Hi, try the followi..

Hi,

try the following function implementation

 
 Status append( MY_QUEUE queue, int item )  
 {  
 	Head_ptr head = (Head_ptr) queue;  
  
 	//create a new node  
 	Node_ptr temp;  
  
 	temp = ( Node_ptr )malloc( sizeof( Node ) ); //allocates the space  
  
 	if ( temp == NULL )  
 	{  
 		printf( "Failed to allocate node\n" );  
 		return FAILURE;  
 	}  
  
 	temp->data = item;  
 	temp->next = NULL;  
  
 	Node_ptr *current = &head->head; 
 	while ( *current != NULL ) current = &( *current )->next; 
  
 	*current = temp; 
   
 	return SUCCESS;  
 } 
 

 Отправлено: 09.07.15 06:37. Заголовок: actually i fixed the..

actually i fixed the append function. but the destroy function is not working. its crashing.




void destroy(MY_QUEUE* queue)
{

Head_ptr head = (Head_ptr)queue;

Node_ptr tmp;

Node_ptr current = head->head;

if (head == NULL) {

return;
}


while (current !=NULL){
tmp = current;
current = current->next;
free(tmp);
}

head->head = NULL;
}

 Отправлено: 09.07.15 11:34. Заголовок: It is not clear why ..

It is not clear why the function is declared like

 
 void destroy(MY_QUEUE* queue)  
 

That is why does the parameter have type MY_QUEUE* instead of MY_QUEUE?

Also if to replace MY_QUEUE* with MY_QUEUE in the parameter declaration nevertheless there is a wrong order of the stetement execution in the function. At first you use expression head->head in statement

 
 Node_ptr current = head->head;  
 

and only after that you check whether head is equal to NULL

 
 if (head == NULL) {  
     return;  
 } 
  

So if head is indeed equal to NULL then the first statement can result in the function crash.

You could use the function from the class stack that I already showed.
For example

 
 void destroy( MY_QUEUE queue )  
 {  
 	if ( queue == NULL ) return;  
  	  
 	Head_ptr head = ( Head_ptr )queue;  
  	  
 	for ( Node_ptr current = head->head; current != NULL; )  
 	{  
 		Node_ptr tmp = current;  
 		current = current->next;  
 		free( tmp );  
 	}  
  	  
 	head->head = NULL;  
 }