C语言实现staque结构
1. 使用说明
staque结构以单链表方式实现，结合了stack与queue结构：pop_front+push_front使用方式为stack；pop_front+push_back使用方式是queue。
首尾插入和顶部弹出是运行效率最高的，此外还实现了任意位置的插入、移除和访问功能。
带有返回值的函数：返回值如果是void*类型，则NULL代表执行失败；如果是int类型，则0为成功，-1为失败。
2. 代码实现
staque.h
1 #ifndef __STAQUE_H 2 #define __STAQUE_H 3 4 typedef 5 struct unidirectional_node 6 { 7 void* p_data; 8 struct unidirectional_node* p_next; 9 }STRUCT_UD_NODE,10 * P_STRUCT_UD_NODE;11 12 typedef13 struct staque14 {15 unsigned int count;16 P_STRUCT_UD_NODE p_first;17 P_STRUCT_UD_NODE p_last;18 }STRUCT_STAQUE,19 * P_STRUCT_STAQUE;20 21 P_STRUCT_STAQUE22 f_staque_construct(void);23 24 void25 f_staque_push_back(P_STRUCT_STAQUE const p_stq, void* const p_data);26 27 void28 f_staque_push_front(P_STRUCT_STAQUE const p_stq, void* const p_data);29 30 void*31 f_staque_pop_front(P_STRUCT_STAQUE const p_stq);32 33 int34 f_staque_data_insert(P_STRUCT_STAQUE const p_stq, void* const p_data, const unsigned int index);35 36 void*37 f_staque_data_remove(P_STRUCT_STAQUE const p_stq, const unsigned int index);38 39 void*40 f_staque_data_access(P_STRUCT_STAQUE const p_stq, const unsigned int index);41 42 int43 f_staque_data_index(P_STRUCT_STAQUE const p_stq, void* const p_data, unsigned int* const p_index);44 45 void46 f_staque_destroy(P_STRUCT_STAQUE const p_stq);47 48 #endif // !__STAQUE_H
head
staque.c
1 #include "staque.h" 2 #include 3 4 #pragma warning(disable:6011) 5 6 P_STRUCT_STAQUE f_staque_construct(void) 7 { 8 P_STRUCT_STAQUE p_ret_vec = (P_STRUCT_STAQUE)malloc(sizeof(STRUCT_STAQUE)); 9 p_ret_vec->count = 0; 10 p_ret_vec->p_first = NULL; 11 p_ret_vec->p_last = NULL; 12 return p_ret_vec; 13 } 14 15 void innf_add_first_node(P_STRUCT_STAQUE const p_stq, void* const p_data) 16 { 17 p_stq->p_first = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 18 p_stq->p_first->p_data = p_data; 19 p_stq->p_first->p_next = NULL; 20 p_stq->p_last = p_stq->p_first; 21 p_stq->count = 1; 22 } 23 24 void* innf_remove_last_node(P_STRUCT_STAQUE const p_stq) 25 { 26 void* p_ret_data = p_stq->p_first->p_data; 27 free(p_stq->p_first); 28 p_stq->p_first = NULL; 29 p_stq->p_last = NULL; 30 p_stq->count = 0; 31 return p_ret_data; 32 } 33 34 void f_staque_push_back(P_STRUCT_STAQUE const p_stq, void* const p_data) 35 { 36 switch (p_stq->count) 37 { 38 case 0: 39 innf_add_first_node(p_stq, p_data); 40 return; 41 } 42 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 43 p_node->p_data = p_data; 44 p_node->p_next = NULL; 45 p_stq->p_last->p_next = p_node; 46 p_stq->p_last = p_node; 47 p_stq->count++; 48 } 49 50 void f_staque_push_front(P_STRUCT_STAQUE const p_stq, void* const p_data) 51 { 52 switch (p_stq->count) { 53 case 0: 54 innf_add_first_node(p_stq, p_data); 55 return; 56 } 57 P_STRUCT_UD_NODE p_node = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE)); 58 p_node->p_data = p_data; 59 p_node->p_next = p_stq->p_first; 60 p_stq->p_first = p_node; 61 p_stq->count++; 62 } 63 64 void* f_staque_pop_front(P_STRUCT_STAQUE const p_stq) 65 { 66 switch (p_stq->count) { 67 case 0: 68 return NULL; 69 case 1: 70 return innf_remove_last_node(p_stq); 71 } 72 void* p_ret_data = p_stq->p_first->p_data; 73 P_STRUCT_UD_NODE p_node = p_stq->p_first->p_next; 74 free(p_stq->p_first); 75 p_stq->p_first = p_node; 76 p_stq->count--; 77 return p_ret_data; 78 } 79 80 int f_staque_data_insert(P_STRUCT_STAQUE const p_stq, void* const p_data, const unsigned int index) 81 { 82 switch (index) { 83 case 0: 84 f_staque_push_front(p_stq, p_data); 85 return 0; 86 } 87 if (index == p_stq->count) { 88 f_staque_push_back(p_stq, p_data); 89 return 0; 90 } 91 else if (index > p_stq->count) { 92 return -1; 93 } 94 P_STRUCT_UD_NODE p_node = p_stq->p_first; 95 for (unsigned int i = 0 ; i < index - 1; i++) { 96 p_node = p_node->p_next; 97 } 98 P_STRUCT_UD_NODE p_node_next = p_node->p_next; 99 p_node->p_next = (P_STRUCT_UD_NODE)malloc(sizeof(STRUCT_UD_NODE));100 p_node->p_next->p_data = p_data;101 p_node->p_next->p_next = p_node_next;102 p_stq->count++;103 return 0;104 }105 106 void* f_staque_data_remove(P_STRUCT_STAQUE const p_stq, const unsigned int index)107 {108 switch (p_stq->count) {109 case 0:110 return NULL;111 }112 switch (index) {113 case 0:114 return f_staque_pop_front(p_stq);115 }116 if (index >= p_stq->count) {117 return NULL;118 }119 P_STRUCT_UD_NODE p_node = p_stq->p_first;120 for (unsigned int i = 0; i < index - 1; i++) {121 p_node = p_node->p_next;122 }123 P_STRUCT_UD_NODE p_node_next = p_node->p_next->p_next;124 void* p_ret_data = p_node->p_next->p_data;125 free(p_node->p_next);126 p_node->p_next = p_node_next;127 p_stq->count--;128 return p_ret_data;129 }130 131 void* f_staque_data_access(P_STRUCT_STAQUE const p_stq, const unsigned int index)132 {133 switch (p_stq->count) {134 case 0:135 return NULL;136 }137 if (index >= p_stq->count) {138 return NULL;139 }140 P_STRUCT_UD_NODE p_node = p_stq->p_first;141 for (unsigned int i = 0; i < index; i++) {142 p_node = p_node->p_next;143 }144 return p_node->p_data;145 }146 147 int f_staque_data_index(P_STRUCT_STAQUE const p_stq, void* const p_data, unsigned int* const p_index)148 {149 P_STRUCT_UD_NODE p_node = p_stq->p_first;150 for (unsigned int i = 0; icount; i++) {151 if (p_node->p_data == p_data) {152 *p_index = i;153 return 0;154 }155 p_node = p_node->p_next;156 }157 return -1;158 }159 160 void f_staque_destroy(P_STRUCT_STAQUE const p_stq)161 {162 if (p_stq == NULL) {163 return;164 }165 while (p_stq->count != 0) {166 f_staque_pop_front(p_stq);167 }168 free(p_stq);169 }
code
3. 代码测试
source.c
1 #include "staque.h" 2 #include 3 #include 4 5 #pragma warning(disable:6011) 6 7 int main(int argc, char** argv) 8 { 9 P_STRUCT_STAQUE p_stq = f_staque_construct();10 const unsigned int arr_size = 10;11 int* arr = (int*)malloc(sizeof(int) * arr_size);12 printf("arr: ");13 for (unsigned int i = 0; i < arr_size; i++) {14 *(arr + i) = i * 2;15 printf("%d ", *(arr + i));16 }17 printf("\nstaque push back all\n");18 for (unsigned int i = 0; i < arr_size; i++) {19 f_staque_push_back(p_stq, arr + i);20 }21 printf("access staque data\n");22 for (unsigned int i = 0; icount; i++) {23 printf("%d ", *(int*)f_staque_data_access(p_stq, i));24 }25 printf("\nstaque push front all\n");26 for (unsigned int i = 0; i < arr_size; i++) {27 f_staque_push_front(p_stq, arr + i);28 }29 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {30 printf("%d ", *(int*)p_node->p_data);31 }32 printf("\ninsert to half\n");33 f_staque_data_insert(p_stq, &p_stq->count, p_stq->count / 2);34 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {35 printf("%d ", *(int*)p_node->p_data);36 }37 unsigned int index = 0;38 f_staque_data_index(p_stq, &p_stq->count, &index);39 printf("\nget index of that node: %d", index);40 printf("\nremove half: %d\n", *(int*)f_staque_data_remove(p_stq, p_stq->count / 2));41 for (P_STRUCT_UD_NODE p_node = p_stq->p_first; p_node != NULL; p_node = p_node->p_next) {42 printf("%d ", *(int*)p_node->p_data);43 }44 printf("\nstaque pop front all\n");45 while (p_stq->count != 0) {46 printf("%d ", *(int*)f_staque_pop_front(p_stq));47 }48 printf("\n");49 f_staque_destroy(p_stq);50 free(arr);51 return 0;52 }
test
运行结果：
arr: 0 2 4 6 8 10 12 14 16 18
staque push back all
access staque data
0 2 4 6 8 10 12 14 16 18
staque push front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
insert to half
18 16 14 12 10 8 6 4 2 0 21 0 2 4 6 8 10 12 14 16 18
get index of that node: 10
remove half: 20
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18
staque pop front all
18 16 14 12 10 8 6 4 2 0 0 2 4 6 8 10 12 14 16 18