Reputation: 91
Here is my stack implementation with linked list. The program is working correctly. Would you have any comments in terms of functionality/ performance/ memory usage?
#include <stdafx.h>
#include <stdlib.h>
#include <stdio.h>
struct node
{
int data;
struct node * next;
};
int length(struct node * current)
{
int len = 0;
while(current)
{
len++;
current = current->next;
}
return len;
}
struct node* push(struct node* stack, int data)
{
struct node * current = stack;
struct node * newNode = (node*)(malloc(sizeof(node*)));
newNode->data = data;
newNode->next = NULL;
//length(current);
//single element case
if(stack == NULL)
{
stack = newNode;
}
else// multiple element case
{
while(current!=NULL)
{
if(current->next==NULL){
current->next = newNode;
break;
}
else
{
current = current->next;
}
}
}
return stack;
}
bool isemp(struct node * stack)
{
if(stack == NULL)
{
printf("Stack is empty");
return true;
}
else{
return false;
}
}
struct node * pop(struct node * stack)
{
struct node * current = stack;
struct node * previous = NULL;
bool isempty = false;
while(!isemp(stack)&& current)
{
if(current->next==NULL)
{
//delete previous;
if(previous)
{
previous->next = NULL;
printf("Popped element is %d ", current->data);
current = current->next;
}
else if(length(stack)==1)
{
printf("Pop last element %d",stack->data);
stack = NULL;
current = NULL;
}
}
else
{
previous = current;
current = current->next;
//stack = current;
}
}
return stack;
}
void main()
{
struct node * stack = NULL;
int data = 1;
int index = 5;
while(index)
{
stack = push(stack,data );
data++;
index--;
}
while(stack!=NULL)
{
stack = pop(stack);
}
}
Upvotes: 0
Views: 5773
Reputation: 1052
One way of implementing the same is done in the link
http://codepad.org/dRMwSOuO
where a new item is added to the initial end of the list and poped from the same end .The boundary conditions are not handled properly though.Still the time complexity will be better as you dont have to traverse in the list till end.
Upvotes: 0
Reputation: 6695
There are myriad number of problems in your code .In push() method you are doing this:
while(current!=NULL)
{
if(current->next==NULL){
current->next = newNode; //This is also Wrong .You are not making Head pointing to newly created node
break;
}
else
{
current = current->next; //This is Wrong For Stack Implementation
}
}`
What you are actually doing is inserting a newly created node to the end of the linked list.Thus somewhat a queue implemented through linked list.
Upvotes: 3