數(shù)據(jù)結(jié)構(gòu)-第三章-棧與隊列ppt課件

1、棧和隊列廖勇毅棧 特點：LIFO 操作：初始化、插入、彈出。 定義棧 #define STACT_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int SElemType; typedef structSElemType *base;SElemType *top;int stacksize; SqStack; 初始化棧 int InitStack(SqStack &S)S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType);if(!S.base)printf(“o

2、verflown);return 0;S.base = S;S.stacksize = STACT_INIT_SIZE;return 1; 插入元素 int Push(SqStack &S, SElemType &e)if(S - S.base = S.stacksize)S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType);if(!S.base)printf(“overflown);return 0;S = S.base + S.stacksize;S.

3、stacksize += STACKINCREMENT;*S+ = e;return 1; 彈出元素 int Pop(SqStack &S, SElemType &e)if(S = S.base) printf(“empty stack!n);return 0;e = *-S;return 1; 讀取棧頂元素 int GetTop(SqStack &S, SElemType &e)if(S = S.base) printf(“empty stack!n);return 0;e = *(S - 1);return 1; 判空int StackEmpty(SqSta

4、ck &S) if(S = S.base)return 1; elsereturn 0;數(shù)制轉(zhuǎn)換運用 十進(jìn)制數(shù)和其他d進(jìn)制轉(zhuǎn)換原理： 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 操作：初始化、入隊、出隊、讀取隊頭、獲取長度、判空、遍歷。循環(huán)

5、隊列 定義 #define MAXQSIZE 10 typedef int QElemType; typedef structQElemType *base;int front;int rear; SqQueue; 初始化 int InitQueue(SqQueue &Q)Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(SqQueue);if(!Q.base)printf(overflown);return 0;Q.front = Q.rear = 0;return 1; 入隊 int EnQueue(SqQueue &Q, QEl

6、emType e)if(Q.rear + 1) % MAXQSIZE = Q.front)printf(queue is fulln);return 0;Q.baseQ.rear = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return 1; 出隊 int DeQueue(SqQueue &Q, QElemType &e)if(Q.rear = Q.front)printf(queue is emptyn);return 0;e = Q.baseQ.front;Q.front = (Q.front + 1) % MAXQSIZE;return 1; 讀取隊頭元素 int GetHead(SqQueue &Q, QElemType &e)if(Q.rear = Q.front)printf(queue is emptyn);return 0;e = Q.baseQ.front;return 1; 獲取隊列長度 int QueueLength(SqQueue &Q)return (Q.rear + MAXQSIZE) - Q.front) % MAXQSIZE; 判空 bool QueueEmpty(SqQueue &Q)return (Q.rear = Q.front); 遍歷隊列 void Q