前言 ：
栈和队列的实现与链表的实现很相似，新瓶装旧酒，没什么新东西。
可以参考这篇文章：
-------------------------无头单向不循环链表和带头双向循环链表的创建---------------------------
栈
逻辑图：
这里我们写顺序栈，不写链栈，因为栈数据的插入只能从栈顶入，栈顶出，这里链栈的优势就没有了，而大多数人所认为的另一个优势是顺序栈容易满？我们难道不能动态开一个，写一个checkcapacity吗，让他满了自动扩容，虽然有空间的损失，但这个并不是什么问题。再一个顺序栈的开辟与释放更为简单，直接释放掉动态开辟的数组空间就好。（当然，链栈也有其优势，但我更认可顺序栈）
头文件：
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int DataType; typedef struct Stack { DataType* data; int top; int capacity; }Stack; void Init(Stack *st); void Push(Stack* st, DataType x); void Pop(Stack* st); DataType GetTop(Stack* st); bool Empty(Stack* st); void Destroy(Stack* st); int Size(Stack* st);
Test文件(main)：
#include "join_stack.h" void Test(); int main() { Test(); return 0; } void Test() { Stack st; Init(&st); Push(&st, 1); Push(&st, 2); Push(&st, 3); Push(&st, 4); Push(&st, 5); Push(&st, 6); printf("size = %d\n", Size(&st)); while (!Empty(&st)) { printf("%d ", GetTop(&st)); Pop(&st); } putchar('\n'); Destroy(&st); }
函数源文件：
#include "join_stack.h" void Init(Stack* st) { assert(st); st->data = NULL; st->top = 0; st->capacity = 0; } void Push(Stack* st, DataType x) { assert(st); if (st->capacity == st->top) { int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2; DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity); if (temp == NULL) { perror("realloc fail"); exit(-1); } st->data = temp; st->capacity = newcapacity; } st->data[st->top++] = x; } void Pop(Stack* st) { assert(st); assert(st->top > 0); st->top--; } DataType GetTop(Stack* st) { assert(st); assert(st->top > 0); return st->data[st->top - 1]; } bool Empty(Stack* st) { assert(st); return (st->top == 0); } void Destroy(Stack* st) { assert(st); free(st->data); st->data = NULL; st->top = st->capacity = 0; } int Size(Stack* st) { assert(st); return st->top; }
队列
逻辑图：
队列我们就用链式结构，这和链表非常像，只是不能在中间插入，而且只能尾进头出。
头文件：
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int DataType; typedef struct Queue { DataType data; struct Queue *next; }Queue; typedef struct Q { Queue* head; Queue* tail; int size; }Q; void Init(Q *qq); void Destroy(Q* qq); void QueuePush(Q* qq, DataType x); void QueuePop(Q* qq); DataType GetQueueFrontNum(Q* qq); DataType GetQueueBackNum(Q* qq); bool Empty(Q* qq); int Size(Q* qq);
Test文件(main):
#define _CRT_SECURE_NO_WARNINGS 1 #include "newQueue.h" void Test(); int main() { Test(); return 0; } void Test() { Q qq; Init(&qq); QueuePush(&qq, 1); QueuePush(&qq, 2); QueuePush(&qq, 3); printf("%d ", GetQueueFrontNum(&qq)); QueuePop(&qq); printf("%d \n", GetQueueFrontNum(&qq)); QueuePush(&qq, 3); QueuePush(&qq, 4); QueuePush(&qq, 5); int head_num = GetQueueFrontNum(&qq); int tail_num = GetQueueBackNum(&qq); printf("%d %d\n", head_num, tail_num); printf("size = %d\n", Size(&qq)); Destroy(&qq); }
函数源文件：
#define _CRT_SECURE_NO_WARNINGS 1 #include "newQueue.h" void Init(Q* qq) { assert(qq); qq->head = NULL; qq->tail = NULL; qq->size = 0; } void QueuePush(Q* qq, DataType x) { assert(qq); Queue* temp = (Queue*)malloc(sizeof(Queue)); if (temp == NULL) { perror("malloc fail"); exit(-1); } temp->data = x; temp->next = NULL; if (qq->tail == NULL) qq->head = qq->tail = temp; else { qq->tail->next = temp; qq->tail = temp; } qq->size++; } void QueuePop(Q* qq) { assert(qq); assert(!Empty(qq)); if (qq->head == qq->tail) { free(qq->head); qq->head = qq->tail = NULL; } else { Queue* next = qq->head->next; free(qq->head); qq->head = next; } qq->size--; } DataType GetQueueFrontNum(Q* qq) { assert(qq); assert(!Empty(qq)); return qq->head->data; } DataType GetQueueBackNum(Q* qq) { assert(qq); assert(!Empty(qq)); return qq->tail->data; } bool Empty(Q* qq) { assert(qq); return qq->size == 0; } void Destroy(Q* qq) { assert(qq); Queue *cur = qq->head; while(cur) { Queue *next = cur->next; free(cur); cur = next; } qq->head = qq->tail = NULL; qq->size = 0; } int Size(Q* qq) { assert(qq); return qq->size; }
