Bài viết sưu tầm

Chào các bạn!

Bài viết này xin giới thiệu thuật toán chuyển các giá trị từ stack s1 sang stack s2 nhưng không dùng stack trung gian.

Chúc các bạn học giỏi.

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

 

struct node{

                int inf;

                struct node *link;

};

struct stack{

                struct node *top;

};

 

void create_s(struct stack *s){

                (*s).top=NULL;

}

int empty_s(struct stack s)

{

                return s.top == NULL;

}

 

void push_s(struct stack *s, int x){

                struct node *p = (struct node*)calloc(sizeof(struct node),1);

                p->inf = x;

                p->link = s->top;

                s->top = p;

}

void pop_s(struct stack *s, int *x){

                if(!empty_s(*s)){

                                struct node *p;

                                p = (*s).top;

                                *x = p->inf;

                                (*s).top = (*s).top->link;

                                free(p);

                }

}

void visit(struct stack s){

                int x;

                struct stack temp;

                create_s(&temp);

                while(!empty_s(s)){

                                pop_s(&s,&x);                 

                                printf("%d ",x);

                                push_s(&temp, x);

                }

                while(!empty_s(temp)){

                                pop_s(&temp,&x);                        

                                push_s(&s, x);

                }

                printf("\n");      

}

//Chuyen stack nhung khong dung stack phu

void ChangeStack(struct stack *s1, struct stack *s2){

                int x,n=0,temp;

                while(!empty_s(*s1)){

                                while(!empty_s(*s1)){

                                                pop_s(&*s1,&x);

                                                push_s(&*s2, x);

                                                n++;

                                }                             

                                pop_s(&*s2,&temp);

                                n--;

                                while(n > 0){

                                    pop_s(&*s2,&x);                        

                                                push_s(&*s1,x);

                                                n--;

                                }

                                push_s(&*s2, temp);

                }             

}

 

int main(int argc, char *argv[]){

                struct stack s1,s2;

                int x, code;         

                create_s(&s1);create_s(&s2);

                do{

                                printf("x=");

                                if(code = scanf("%d",&x) > 0)

                                                push_s(&s1, x);

                }while(code > 0);   

    //printf("S1:\t");

                visit(s1);

                ChangeStack(&s1,&s2);

                //printf("S2:\t");

                visit(s2);              

                return 0;

}