EUQI

切换主题

4 栈与队列 ​

4.2 栈的定义 ​

4.2.1 栈的定义 ​

栈（Stack）是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称为LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。
栈的删除操作，叫做出栈，有的也叫作弹栈。

4.2.2 进栈出栈变化形式 ​

3个整型数字1、2、3依次进栈，有哪些出栈顺序？

  • 1、2、3进，3、2、1出
  • 1进，1出；2进，2出；3进，3出
  • 1进，2进，2出，1出，3进，3出
  • 1进，1出，2进，3进，3出，2出
  • 1进，2进，2出，3进，3出，1出

4.3 栈的抽象数据类型 ​

ADT 栈（stack）

Data
  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。

Operation
  InitStack(*S)：初始化，建立一个空栈
  DestroyStack(*S)：若栈存在，销毁它
  ClearStack(*S)：将栈清空
  StackIsEmpty(S)：判断栈是否为空
  GetTop(S, *e)：若栈不为空，获取栈顶元素
  Push(*S, e)：若栈存在，向栈顶添加元素
  Pop(*S, *e)：删除栈顶元素，并返回
  StackLength(S)：返回栈的元素个数

endADT

4.4 栈的顺序存储结构和实现 ​

4.4.1 栈的顺序存储结构 ​

栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。

栈的结构定义：

c
typedef int SElemType;
//顺序栈结构
typedef struct {
  SElemType data[MAXSIZE];
  int top;
}SqStack;

一个栈，StackSize为5，栈的普通情况、空栈和满栈情况如下：

4.4.2 栈的顺序存储结构--进栈操作 ​

进栈操作：

c
// 插入元素e为新的栈顶元素
Status Push(SqStack *S, SElemType e) {
  if(S->top == MAXSIZE - 1){
    return ERROR;
  }
  S->top++;
  S->data[S->top] = e;
  return OK;
}

4.4.2 栈的顺序存储结构--出栈操作 ​

出栈操作：

c
// 删除栈顶元素，并返回
Status Pop(SqStack *S, SElemType *e) {
  if(S->top == -1){
    return ERROR;
  }
  *e = S->data[S->top];
  S->top--;
  return OK;
}

4.5 两栈共享空间 ​

两栈共享空间，即一个栈的存储空间，可以作为另一个栈的存储空间。

两栈共享空间结构：

c
typedef struct {
  SElemType data[MAXSIZE];
  int top1, top2;
}SqDoubleStack;

若栈2是空栈，栈1的top1等于n-1时栈1就满了，反之，当栈1为空，栈2的top2等于0时栈2就满了。top1 + 1 == top2为栈满。

进栈操作：

c
// 插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S, int stackNumber, SElemType e) {
  if(S->top1 + 1 == S->top2) {
    return ERROR;
  }
  if(stackNumber == 1) {
    S->data[++S->top1] = e;
  }else if(stackNumber == 2) {
    S->data[--S->top2] = e;
  }
  return OK;
}

出栈操作：

c
// 删除栈顶元素，并返回
Status Pop(SqDoubleStack *S, int stackNumber, SElemType *e) {
  if(stackNumber == 1) {
    if(S->top1 == -1) {
      return ERROR;
    }
    *e = S->data[S->top1--];
  }else if(stackNumber == 2) {
    if(S->top2 == MAXSIZE) {
      return ERROR;
    }
    *e = S->data[S->top2++];
  }
  return OK;
}

4.6 栈的链式存储结构和实现 ​

4.6.1 栈的链式存储结构 ​

栈的链式存储结构，简称链栈。

链栈的结构定义：

