**队列** ``` #include #include #define initialVal 0 typedef struct Node{ int data; struct Node *next ; }LinkedQueue; void push(LinkedQueue *queue , int data){ if (queue -> next == NULL){ queue -> next = (struct Node *) malloc(sizeof(struct Node)); queue -> next -> data = data ; } else{ struct Node *node = queue ; while (1){ if (node -> next == NULL){ node -> next = (struct Node *) malloc(sizeof(struct Node)); node -> next -> next = NULL ; node -> next -> data = data; break ; } node = node -> next ; } } } struct Node * pop(LinkedQueue *queue){ if (queue == NULL)return NULL; struct Node *first = queue -> next ; queue -> next = queue -> next -> next ; return first ; } LinkedQueue * getLinkedQueue(){ //初始化队头 struct Node *first = (LinkedQueue * ) malloc(sizeof(LinkedQueue)); first -> data = initialVal ; first -> next = NULL ; return first ; } void printfQueue(LinkedQueue *queue){ struct Node * node = queue -> next; while (node != NULL){ printf("%d ",node -> data) ; node = node -> next ; } printf("\n"); } int main() { LinkedQueue *queue = getLinkedQueue(); for (int i = 1; i < 11; ++i) { push(queue , i); } printfQueue(queue); for (int i = 0; i < 6; ++i) { printf("%d \n" , pop(queue) -> data ) ; printfQueue(queue); } } ``` ![图片描述](https://dn-simplecloud.shiyanlou.com/courses/uid1569360-20210628-1624810820975) **链式存储实现栈** ``` #include #include #define initialization_val 0 #define initialization_size 0 /** * 我还是希望存在能按索引获取节点的方式，所以我依旧存在一个 size 也是栈的容量 */ typedef struct LinkedStack{ int val ; int size ; struct LinkedStack *next ; }Node; void push(Node *head , int val){ if (head -> next == NULL){ head -> next = (Node*)malloc(sizeof(Node)) ; head -> next -> next = NULL ; head -> next -> val = val ; (head -> next -> size) = 1 ; } else{ Node *temporaryNode = head ; while (1){ if (temporaryNode -> next == NULL){ temporaryNode -> next = (Node*)malloc(sizeof(Node)); temporaryNode -> next -> next = NULL ; temporaryNode -> next -> size = ((temporaryNode -> size) + 1); temporaryNode -> next -> val = val ; break; } temporaryNode = temporaryNode -> next ; } } } /** * 单向链表模拟栈的弹栈是比较耗时的（因为每次都得从head去遍历一次，原因就是因为单向，如果是双向可以直接从last删除尾节点并返回） * @param head * @return */ Node * poll(Node *head){ if (head -> next == NULL){ return NULL; } Node *node = head -> next; if (node -> next == NULL){ node -> next = NULL ; return node ; } while (1){ if (node -> next -> next == NULL){ Node *pollNode = node -> next ; node -> next = NULL ; return pollNode; } node = node -> next ; } } /** * 初始化链表表头 * @return */ Node * getHead(){ Node *head = (Node*)malloc(sizeof(Node)); head -> val = initialization_val; head -> size = initialization_size; head -> next = NULL; return head; } /*============================================基于双向链表实现的栈===============================================================================*/ typedef struct TwoWayLinkedStack{ int val ; int size ; struct TwoWayLinkedStack *next ; struct TwoWayLinkedStack *pre ; }node; struct TwoWayLinkedStack *last; void pushTwo(node *head , int val){ if (head -> next == NULL){ head -> next = (node*)malloc(sizeof(node)) ; head -> next -> next = NULL ; head -> next -> pre = NULL ; head -> next -> val = val ; (head -> next -> size) ++ ; last = head -> next ; } else{ node *temporaryNode = head ; while (1){ if (temporaryNode -> next == NULL){ temporaryNode -> next = (node*)malloc(sizeof(node)); temporaryNode -> next -> next = NULL ; temporaryNode -> next -> pre = temporaryNode ; temporaryNode -> next -> size = ((temporaryNode -> size) + 1); temporaryNode -> next -> val = val ; last = temporaryNode -> next ; break; } temporaryNode = temporaryNode -> next ; } } } node * pollTwo(){ node *temporaryNode = last ; last = last -> pre ; last -> next = NULL ; temporaryNode -> pre = NULL ; return temporaryNode ; } node * getHeadTwo(){ node *head = (node*)malloc(sizeof(node)); head -> val = initialization_val; head -> size = initialization_size; head -> next = NULL; return head; } int main(){ Node *head = getHead(); for (int i = 1; i < 11; ++i) { push(head , i); } Node *pollNode = poll(head); printf("pollNode : val = %d size = %d \n" , pollNode -> val , pollNode -> size); node *headTwo = getHeadTwo(); for (int i = 1; i < 11; ++i) { pushTwo(headTwo , i); } node *pollTwoNode = pollTwo(); printf("pollTwoNode : val = %d size = %d \n" , pollTwoNode -> val , pollTwoNode -> size); } ``` **线性存储实现栈** ``` #include #include #define initial_Capacity 10 #define MAX_CAPACITY 0x80000000 #define initial_size 0 #define initial_length 0 struct ArrayStack{ int *data ; int *top ; int size ; int Capacity; }; void push(struct ArrayStack *stack , int data){ if (stack->size >= stack->Capacity){ /* * 这里的扩容法则借鉴了 java ArrayList的源码扩容机制我正好也在研究 * 每次扩容大约是 1.5 倍 */ int goodGrow = ((stack->size)+1) > ((stack->Capacity) >> 1) ? (stack -> size) + 1 : (stack->Capacity) ; int newCapacity = goodGrow + (stack -> Capacity); //overflow 溢出！ if (newCapacity < 0){ stack -> data = (int *)realloc(stack -> data , MAX_CAPACITY * sizeof(int)); } else{ stack -> data = (int *)realloc(stack -> data , newCapacity * sizeof(int)); } if (!stack -> data){ exit(0); } } *((stack -> data)+(stack -> size)) = data ; stack -> top = (stack -> data)+(stack -> size) ; stack -> size ++ ; } int * poll(struct ArrayStack *stack){ int *top = stack -> top ; stack -> top = ((stack -> data) + ((stack -> size) -2)) ; stack -> size -- ; return top ; } struct ArrayStack * getArrayStack(){ struct ArrayStack *stack = (struct ArrayStack*)malloc(sizeof(struct ArrayStack)) ; stack -> data = (int*)malloc(initial_Capacity * sizeof(int)) ; stack -> top = initial_size ; stack -> size = initial_length ; stack -> Capacity = initial_Capacity ; return stack ; } void printfStack(struct ArrayStack *stack){ for (int i = 0; i < stack -> size ; ++i) { printf(" %d " , *(stack ->data +i)); } printf("\n"); } int main(){ struct ArrayStack *stack = getArrayStack(); for (int i = 0; i < 20; ++i) { push(stack,i); } printfStack(stack); for (int i = 0; i < 5; ++i) { printf("%d \n",*poll(stack)); printfStack(stack); } } ``` ![图片描述](https://dn-simplecloud.shiyanlou.com/courses/uid1569360-20210628-1624811028959)

“数据结构实验”实验报告