数据结构——栈与队列的功能实现

头文件"SqStackQueue.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #include <stdio.h> #include <stdlib.h> typedef char ElemType; typedef int Status; typedef struct { ElemType* base; ElemType* top; int stacksize; }SqStack; Status InitStack(SqStack &S); Status DestroyStack(SqStack& S); Status ClearStack(SqStack& S); Status GetTop(SqStack S, ElemType& e); Status Push(SqStack& S, ElemType e); Status Pop(SqStack& S, ElemType& e); Status StackEmpty(SqStack S); typedef struct { ElemType* base; int front; int rear; }SqQueue; Status InitQueue_Sq(SqQueue& Q); Status EnQueue_Sq(SqQueue& Q, ElemType e); Status DeQueue_Sq(SqQueue& Q, ElemType& e); Status GetHead(SqQueue Q, ElemType& e); Status QueueEmpty(SqQueue Q); Status DestroyQueue(SqQueue& Q); Status ClearQueue(SqQueue& Q); 栈的功能实现StackFun.c #include "SqStackQueue.h" Status InitStack(SqStack& S) { //构造一个空栈S S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));//为顺序栈动态分配储存空间 if (!S.base) exit(OVERFLOW); //空间分配失败 S.top = S.base; //空栈的条件：S.top == S.base S.stacksize = STACK_INIT_SIZE; return OK; }//初始化一个空栈 Status DestroyStack(SqStack& S) { if (!S.base) return ERROR; //栈为未建立（尚未分配存储空间） free(S.base); //回收栈空间 S.base = S.top = NULL; S.stacksize = 0; return OK; }//销毁操作 Status ClearStack(SqStack& S) { //将S置为空栈 if (!S.base) return ERROR; //栈为未建立（尚未分配存储空间） S.top = S.base; return OK; }//置空操作算法 Status GetTop(SqStack S, ElemType& e) { if (S.top == S.base) return ERROR; //栈空 e = *(S.top - 1); return OK; }//取栈顶元素操作 Status Push(SqStack& S, ElemType e) { //元素进栈 //将元素e插入栈中，使其成为新的栈顶元素 if (S.top - S.base >= S.stacksize) {//栈满，追加储存空间 S.base = (ElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType)); if (!S.base) exit(OVERFLOW);//存储分配失败 S.top = S.base + S.stacksize;//存储空间增大后修改top指针 S.stacksize += STACKINCREMENT; } *S.top++ = e;//元素e进栈顶，然后修改top指针，top++，指向下一个空间 return OK; }//进栈操作算法 Status Pop(SqStack& S, ElemType& e) { if (S.top == S.base) return ERROR;//栈空 e = *--S.top;//先--S.top，再将*S.top赋值给e return OK; }//出栈操作算法 Status StackEmpty(SqStack S) { if (S.top == S.base) return OK; else return ERROR; } 循环队列功能实现QueueFun.c #include "SqStackQueue.h" Status InitQueue_Sq(SqQueue& Q) { //构造一个空队列Q Q.base = (ElemType*)malloc(MAXSIZE * sizeof(ElemType)); if (!Q.base) exit(OVERFLOW); Q.front = Q.rear = 0; return OK; }//构造空队列 Status EnQueue_Sq(SqQueue& Q, ElemType e) { //将元素e插入队尾 if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;//队满 Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXSIZE; return OK; }//入队操作 Status DeQueue_Sq(SqQueue& Q, ElemType& e) { //删除队头元素，用e返回其值，并返回OK；否则返回ERROR if (Q.rear == Q.front) return ERROR;//队空 e = Q.base[Q.front];//取队头元素e Q.front = (Q.front + 1) % MAXSIZE;//修改队头指针 return OK; }//出队操作 Status GetHead(SqQueue Q, ElemType& e) { if (Q.rear == Q.front) return ERROR;//队空 e = Q.base[Q.front]; return OK; }//取队头算法 Status QueueEmpty(SqQueue Q) { if (Q.rear == Q.front) return OK;//队空 else return ERROR; }//判空算法 Status DestroyQueue(SqQueue& Q) { if (!Q.base) return ERROR; //队列未建立 free(Q.base);//释放队列空间 Q.front = Q.rear = NULL; return OK; }//销毁操作 Status ClearQueue(SqQueue& Q) { if (!Q.base) return ERROR; //队列未建立 Q.front = Q.rear ; return OK; }//置空操作