堆栈的应用.ppt

堆栈 堆栈的应用 队列 队列的应用 4. 顺序队列入队 int ENQUEUE(sequeue *sq,datatype x) { if (sq-front==(sq-rear+1)%maxsize) {printf(“sequeue is full\n”);return NULL;} else { sq-rear＝(sq-rear+1)%maxsize; sq-data[sq-rear]＝x; return(TRUE); } } 5. 顺序队列出队 datetype DEQUEUE(sequeue *sq) { if (EMPTY(sq)) {printf(“queue is empty\n”);return NULL;} else { sq-front＝(sq-front+1)%maxsize; return(sq-data[sq-front]); } } 队头在链头，队尾在链尾。 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front == rear 3.3.2 链队列 链队列结点类型定义 typedef struct { linklist *front,*rear; } linkqueue; linkqueue *q; 头结点 ∧ 带头结点的空链队列 q-front q-rear q 带头结点的非空链队列 a1 a2 an ∧ … 队头结点 队尾结点 头结点 q-front q-rear q 1. 链队列置队空 linkqueue *SETNULL(linkqueue *q) { q-front＝malloc(sizeof(linklist)); q-front-next＝NULL; q-rear＝q-front; return q; } 问题：当q不为空时， 即q是一个已存在的 非空队列，算法正确 否？ 2. 链队列判队空 int EMPTY(linkqueue *q) { if (q-front==q-rear) return(TRUE); else return(FALSE); } 3. 取链队列队头结点 datatype FRONT(linkqueue *q) { if (EMPTY(q)) {printf(“queue is empty\n”);return NULL;} else return(q-front-next-data); } 4. 链队列入队 ENQUEUE(linkqueue *q,datatype x) { q-rear-next＝malloc(sizeof(linklist)); q-rear＝q-rear-next; q-rear-data＝x; q-rear-next＝NULL; } 5. 链队列出队 队列长度大于1的出队运算 a1 a2 an ∧ … 队头结点 队尾结点 头结点 q-front q-rear q s ① ② ③ ① s=q-front-next; ② q-front-next=s-next; ③ free(s); ∧ (b)出队后 q-front q-rear q 队列长度为1时的出队运算 头结点 a1 (a)出队前 q-front q-rear q ∧ s 改进的出队运算 a1 a2 an ∧ … 队头结点 队尾结点 头结点 q-front q-rear q s ① ③ ② datatype DEQUEUE(linkqueue *q) { linklist *s; if (EMPTY(q)) {printf(“queue is empty\n”);return NULL;} else { s＝q-front; q-front＝q-front-next; free(s); return(q-front-data); } } * 3.1 栈 ( Stack ) 3.1.1 栈的概念及运算 只允许在一端插入和删除的线性表 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) 特点 后进先出 (LIFO) 退栈 进栈 进栈示例 退栈示例 栈的基本操作 1、置栈空SETNULL(S):将S置成空栈； 2、判栈空EMPTY(S):S是否为空栈; 3、进栈PUSH(S,x):在S的顶部插入(压入)元素x; 4、退栈POP(S):删除（弹出）栈S的顶部元素； 5、取栈顶元素TOP(S):取栈S的顶部元素。 顺序栈的定义 typedef int