快速解析 栈和队列

栈：      定义：          后进先出的线性表，只能在表尾进行删除和插入操作         ——表尾：栈顶（top）， 表头：栈底（bottom）      栈的顺序存储结构：           typedef struct{ ElemType *base; ElemType *top; int stackSize;}sqStack;      其中，base 是指向栈底的指针变量，top 是指向栈顶的指针变量， stackSize 指示栈的当前可使用的最大容量         创建栈：           #define STACK_INIT_SIZE 100initStack(sqStack *s){ s -> base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s -> base) exit(0); s -> top = s -> base; s -> stackSize = STACK_INIT_SIZE;}      压栈操作： #define STACKINCREMENT 10Push(sqStack *s, ElemType e){ if( s-> top - s -> base >= s -> stackSize) { s -> base = (ElemType *)realloc(s -> base, (s -> stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s -> base) exit(0); s -> top = s -> base + s -> stackSize; s -> stackSize = s -> stackSize + STACKINCREMENT; } *(s -> top) = e; s -> top ++;}      出栈操作： Pop(sqStack *s, ElemType *e){ if(s -> top == s -> base) //栈空 return ; *e = *--(s -> top);}      清空栈：            只要将 s -> top 的内容赋值为 s -> base 即可，就表明这个栈是空的了。 ClearStack(sqStack *s){ s -> top = s -> base;}      销毁栈： DestroyStack(sqStack *s){ int i, len; len = s -> stackSize; for(i = 0; i < len; i++){ free(s -> base); s -> base ++; } s -> base = s -> top = NULL; s -> stackSize = 0;}      注意：销毁栈和清空栈不同，销毁栈是要释放掉该栈所占据的物理内存空间      栈的链式存储结构：   typedef struct StackNode{ ElemType data; //存放栈的数据 struct StackNode *next;}StackNode, *LinkStackPtr;typedef struct LinkStack{ LinkStackPrt top; //top指针 int count; //栈元素计数器}  计算栈的当前容量： int StackLen(sqStack s){ return (s.top - s.base);} 队列：      在一端进行插入操作，在另一端进行删除操作的线性表      队列的链式存储结构：   typedef struct QNode{ ElemType *data; struct QNode *next;}QNode, *QueuePrt;typedef struct{ QueuePrt front, rear; //队头、尾指针}LinkQueue;       创建队列： initQueue(LinkQueue *q){ q -> front = q -> rear = (QueuePtr)malloc(sizeof(QNode)); if(!q -> front) exit(0); q -> front -> next = NULL;}       入队列操作： InsertQueue(LinkQueue *q, ElemType e){ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if(p == NULL) exit(0); p -> data = e; p -> next = NULL; q -> rear -> next = p; q -> rear = p;}      出队列操作： DeleteQueue(LinkQueue *q, ElemType *e){ QueuePtr p; if(q -> front == q -> rear) return; p = q -> front -> next; *e = p -> data; q -> front -> next = p -> next; if(q -> rear == p) q -> rear = q -> front; free(p);}       销毁队列操作： DestoryQueue(LinkQueue *q){ while(q -> front){ q -> rear = q -> front -> next; free(q -> front); q -> front = q -> rear; }}       循环队列：          循环队列的容量是固定的，它的队头和队尾指针都可以随着元素出入队列而发生变化，这样循环队列逻辑上就好像是一个环形存储空间。          循环队列的尾指针 rear 将指向下一个存储单元       定义循环队列： #define MAXSIZE 100typedef struct{ ElemType *base;//用于存放内存分配基地址 int front; int rear;}      初始化循环队列： initQueue(cycleQueue *q){ q -> base = (ElemType *)malloc(MAXSIZE *sizeof(ElemType)); if(!q -> base) exit(0); q -> front = q -> rear = 0;}       入队操作： InsertQueue(cycleQueue *q, ElemType e){ if((q -> rear + 1) % MAXSIZE == q -> front) return ; q -> base[q -> rear] = e; q -> rear = (q -> rear + 1) % MAXSIZE;}       出队操作： DeleteQueue(cycleQueue *q, ElemType *e){ if(q -> front == q -> rear) return ; *e = q -> base[q -> front]; q -> front = (q -> front + 1) % MAXSIZE;}   栈：      定义：          后进先出的线性表，只能在表尾进行删除和插入操作         ——表尾：栈顶（top）， 表头：栈底（bottom）      栈的顺序存储结构：           typedef struct{ ElemType *base; ElemType *top; int stackSize;}sqStack;      其中，base 是指向栈底的指针变量，top 是指向栈顶的指针变量， stackSize 指示栈的当前可使用的最大容量         创建栈：           #define STACK_INIT_SIZE 100initStack(sqStack *s){ s -> base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if(!s -> base) exit(0); s -> top = s -> base; s -> stackSize = STACK_INIT_SIZE;}      压栈操作： #define STACKINCREMENT 10Push(sqStack *s, ElemType e){ if( s-> top - s -> base >= s -> stackSize) { s -> base = (ElemType *)realloc(s -> base, (s -> stackSize + STACKINCREMENT) * sizeof(ElemType)); if(!s -> base) exit(0); s -> top = s -> base + s -> stackSize; s -> stackSize = s -> stackSize + STACKINCREMENT; } *(s -> top) = e; s -> top ++;}      出栈操作： Pop(sqStack *s, ElemType *e){ if(s -> top == s -> base) //栈空 return ; *e = *--(s -> top);}      清空栈：            只要将 s -> top 的内容赋值为 s -> base 即可，就表明这个栈是空的了。 ClearStack(sqStack *s){ s -> top = s -> base;}      销毁栈： DestroyStack(sqStack *s){ int i, len; len = s -> stackSize; for(i = 0; i < len; i++){ free(s -> base); s -> base ++; } s -> base = s -> top = NULL; s -> stackSize = 0;}      注意：销毁栈和清空栈不同，销毁栈是要释放掉该栈所占据的物理内存空间      栈的链式存储结构：   typedef struct StackNode{ ElemType data; //存放栈的数据 struct StackNode *next;}StackNode, *LinkStackPtr;typedef struct LinkStack{ LinkStackPrt top; //top指针 int count; //栈元素计数器}  计算栈的当前容量： int StackLen(sqStack s){ return (s.top - s.base);} 队列：      在一端进行插入操作，在另一端进行删除操作的线性表      队列的链式存储结构：   typedef struct QNode{ ElemType *data; struct QNode *next;}QNode, *QueuePrt;typedef struct{ QueuePrt front, rear; //队头、尾指针}LinkQueue;       创建队列： initQueue(LinkQueue *q){ q -> front = q -> rear = (QueuePtr)malloc(sizeof(QNode)); if(!q -> front) exit(0); q -> front -> next = NULL;}       入队列操作： InsertQueue(LinkQueue *q, ElemType e){ QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if(p == NULL) exit(0); p -> data = e; p -> next = NULL; q -> rear -> next = p; q -> rear = p;}      出队列操作： DeleteQueue(LinkQueue *q, ElemType *e){ QueuePtr p; if(q -> front == q -> rear) return; p = q -> front -> next; *e = p -> data; q -> front -> next = p -> next; if(q -> rear == p) q -> rear = q -> front; free(p);}       销毁队列操作： DestoryQueue(LinkQueue *q){ while(q -> front){ q -> rear = q -> front -> next; free(q -> front); q -> front = q -> rear; }}       循环队列：          循环队列的容量是固定的，它的队头和队尾指针都可以随着元素出入队列而发生变化，这样循环队列逻辑上就好像是一个环形存储空间。          循环队列的尾指针 rear 将指向下一个存储单元       定义循环队列： #define MAXSIZE 100typedef struct{ ElemType *base;//用于存放内存分配基地址 int front; int rear;}      初始化循环队列： initQueue(cycleQueue *q){ q -> base = (ElemType *)malloc(MAXSIZE *sizeof(ElemType)); if(!q -> base) exit(0); q -> front = q -> rear = 0;}       入队操作： InsertQueue(cycleQueue *q, ElemType e){ if((q -> rear + 1) % MAXSIZE == q -> front) return ; q -> base[q -> rear] = e; q -> rear = (q -> rear + 1) % MAXSIZE;}       出队操作： DeleteQueue(cycleQueue *q, ElemType *e){ if(q -> front == q -> rear) return ; *e = q -> base[q -> front]; q -> front = (q -> front + 1) % MAXSIZE;}