栈和队列

栈和队列

栈

栈(stack)　限定仅在表尾进行插入或删除操作的线性表。

表尾端称为栈顶(top)，表头端称为栈底(bottom)。

后进先出的线性表。栈的抽象数据类型定义：

ADT Stack{
  数据对象： D = {ai|ai belong to ElemSet,i=1,2,....,n, n>=0}
  数据关系： R1 = {<ai-1,ai>|ai-1,ai belong to D,i=1,2,....,n}
      InitStack(&S)
      // 构造一个空栈Ｓ。
      DestoryStack(&S)
      // 销毁栈Ｓ。
      ClearStack(&S)
      //将S清为空栈。
      StackEmpty(S)
      // 若栈Ｓ为空栈，则返回true,否则False。
      StackLength(S)
      //返回S的元素个数，即栈的长度。
      GetTop(S,&e)
      //用e返回S的栈顶元素。
      Push(&S,e)
      //插入元素e为新的栈顶元素。
      Pop(&S,&e)
      //删除S的栈顶元素，并用e返回其值。
 
}ADT Stack

顺序栈定义：

typedef struct{
  SElemType    *base;
  SElemType    *top;
  int          stacksize;
}SqStack

设定两个常量：STACK_INIT_SIZE(存储空间初始分配量) 和STACKINCREMENT（存储空间分配增量)

top:栈顶指针，初始值指向栈底，base:栈底指针，初始值指向栈底顶，stacksize:栈当前可用容量

顺序栈模块说明：

#define STACK_INIT_SIZE  100;
#define STACKINCREMENT   10;
typedef struct{
  SElemType    *base;
  SElemType    *top;
  int          stacksize;
}SqStack;
//－－－－－基本操作的函数原型说明－－－－－
Status InitStack(SqStack &S);

Status DestoryStack(SqStack &S);

Status  ClearStack(SqStack &S);

Status StackEmpty(SqStack S);

Status StackLength(SqStack S);

Status GetTop(SqStack S,SElemType &e);

Status Push(SqStack &S,SElemType e);

Status Pop(SqStack &S,SElemType &e);

//－－－－－基本操作的算法描述－－－－－
Status InitStack(SqStack &S){
  S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
  if(!S.base) exit (OVERFLOW);  //存储分配失败
  S.top = S.base;
  S.stacksize = STACK_INIT_SIZE;
  return Ok;
}

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

Status 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) exit (OVERFLOW);
    S.top = S.base+S.stacksize;
    S.stacksize+= STACKINCREMENT;
  }
  *S.top ++ = e;
  return OK;
}

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

栈的应用举例

迷宫求解（从入口到出口的路径算法）

typedef struct{
  int       ord;       //通道块在路径上的“序号”
  PosType   seat;　　　//通道块在迷宫中的“坐标位置”
  int       di;　　　　//从此通道走向下一通道块的“方向”
}SElemType;

Status MazePath(MazeType maze,PosType start,PosType end){
  InitStack(S); curpos = start;   //设定“当前位置”为“入口位置”
  curpos = 1;　　　　　　　　　　　　//探索第一步
  do{
    if(Pass(curpos)){　　　　　　　//当前位置可以通过，即是未曾走到过的通道块
      FootPrint(curpos);　　　　　//留下足迹
      e = (curstep,curpos,1);
      Push(S,e);　　　　　　　　　//加入路径
      if(corpos == end) return (TRUE);
      curpos = NextPos(curpos,1);
      curpos ++;　　　　　　　　 //探索下一步
    }
    else{　　　　　　　　　　　　　//当前位置不可以通过
      if(!StackEmpty(S)){
        Pop(S,e);
        while(e.di == 4 && !StackEmpty(S)){
          MarkPrint(e.seat); Pop(S,e);   //留下不能通过的标记，并退回一步
        }
        if(e.di<4){
          e.di++;  Push(S,e); 　　　　　　//换下一个方向探索
          curpos = NextPos(e.seat,e.di);
        }
      }
    }
  }while(!StackEmpty(S));
  return (FALSE);
}

栈与递归的实现

队列

队列(queue)是一种先进先出的线性表。只允许在表的一端进行插入，而在另一端删除元素。

队列的抽象数据类型定义：

ADT Queue{
  数据对象： D = {ai|ai belong to ElemSet,i=1,2,....,n, n>=0}
  数据关系： R1 = {<ai-1,ai>|ai-1,ai belong to D,i=1,2,....,n}
      InitQueue(&Q)
      // 构造一个空队列Q。
      DestoryQueue(&Q)
      // 销毁栈Q。
      ClearQueue(&Q)
      //将Q清为空队列。
      QueueEmpty(Q)
      // 若栈Q为空队列，则返回true,否则False。
      QueueLength(Q)
      //返回S的元素个数，即队列的长度。
      GetHead(Q,&e)
      //用e返回Q的队头元素。
      EnQueue(&Q,e)
      //插入元素e为Q的新的队尾元素。
      DeQueue(&S,&e)
      //删除Q的队头元素，并用e返回其值。
 
}ADT Queue

链队列

//－－－－－ADT Queue的表示与实现－－－－－

//－－－－－单链队列－－队列的链式存储结构－－－－－
typedef struct QNode{
  QElemType       data;
  struct QNOde    *next;
}QNOde, *QueuePtr;

typedef struct{
  QueuePtr   front    //队头指针
  QueuePtr   rear     //队尾指针
}LinkQueue;

//－－－－－基本操作的函数原型说明－－－－－
Status InitQueue(LinkQueue &Q)
   
Status DestoryQueue(LinkQueue &Q)

Status ClearQueue(LinkQueue &Q)
  
Status QueueEmpty(LinkQueue Q)

Status QueueLength(LinkQueue Q)
  
Status GetHead(LinkQueue &Q, QElemType &e)
  
Status EnQueue(LinkQueue &Q, QElemType e)
  
Status DeQueue(LinkQueue &Q, QElemType &e)

//－－－－－基本操作的算法描述－－－－－
Status InitQueue(LinkQueue &Q){
  Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
  if(!Q.front)exit(OVERFLOW);
  Q.front->next = NULL;
  return OK;
}

Status DestoryQueue(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;
  free(p);
  return OK;
}

循环队列

//－－－－－循环队列－－队列的顺序存储结构－－－－－
#define MAXQSIZE 100　　　//最大队列长度
typedef struct{
  QElemType  *base;   //初始化的动态分配存储空间
  int  front;         //头指针，若队列不为空，指向队列头元素
  int  rear;　　　　　　//尾指针，若队列不为空，指向队列尾元素的下一个位置
}sqQueue;

//－－－－－循环队列的基本操作的算法描述－－－－－
Status InitQueue(SqQueue &Q){
  //构造一个空队列
  Q.base = (QElemType ×)malloc(MAXQSIZE *sizeof(QElemType));
  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(SqQueue &Q, QElemType e){
  //若对垒不为空，则删除Ｑ的队头元素，用ｅ返回其值，并返回ＯＫ；
  //否则返回ＥＲＲＯＲ
  if(Q.front == Q.rear) return ERROR;
  e = Q.base[Q.front];
  Q.front = (Q.front+1) %　MAXQSIZE;
  return OK;
}