【数据结构】课堂复习笔记3——栈与队列

Kendal2024-10-242024-10-25

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

三、栈和队列

3.1 栈和队列的定义和特点

3.1.1 栈

定义：只能在表的一端（栈顶）进行插入和删除运算的线性表
逻辑结构：与线性表相同，仍为一对一关系
存储结构：用顺序栈或链栈存储均可，但以顺序栈更常见
运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则
实现方式：基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等

3.1.2 队列

定义：只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表
逻辑结构：与线性表相同，仍为一对一关系
存储结构：用顺序队列或链队存储均可
运算规则：先进先出（FIFO）
实现方式：关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同

3.2 栈的表示和操作的实现

3.2.1 顺序栈

顺序栈的表示：

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

顺序栈的初始化：

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

判断顺序栈是否为空：

bool StackEmpty( SqStack S )
{
    if(S.top == S.base) return true;
   else return false;
}

求顺序栈的长度：

int StackLength( SqStack S )
{
    return S.top – S.base;
}

清空顺序栈：

Status ClearStack( SqStack S )
{
    if( S.base ) S.top = S.base;
    return OK;
}

销毁顺序栈：

Status DestroyStack( SqStack &S )
{
    if( S.base )
    {
        delete S.base ;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
  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;
}

取顺序栈栈顶元素：

Status GetTop( SqStack S, SElemType &e)  
{
    if( S.top == S.base )	 return ERROR; 	// 栈空
    e = *( S.top – 1 );
    return OK;
}

3.2.2 链栈

链栈的表示：运算受限，只在链表头部进行操作

typedef  struct StackNode {
      SElemType  data;
      struct StackNode *next;
 } StackNode,  *LinkStack;
LinkStack S;

链表的头指针就是栈顶
不需要头结点
基本不存在满栈的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行

链栈的初始化：

void InitStack(LinkStack &S )
{
    S=NULL;
}

判断链栈是否为空：

Status StackEmpty(LinkStack S)
{  
    if (S==NULL) return TRUE;
   else return FALSE;
}

链栈的入栈：

Status Push(LinkStack &S , SElemType e){
    p=new StackNode;      //生成新结点p 
    if (!p) exit(OVERFLOW);
    p->data=e; p->next=S; S=p; 
    return OK; 
}

链栈的出栈：

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

取栈顶元素：

SElemType GetTop(LinkStack S)
{
    if (S==NULL) exit(1)；
    else return S–>data;
}

3.3 栈与递归

递归的定义：
- 若一个对象部分地包含自己，或用它给自己定义，则称这个对象是递归的
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程
分治法：能分解成相对简单且解法相同或类似的子问题求解
- 能转变成一个新问题，解法相同或类同，不同的仅是处理的对象，且对象变化有规律
- 可以通过上述转化而使问题简化
- 必须有一个明确的递归出口，即递归的边界

void   p (参数表)
{
    if   （递归结束条件）可直接求解步骤；-----基本项
    else  p（较小的参数）；------归纳项
}

3.3.1 函数调用过程

调用前, 系统完成:
- 将实参,返回地址等传递给被调用函数
- 为被调用函数的局部变量分配存储区
- 将控制转移到被调用函数的入口
调用后, 系统完成:
- 保存被调用函数的计算结果
- 释放被调用函数的数据区
- 依照被调用函数保存的返回地址将控制转移到调用函数

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

队列的顺序表示：一维数组base[M]

#define M  100   //最大队列长度
Typedef struct {
   QElemType *base;  //初始化的动态分配存储空间
   int  front;            //头指针   
   int  rear;             //尾指针
}SqQueue;

空队标志：front= =rear 入队：base[rear++]=x; 出队：x=base[front++];

3.4.1 循环队列

解决假上溢的问题：利用模运算入队：

base[rear]=x;
rear=(rear+1)%M;

出队：

x=base[front];
front=(front+1)%M;

循环队列队满判断方法：少用一个元素空间队满：

(rear+1)%M==front;

队列的初始化：

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

求队列的长度：

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

循环队列入队：

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)%MAXQSIZE;
     return OK;
}

循环队列出队：

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

3.4.2 链队列

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

链队列的初始化：

Status InitQueue (LinkQueue &Q){
   Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); 
    if(!Q.front) exit(OVERFLOW);
    Q.front->next=NULL;
     return OK;
}

销毁链队列：

Status DestroyQueue (LinkQueue &Q){
   while(Q.front){
      Q.rear=Q.front->next;
      free(Q.front);
      Q.front=Q.rear;   }    
   return OK;
}

链队列的入队：

Status EnQueue(LinkQueue &Q,QElemType e){
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data=e; p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

链队列出队：

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;
}

链队列求头元素：

Status GetHead (LinkQueue Q, QElemType &e){
   if(Q.front==Q.rear) return ERROR;
   e=Q.front->next->data;
   return OK;
}