堆栈的各种算法

1. #include   
2. char stack[512];  
3. int top=0;  
4. void push(char c)  
5. {  
6.     stack[top]=c;  
7.     top++;  
8. }  
9. char pop()  
10. {  
11.     top--;  
12. return stack[top];  
13. }  
14. int is_empty()  
15. {  
16. return 0==top;  
17. }  
18. void main()  
19. {  
20. '1');  
21. '2');  
22. '3');  
23. '4');  
24. '5');  
25. while(!is_empty())  
26.         putchar(pop());  
27. '/n');  
28.     getch();  
29. }

1. #include   
2. #include   
3. /* typedef int DataType; */  
4. #define DataType int  
5. #define MAX 1024  
6. typedef struct  
7. {  
8.     DataType data[MAX];  
9. int top;  
10. }stack, *pstack;  
11. pstack *init_stack()  
12. {  
13.     pstack ps;  
14. sizeof(stack));  
15. if(!ps)  
16.     {  
17. "Error. fail malloc.../n");  
18. return NULL;  
19.     }  
20.     ps->top=-1;  
21. return ps;  
22. }  
23. int empty_stack(pstack ps)  
24. {  
25. if(-1 == ps->top)  
26. return 1;  
27. else  
28. return 0;  
29. }  
30. int push(pstack ps, DataType data)  
31. {  
32. if(ps->top == MAX-1)  
33.     {  
34. "Stack is full.../n");  
35. return 0;  
36.     }  
37.     ps->top++;  
38.     ps->data[ps->top]=data;  
39. return 1;  
40. }  
41. int pop(pstack ps, DataType *data)  
42. {  
43. if(empty_stack(ps))  
44.     {  
45. "Stack is empty.../n");  
46. return 0;  
47.     }  
48.     *data=ps->data[ps->top];  
49.     ps->top--;  
50. return 1;  
51. }  
52. DataType top_stack(pstack ps)  
53. {  
54. if(empty_stack(ps))  
55.     {  
56. "Stack is empty.../n");  
57. return 0;  
58.     }  
59. return ps->data[ps->top];  
60. }  
61. void display(pstack ps)  
62. {  
63. int i;  
64. if(empty_stack(ps))  
65.     {  
66. "Stack is empty.../n");  
67. return;  
68.     }  
69. "printf the items of stack.../n");  
70. for(i=ps->top;i>-1;i--)  
71. "%4d", ps->data[i]);  
72. "/n/n");  
73. }  
74. void main()  
75. {  
76. int i, num, data, *pdata;  
77.     pstack ps;  
78.     ps=init_stack();  
79. "Enter stack num:");  
80. "%d", &num);  
81. for(i=0;i

1. #include   
2. #include   
3. typedef char DataType;  
4. struct _node  
5. {  
6.     DataType data;  
7. struct _node *next;  
8. };  
9. typedef struct _node node, *pstack;  
10. pstack init_stack()  
11. {  
12.     pstack ps;  
13. sizeof(node));  
14. if(NULL == ps)  
15.     {  
16. "Error. malloc is fail.../n");  
17. return NULL;  
18.     }  
19. /* base of stack: data=-1 and next=NULL */  
20.     ps->next=NULL;  
21. return ps;  
22. }  
23. pstack push(pstack ps, DataType data)  
24. {  
25.     pstack ptop;  
26. sizeof(node));  
27. if(NULL == ptop)  
28.     {  
29. "Error. malloc is fail.../n");  
30. return NULL;  
31.     }  
32.     ptop->data=data;  
33. /* insert new item */  
34. /* move top */  
35. return ps;  
36. }  
37. pstack pop(pstack ps, DataType *data)  
38. {  
39. if(ps->next == NULL)  
40.     {  
41. "stack is empty.../n");  
42. return NULL;              
43.     }  
44.     *data=ps->data;  
45.     ps=ps->next;  
46. return ps;  
47. }  
48. DataType top_stack(pstack ps)  
49. {  
50. if(ps->next == NULL)  /* if empty */  
51.     {  
52. "stack is empty.../n");  
53. return -1;  
54.     }  
55. return ps->data;  
56. }  
57. int len_stack(pstack ps)  
58. {  
59. int len=0;  
60.     pstack ptop=ps;  
61. while(ptop->next)  
62.     {  
63.         len++;  
64.         ptop=ptop->next;  
65.     }  
66. return len;  
67. }  
68. void display(pstack ps)  
69. {  
70.     pstack ptop;  
71.     ptop=ps;  
72. while(ptop->next != NULL)  
73.     {  
74. "%4c", ptop->data);  
75.         ptop=ptop->next;  
76.     }  
77. "/n/n");  
78. }  
79. void main()  
80. {  
81.     pstack ps;  
82. sizeof(DataType));  
83.     ps=init_stack();  
84. 'a');  
85. 'b');  
86. 'c');  
87. 'd');  
88. 'e');  
89.     display(ps);  
90. "len of stack is: %d/n/n", len_stack(ps));  
91. "top of stack is: %c/n/n", top_stack(ps));  
92.     ps=pop(ps, data);  
93. "pop %c/n",*data);  
94.     display(ps);  
95.     ps=pop(ps, data);  
96. "pop %c/n",*data);  
97.     display(ps);  
98.     getch();  
99. }

