数据结构-第三章-栈与队列.ppt

栈和队列 廖勇毅 栈 特点：LIFO 操作：初始化、插入、弹出。 定义栈 #define STACT_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; 初始化栈 int InitStack(SqStack S){ S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType)); if(!S.base){ printf(“overflow\n); return 0; } S.base = S.top; S.stacksize = STACT_INIT_SIZE; return 1; } 插入元素 int Push(SqStack S, SElemType e){ if(S.top - S.base = S.stacksize){ S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType)); if(!S.base){ printf(“overflow\n); return 0; } S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return 1; } 弹出元素 int Pop(SqStack S, SElemType e){ if(S.top == S.base) { printf(“empty stack!\n); return 0; } e = *--S.top; return 1; } 读取栈顶元素 int GetTop(SqStack S, SElemType e){ if(S.top == S.base) { printf(“empty stack!\n); return 0; } e = *(S.top - 1); return 1; } 判空 int StackEmpty(SqStack S) { if(S.top == S.base) return 1; else return 0; } 数制转换应用 十进制数和其他d进制转换原理： N = (N / d) + (N % d) void conversion (int Num) { SElemType e; SqStack S; InitStack(S); while (Num) { Push(S, Num % 8); Num = Num/8; } while (!StackEmpty(S)) { Pop(S,e); printf (%d, e); } printf(\n); } 队列 特点：FIFO 操作：初始化、入队、出队、读取队头、获取长度、判空、遍历。 循环队列 定义 #define MAXQSIZE 10 typedef int QElemType; typedef struct{ QElemType *base; int front; int rear; }SqQueue; 初始化 int InitQueue(SqQueue Q){ Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(SqQueue)); if(!Q.base){ printf(overflow\n); return 0; } Q.front = Q.rear = 0; return 1; } 入队 int EnQueue(SqQueue Q, QElemType e){ if((Q.rear + 1) % MAXQSIZE == Q.front){ printf(queue is full\n); return 0; } Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return 1; } 出队 int DeQueue(SqQueue Q, QElemType e){ if(Q.rear == Q.front){ printf(queue is emp