Created
August 26, 2012 12:43
-
-
Save murikadan/3478676 to your computer and use it in GitHub Desktop.
Program to reverse a linked list using stack
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
struct node | |
{ | |
int val; | |
struct node* next; | |
}; | |
void enqueue(struct node**,struct node **,int); | |
void dequeue(struct node**,struct node **); | |
void traverse(struct node*,struct node*); | |
void push(struct node**,struct node**); | |
struct node* pop(struct node**); | |
void listrev(struct node**,struct node**); | |
void free_queue(struct node*); | |
void free_stack(struct node*); | |
int isstackempty(struct node*); | |
int main() | |
{ | |
int key; | |
struct node *front=NULL,*rear=NULL; | |
FILE *fp; | |
fp=fopen("input","r"); | |
fscanf(fp,"%d",&key); | |
while(!feof(fp)) | |
{ | |
enqueue(&front,&rear,key); | |
fscanf(fp,"%d",&key); | |
} | |
traverse(front,rear); | |
listrev(&front,&rear); | |
traverse(front,rear); | |
free_queue(front); | |
return 0; | |
} | |
void enqueue(struct node** front,struct node** rear,int num) | |
{ | |
struct node* newnode=malloc(sizeof(struct node)); | |
newnode->val=num; | |
newnode->next=NULL; | |
if(*front==NULL) | |
*front=*rear=newnode; | |
else | |
{ | |
(*rear)->next=newnode; | |
(*rear)=newnode; | |
} | |
} | |
void dequeue(struct node** front,struct node** rear) | |
{ | |
struct node* temp=NULL; | |
if(*front==*rear) | |
{ | |
temp=*front; | |
*front=*rear=NULL; | |
} | |
else if(*front!=NULL) | |
{ | |
temp=*front; | |
*front=(*front)->next; | |
} | |
if(temp!=NULL) | |
{ | |
temp->next=NULL; | |
free(temp); | |
} | |
} | |
void free_queue(struct node* front) | |
{ | |
while(front!=NULL) | |
{ | |
free(front); | |
front=front->next; | |
} | |
} | |
void traverse(struct node* front,struct node* rear) | |
{ | |
struct node* temp=front; | |
while(temp!=NULL) | |
{ | |
printf("%d",temp->val); | |
if(temp!=rear) | |
printf("--->"); | |
else | |
printf("\n"); | |
temp=temp->next; | |
} | |
} | |
void push(struct node** top,struct node** newnode) | |
{ | |
(*newnode)->next=NULL; | |
if(*top==NULL) | |
*top=*newnode; | |
else | |
{ | |
(*newnode)->next=*top; | |
*top=*newnode; | |
} | |
} | |
struct node* pop(struct node** top) | |
{ | |
struct node* temp=NULL; | |
if(!isstackempty(*top)) | |
{ | |
temp=(*top); | |
*top=(*top)->next; | |
} | |
temp->next=NULL; | |
return temp; | |
} | |
int isstackempty(struct node* top) | |
{ | |
if(top==NULL) | |
return 1; | |
else | |
return 0; | |
} | |
void listrev(struct node** front,struct node** rear) | |
{ | |
struct node *temp1=NULL,*temp2=NULL,*top=NULL; | |
temp1=*front; | |
while(temp1!=NULL) | |
{ | |
temp2=temp1->next; | |
push(&top,&temp1); | |
temp1=temp2; | |
} | |
if(!isstackempty(top)) | |
*front=pop(&top); | |
temp1=*front; | |
while(!isstackempty(top)) | |
{ | |
temp2=pop(&top); | |
temp1->next=temp2; | |
temp1=temp2; | |
} | |
*rear=temp1; | |
} | |
/* | |
Linked list is read from a file called input | |
Content of the file is integers | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Program reads input from a file called 'input', makes a queue, then uses a stack to reverse it.
No additional memory is used for stack