《数据结构》第三章"栈和队列"

3. 栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈的定义和特点

1. 栈：仅在表尾进行插入和删除的线性表，表尾称为栈顶，表头称为栈底
2. 栈被称为后进先出（LIFO）

3.1.2 队列的定义和特点

1. 队列是一种先进先出（FIFO）
2. 队列仅允许表的一端插入，而在另一端删除
3. 允许插入的一端称为队尾，允许删除的一端称为队头

3.2 案例引入

1. 数制的转换
2. 括号匹配的检验
3. 表达式求值
4. 舞伴问题

3.3 栈的表示和操作的实现

3.3.1 栈的类型定义

ADT Stack
{
    数据对象:
    数据关系:
    基本操作:
}ADT Stack

3.3.2 顺序栈的表示和实现

1. 顺序栈的存储结构

   #define MAXSIZE 100
   typedef struct
   {
       SElemType *base;
       SElemType *top;
       int stacksize;
   }SqStack

2. 空栈的判定方法：base == top;

3. 满栈的判定方法：top - base == stacksize;

4. 操作的实现算法

   • 初始化：

     Status InitStack(SqStack &S)
     {
         S.base = new SElemType[MAXSIZE];
         if(!S.base)  exit (OVERFLOW);
         S.top = S.base;
         S.stacksize = MAXSIZE;
         return OK;
     }

   • 入栈：

     Status Push (SqStack &S, SElemType e)
     {
         if(S.top - S.base == S.stacksize)  return ERROR;
         *S.top++ = e;
         return OK;
     }

   • 出栈：

     Status Pop(SqStack &S, SElemType &e)
     {
         if(S.top == S.base)  return ERROR;
         e = *--S.top;
         return OK;
     }

   • 取栈顶元素

     SElemType GetTop(SqStack S)
     {
         if(S.top != S.base)
             return *(S.top-1);
     }

3.3.3 链栈的表示和实现

1. 初始化：

   Status InitStack(LinkStack &S)
   {
       S = NULL;
       return OK;
   }

2. 入栈：

   Status Push (LinkStack &S, SElemType e)
   {
       p = new StackNode;
       p -> data = e;
       p ->next = S;
       S = p;
       return OK;
   }

3. 出栈：

   Status Pop (LinkStack &S , SElemType &e)
   {
       if(S==NULL) return ERROR;
       e = S->data;
       p = S;
       S = S->next;
       delete p;
       return OK;
   }

4. 取栈顶值：

   SElemType GetTop (LinkStack S)
   {
       if(S != NULL)
           return S->data;
   }

3.4 栈与递归

3.4.1 采用递归算法解决的问题

1. 定义是递归的
2. 数据结构是递归的
3. 问题的解法是递归的

3.4.2 递归过程与递归工作栈

1. 一个函数在运行期间调用另一个函数时，在运行被调用函数之前，系统需要完成3件事：

   (1) 将所有的实参、返回地址等信息传递给被调用函数保存

   (2) 为被调用函数的局部变量分配储存区

   (3) 将控制转移到被调函数入口

2. 而从被调用函数返回调用函数之前，系统也应该完成3件事

   (1) 保存被调用函数的计算结果
   (2) 释放被调函数的数据区
   (3) 依照被调用函数保存的返回地址将控制转移到调用函数

3.4.3 递归算法的效率分析

1. 时间复杂度的分析
2. 空间复杂度的分析

3.4.4 利用栈将递归转换为非递归的办法

3.5 队列的表示和操作的实现

3.5.1 队列的类型定义

3.5.2 循环队列 ( 队列的顺序表示和实现 )

1. 队列的顺序结构

   #define MAXQSIZE 100
   typedef struct
   {
       QElemType *base;  //储存空间的基地址
       int front;
       int rear;
   }SqQueue;

2. 循环队列判断队满的两种处理方法：

   1. 少用一个储存空间
      • 队空条件：Q.front == Q.rear
      • 队满条件：(Q.rear + 1)%MAXQSIZE == Q.front
   2. 另外设置一个标志位

3. 初始化：

   Status InitQueue(SqQueue & Q)
   {
   	Q.base=new QElemType[MAXQSIZE];
       if(!Q.base) exit(OVERFLOW);
   	Q.front=Q.rear=0;
   	return OK;
   }

4. 求队列长度：

   int QueueLength(SqQueue Q)
   {
       return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
   }

5. 入队：

   Status EnQueue(SqQueue & Q,QElemType e)
   {
       if((Q.rear+1)%MAXQSIZE == Q.front)
   		return ERROR;
   	Q.base[Q.rear]=e;
   	Q.rear=(Q.rear+1)%MAXOSIZE;
   	return OK ;
   }

6. 出队：

   status DeQueue(SqQueue &Q,QElemType & e)
   {
       if(Q.front==Q.rear) return ERROR;
   	e=Q.base[Q.front];
       Q.front=(Q.front+1)%MAXQSIZE;
       return OK;
   }

7. 取队头元素

   OElemType GetHead(sqQueue Q)
   {
       if(Q.front != Q.rear)
           return Q.base[Q.front];
   }

3.5.3 链队列 ( 队列的链式表示和实现 )

1. 队列的链式存储结构

   typedef struct QNode
   {
       QElemType data;
       struct QNode *next;
   }QNode, *QueuePtr;
   
   typedef struct
   {
       QueuePtr front;  //头指针
       QueuePtr rear;   //尾指针
   }LinkQueue;

2. 初始化：

   Status InitQueue (LinkQueue & Q)
   {
   	Q.front=Q.rear=new QNode;
   	Q.front->next=NULL;
   	return OK;
   }

3. 入队：

   Status EnQueue(LinkQueue & Q,QElemType e)
   {
   	p=new QNode;
   	p->data=e;
   	p->next=NULL;	Q.rear->next=p;
   	Q.rear=p;
   	return OK;
   }

4. 出队：

   status DeQueue(LinkQueue & Q,QElemType & e)
   {
       if(Q.front == Q.rear) return ERROR;
       p=Q.front->next;
   	e=p->data;
   	Q.front->next=p->next;
   	if(Q.rear==p) Q.rear=Q.front;
   	delete p;
   	return OK;
   }

5. 取队头元素

   QElemType GetHead(LinkQueue Q)
   {
       if(Q.front != Q.rear)
           return Q.front ->next ->data;
   }

3.6 案例分析与实现

3.7 小结