c
typedef struct StackNode {
  SElemType data;
  struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct {
  LinkStackPtr top;
  int count;
}LinkStack;

4.6.2 栈的链式存储结构--进栈操作 ​

进栈操作：

c
// 插入元素e为新的栈顶元素
Status Push(LinkStack *S, SElemType e) {
  LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
  p->data = e;
  p->next = S->top;
  S->top = p;
  S->count++;
  return OK;
}

4.6.3 栈的链式存储结构--出栈操作 ​

出栈操作：

c
// 若栈不为空，删除栈顶元素，并返回
Status Pop(LinkStack *S, SElemType *e) {
  LinkStackPtr p;
  if(S->top == NULL) {
    return ERROR;
  }
  *e = S->top->data;
  p = S->top;
  S->top = S->top->next;
  free(p);
  S->count--;
  return OK;
}

如果栈的使用过程中元素变化不可预料，有时很大，有时很小，最好用链栈，反正，如果它的变化在可控范围内，建议使用顺序栈会好一些。

4.7 栈的作用 ​

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

4.8 栈的作用--递归 ​

4.9 栈的应用--表达式求值 ​

4.10 队列的定义 ​

队列（Queue）是限定仅在一端进行插入操作，在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称为FIFO结构。允许插入的一端称为队尾，允许删除的一端称为队头

4.11 队列的抽象数据类型 ​

ADT 队列（queue）
Data
  同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。

Operation
  InitQueue(*Q)：初始化，建立一个空队列
  DestroyQueue(*Q)：若队列存在，销毁它
  ClearQueue(*Q)：将队列清空
  QueueIsEmpty(Q)：判断队列是否为空
  GetHead(Q, *e)：若队列不为空，返回队头元素
  EnQueue(*Q, e)：若队列存在，插入元素e为新的队尾元素
  DeQueue(*Q, *e)：若队列不为空，删除队头元素，并返回
  QueueLength(Q)：返回队列的元素个数

endADT

4.12 循环队列 ​

4.12.1 队列顺序存储的不足 ​

4.12.2 循环队列的定义 ​

队列的这种首尾相接的顺序存储结构称为循环队列。

当少用一个存储位置时，计算队列是否满的公式为：(rear + 1) % QueueSize == front

通用的计算队列长度的公式为：(rear - front + QueueSize) % QueueSize

TIP

另一种方法是设置标志位flag，当front==rear，且flag == 0时队列为空，当front == rear，且flag == 1时队列为满，这样可以利用所有存储空间

循环队列的顺序存储结构代码：

c
typedef int QElemType;
typedef struct {
  QElemType data[MAXSIZE];
  int front;
  // 队列不为空时，指向队尾的下一个位置
  int rear;
}SqQueue;

循环队列的初始化代码：

c
Status InitQueue(SqQueue *Q) {
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

循环队列求队列长度代码：

c
// 返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q) {
  return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

循环队列入队操作代码：

c
// 若队列未满，则插入元素e为Q新的队尾元素
Status EnQueue(SqQueue *Q, QElemType e) {
  // 判断队列是否满了
  if((Q->rea+1)%MAXSIZE == Q->front) {
    return ERROR;
  }
  Q->data[Q->rear] = e;
  Q->rear = (Q->rear+1)%MAXSIZE;
  return OK;
}

循环队列出队操作代码:

c
// 若队列不空，则删除Q中队头的元素
Status DeQueue(SqQueue *Q, QElemType *e) {
  // 判断队列为空
  if(Q->front == Q->rear) {
    return ERROR;
  }
  *e = Q->data[Q->front];
  Q->front = (Q->front+1)%MAXSIZE;
  return OK;
}

4.13 队列的链式存储结构 ​

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

空队列时，front和rear指向同一个结点：

非空队列，front指向头结点，rear指向尾结点：

链队列的结构定义：

c
typedef int QElemType;
typedef struct QNode {
  QElemType data;
  struct QNode *next;
}QNode, *LinkQueuePtr;

typedef struct {
  LinkQueuePtr front, rear;
}LinkQueue;

4.13.1 队列的链式存储结构--入队操作 ​

入队操作：

c
// 若队列存在，插入元素e为新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e) {
  LinkQueuePtr p = (LinkQueuePtr)malloc(sizeof(QNode));
  if(p == NULL) {
    return ERROR;
  }
  p->data = e;
  p->next = NULL;
  Q->rear->next = p;
  Q->rear = p;
  return OK;
}

4.13.2 队列的链式存储结构--出队操作 ​

出队操作：

c
// 若队列不为空，删除队头元素，并返回
Status DeQueue(LinkQueue *Q, QElemType *e) {
  LinkQueuePtr p;
  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;
}

可以确定队列长度的情况下，建议使用循环队列，否则，建议使用链队列。

4.14 总结回顾 ​

栈

  • 顺序栈
    • 两栈共享空间
  • 链栈

队列

  • 顺序队列
    • 循环队列
  • 链队列