1. #include   
2. #include   
3. #include   
4. struct _node  
5. {  
6. int data;  
7. struct _node *next;  
8. };  
9. typedef struct _node node, *pnode;  
10. struct _linkqueue  
11. {  
12.     pnode front;  
13.     pnode rear;      
14. };  
15. typedef struct _linkqueue linkqueue, *plinkqueue;  
16. linkqueue init_queue()  
17. {  
18.     linkqueue lq;  
19. sizeof(node));  
20. if(NULL == lq.front)  
21.     {  
22. "Error. malloc is fail.../n");  
23.         exit(1);  
24.     }  
25.     lq.rear->data=lq.front->data=-1;  
26.     lq.rear->next=lq.front->next=NULL;  
27. return lq;  
28. }  
29. int empty_queue(linkqueue lq)  
30. {  
31. if(lq.front == lq.rear)  
32. return 1;  
33. else  
34. return 0;  
35. }  
36. linkqueue insert_item(linkqueue lq, int data)  
37. {  
38.     pnode pq;  
39. sizeof(node));  
40. if(pq == NULL)  
41.     {  
42. "Error. malloc is fail.../n");  
43.         exit(1);  
44.     }  
45.     pq->data=data;  
46.     pq->next=lq.rear->next;  
47.     lq.rear->next=pq;  
48.     lq.rear=lq.rear->next;  
49. return lq;  
50. }  
51. linkqueue delete_item(linkqueue lq, int *data)  
52. {  
53. if(empty_queue(lq))  
54.     {  
55. "queue is empty.../n");  
56.         exit(1);  
57.     }  
58.     *data=lq.front->data;  
59.     lq.front=lq.front->next;  
60. return lq;  
61. }  
62. int len_queue(linkqueue lq)  
63. {  
64. int len=0;  
65. while(lq.front)  
66.     {  
67.         len++;  
68.         lq.front=lq.front->next;  
69.     }  
70. return len;  
71. }  
72. void display(linkqueue lq)  
73. {  
74.     linkqueue p;  
75.     p=lq;  
76. if(empty_queue(lq))  
77.     {  
78. "queue is empty.../n");  
79. return;  
80.     }  
81. while(p.front->next)  
82.     {  
83. "%4d", p.front->data);  
84.         p.front=p.front->next;  
85.     }  
86. "%4d/n/n", p.front->data);  
87. }  
88. void main()  
89. {  
90. int *data = (int *)malloc(sizeof(int));  
91.     linkqueue lq;  
92.     lq=init_queue();  
93.     lq=insert_item(lq, 1);  
94.     lq=insert_item(lq, 2);  
95.     lq=insert_item(lq, 3);  
96.     lq=insert_item(lq, 4);  
97.     lq=insert_item(lq, 5);  
98.     display(lq);  
99. "len of queue is: %d/n/n", len_queue(lq));  
100.     lq=delete_item(lq, data);  
101. "delete %d/n", *data);  
102.     display(lq);  
103.     lq=delete_item(lq, data);  
104. "delete %d/n", *data);  
105.     display(lq);  
106.     getch();  
107. }