栈和队列

栈和队列

1.栈

1.定义

1、栈是一种特殊的线性表，只允许在一端进行插入或删除操作。

2、栈顶：允许插入和删除的一端

3、栈底：不允许插入和删除的一端

4、空栈：元素为空的栈

2.特点

后进先出

3.基本操作

InitStack(&S);    //初始化化栈，构造一个空栈，分配内存空间
DestroyStack(&S); //销毁栈，回收内存空间

Push(&S, x);   //入栈，若栈未满，则将x加入使之成为新的栈顶
Pop(&S, &x);   //出栈，若栈s非空，则弹出栈顶元素，用x返回

GetTop(S,&x);  //读取栈顶元素，若栈S非空，则用x返回，并不弹出

StackEmpty(S);  //栈判空操作，空，返回true

4.出栈序列

n个不同元素进栈，出栈元素不同排列个数为:

2.顺序栈

1.定义

#define MaxSize 10
typedef struct{
  int data[MaxSize];
  int top;
}SqStack;

//初始化
void InitStack(SqStack &S){
  S.top = -1;    //初始化栈顶指针,也可以实现成初始值为0的情况
}

2.进栈

//新元素进栈操作
bool Push(SqStack &S, int x){
  if(S.top == MaxSize - 1)
    return false;
  S.top = S.top + 1;
  S.data[S.top] = x;
  return true;
}

3.出栈

//出栈操作
bool Pop(SqStack &S, int &x){
  if(S.top == -1){
    return false;
  }
  x = S.data[S.top--];
  return true;
}

4.读栈顶元素

bool GetTop(SqStack S, int &x){
  if(S.top == -1){
    return false;
  }
  x = S.data[S.top];
  return true;
}

注意：top指针初始值为-1，表示指向栈顶元素，如果初始值为0，则表示指向栈顶元素的下一个位置。

5.缺点

顺序栈是通过静态数组实现的，内存固定，不方便拓展，但是如果一开始开辟一个比较大的空间用于栈，则会导致内存的使用效率降低；解决方式如下

3.共享栈

1.定义

两个栈共享同一片空间

#define MaxSize 10

typedef struct{
  int data[MaxSize];
  int top0;
  int top1;
}ShStack;

//初始化栈顶指针
void InitStack(ShStack &S){
  S.top0 = -1;
  S.top1 = MaxSize;
}

判断栈是否满了的条件是：top0 + 1 == top1

2.使用场景？

对于共享栈的使用场景，未找到相关资料，暂时保留？

4.链栈

1.定义

通过链表的方式实现栈；即规定只在单链表的链首进行插入和删除操作

typedef struct LinkNode{
  int data;
  struct LinkNode *next;
}*LiStack;

同样可以实现带头结点和不带头结点的版本，建议实现不带头结点的版本

2.相关操作(无头结点)

//初始化栈
InitStack(LiStack &S);

//进栈
PushLiStack(LiStack &S, int e);
//出栈
PopLiStack(LiStack &S, int& e);

//获取栈顶元素
GetLiStackTop(LiStack S, int& e);

//链栈是否存在判空判满操作，个人觉得，没必要

5.队列——顺序队

1.定义

1、只允许在一端进行插入，在另一端删除的线性表

2、队尾：可以进行插入元素的一端

3、队头：可以进行删除元素的一端

4、空对：元素为空的队列

5、特点：先进先出

2.基本操作

//创销
InitQueue(&Q);
DestroyQueue(&Q);
//入队，出队
EnQueue(&Q,x);
DeQueue(&Q,&x);
//读对头元素
GetHead(Q,&x);
//判队空
QueueEmpty(Q);

3.顺序存储实现

//注意，此种实现方式，rear初值为0，队尾指针指向的是队尾元素的下一个应该插入的位置
//如果需要指向队尾元素，则rear初值应该为-1

#define MaxSize 10
typedef Struct{
  ElemType data[MaxSize];
  int front,rear;
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
  Q.rear = Q.front = 0;
}
//判断队列是否为空
bool QueueEmpty(SqQueue Q){
  if(Q.rear == Q.front){
    return true;
  }
  return false;
}

//入队,只能在队尾入队
bool EnQueue(SqQueue &Q, ElemType x){
  if((Q.rear + 1)%MaxSize == Q.front){
    return false;
  }
  Q.data[Q.rear] = x;
  Q.rear = (Q.rear + 1)%MaxSize;
  return true;
}

//出队，只能在队头进行出队
bool DeQueue(SqQueue &Q, ElemType &x){
  if(Q.rear == Q.front){
    return false;
  }
  X = Q.data[Q.front];
  Q.front = (Q.front + 1)%MaxSize;
  return true;
}

//获得对头元素,用x返回
bool GetHead(SqQueue Q, ElemType &x){
  if(Q.rear == Q.front){
    return false;
  }
  x = Q.data[Q.front];
  return true;
}

1、注意：上面实现情况中，判断队空和队满是通过牺牲一个存储单元实现的；队空rear == front；队满rear + 1 = front;

2、队列元素个数 = （rear + front + MaxSize)%MaxSize

4.判断队满队空

1、如果不能牺牲存储空间，rear初值为0，则判断队满和队空可以通过以下方式：

//方式一
/*
在struct中定义size变量，用来表示当前队列的长度
size初始值0；入队size++；出队size--；
*/
typedef struct{
  int front,rear;
  int size;
}SqQueue;

//方式二
/*
设置tag，表示最近进行的操作是删除/插入
每次删除操作成功时，tag = false;
每次插入操作成功时，tag = true；

只有插入操作，才会导致队满，队满条件：
front == rear && tag == true;
只有删除操作，才会导致队空，队空条件
front == rear && tag == false;
*/
typedef struct{
  int front,rear;
  bool tag;
}SqQueue;

2、如果不能牺牲存储空间，rear初值为1，则判断队满和队空可以通过以下方式：

//判空
(Q.rear + 1)%MaxSize == Q.front;

//判满
/*
方案一：牺牲一个存储单元
(Q.rear + 2)%MaxSize == Q.front;
或
(Q.rear + 1)%MaxSize == Q.front - 1;

方案二：增加辅助变量

*/

6.队列——链式存储

1.定义

可以通过链表实现队列，队尾插入，队头删除，可以实现带头结点和不带头结点的版本

typedef struct LinkNode{
  ElemType data;
  struct LinNode* next;
}LinkNode;

typedef struct{
  LinkNode* front,*rear;     //对头和队尾指针
}LinkQueue;

//初始化，带头结点
void InitQueue(LinkQueue &Q){
  Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
  Q.front->next = NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
  if(Q.front == Q.rear)
    return true;
  return false;
}

/*______________________________________________________
*/

//初始化，不带头结点
void InitQueue(LinkQueue &Q){
  Q.front = Q.rear = NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
  if(Q.front == NULL)
    return true;
  return false;
}

2.入队

//带头结点
void EnQueue(LinkQueue &Q, ElemType x){
  LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
  s->data = x;
  s->next = NULL;
  Q.rear->next = s;
  Q.rear = s;
}


//不带头结点
void EnQueue(LinkQueue &Q, ElemType x){
  LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
  s->data = x;
  s->next = NULL;
  if(Q.front == NULL){
    //第一个节点
    Q.front = s;
    Q.rear = s;
  }
  else{
    Q.rear->next = s;
    Q.rear = s;
  }
}

3.出队

//带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
  if(Q.front == Q.rear){
    return false;            //空队
  }
  LinkQueue* p = Q.front->next;
  x = p->data;
  Q.front->next = p->next;
  //表尾节点，需要修改表尾指针
  if(Q.rear == p)
    Q.rear = Q.front;
  free(p);
  return true;
}

//不带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
  if(Q.front == NULL){
    return false;     //空队
  }
  LinkNode *p = Q.front;
  x = p->data;
  Q.front = p->next;
  //最后一个队
  if(Q.rear == P){
    Q.front = NULL;
    Q.rear = NULL;
  }
  free(p);
  return true;
}

注意：

1、在链式队列中，一般不需要进行判断队满的条件

2、如果需要经常访问队列元素的大小，由于是链表实现的，所以很不方便，每次都要经过O(N)的时间复杂度，因此，可以在struct中定义一个辅助变量length，来存储队列的大小

7.双端队列

1.定义

1、允许两端进行插入、两端删除的线性表

2、输入受限的双端队列：只允许从一端插入、两端删除的线性表

3、输出受限的双端队列：只允许从两端插入、一端删除的线性表

2.输出序列

主要考点是判断输出序列是否合法

8.栈的应用

1.括号匹配问题

bool bracketCheck(char str[], int length){
  SqStack S;
  InitStack(S);
  for(int i = 0; i < length; ++i){
    if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
      Push(S, str[i]);
    }
    else{
      if(StackEmpty(S)){
        //扫描到有括号，栈空，匹配失败
        return false;
      }
      char topElem;
      Pop(S, topElem);
      if(str[i] == ')' && topElem != '('){
        return false;
      }
      if(str[i] == ']' && topElem != '['){
        return false;
      }
      if(str[i] == '}' && topElem != '{'){
        return false;
      }
    }
  }
  //检索完全部括号后，栈空说明匹配成功
  return StackEmpty(S);
}

1、用栈实现括号匹配：

依次扫描所有字符，遇到左括号入栈，遇到有括号则弹出栈顶元素检查是否匹配

2、匹配失败的情况：

1）左括号单身

2）有括号单身

3）左右括号不匹配

2.表达式求值

注意：做操作数和有操作数的位置在转化表达式后不能发生变化

1.三种表达式：

中缀表达式、前缀表达式、后缀表达式

2.中缀表达式转后缀表达式

左优先可以保证顺序唯一

3.后缀表达式的计算

注意：两个操作数有先后顺序

通过栈实现机算，也可以将后缀转化为中缀表达式

4.中缀表达式转成前缀表达式

5.前缀表达式的计算

注意：后缀表达式是从左往右扫描，先弹出的是右操作数；前缀表达式是从右往左扫描，先弹出的是左操作数

3.中缀表达式转后缀表达式

1.算法思想

2.代码

简单实现，此代码存在问题，大致逻辑没问题，只能处理10以内的算术运算，只支持()小括号，只支持 +-*/

static map<char, int> recordOfOperator = {
    {'*',2},
    {'/',2},
    {'+',1},
    {'-',1}
};

//判断是否为运算符
bool isOperator(char ch){
    return recordOfOperator.find(ch) != recordOfOperator.end();
}
//判断两个操作符的优先级，等于返回0，first > second 返回 1；first < second 返回2;
int priorityOfOp(char first, char second){
    int operator1 = recordOfOperator.find(first)->second;
    int operator2 = recordOfOperator.find(second)->second;
    return operator1 - operator2;
}

/*
中缀表达式转后缀表达式
中缀表达式 : 1 + 2 *(3 + 4) - 5
后缀表达式：1 2 3 4 + * + 5 -

默认中缀表达式无特殊字符
*/
bool InfixToPostfixExpression(string str,string &res){
    if(str.empty()){
        return false;
    }
    stack<char> op;
    for(int i = 0; i < str.size(); ++i){
        if(isOperator(str[i])){
            //遇到操作符,依次弹出栈中操作符比当前操作符优先级高的，直到栈空或者遇到 (
            while(!op.empty() && ( op.top() != '(' && priorityOfOp(op.top(), str[i]) >= 0)){
                res.push_back(op.top());
                op.pop();
            }
            op.push(str[i]);
        }
        else if(str[i] == '(' || str[i] == ')'){
            //遇到限定符
            if(str[i] == '('){
                op.push(str[i]);
            }
            else{
                //依次弹出栈内运算符，并加入到后缀表达式，直到弹出'('为止
                while(!op.empty() && op.top() != '('){
                    res.push_back(op.top());
                    op.pop();
                }
                if(op.top() == '('){
                    op.pop();
                }
            }
        }
        else{
            //遇到操作数
            res.push_back(str[i]);
        }
    }
    while(!op.empty()){
        res.push_back(op.top());
        op.pop();
    }
    return true;
}

4.中缀表达式的求值

1.算法思想

中缀表达式计算 = 中缀表达式转后缀表达式 + 后缀表达式的计算

2.代码

可以先转后缀，再通过后缀表达式计算，后缀表达式计算代码如下：

此代码存在的问题和中缀转后缀的一样，尚未作出调整和改进

//通过两个操作数和操作符进行计算
int calculate(int first, int second, char op){
    int res = 0;
    switch (op) {
        case '+':
            res = first + second;
            break;
        case '-':
            res = first - second;
            break;
        case '/':
            res = first / second;
            break;
        case '*':
            res = first * second;
            break;
    }
    return res;
}

//后缀表达式的计算
int postfix_calculate(string str){
    if(str.empty()){
        return 0;
    }
    stack<char> op;
    for(int i = 0; i < str.size(); ++i){
        //isOperator函数在中缀转后缀中实现
        if(!isOperator(str[i])){
            op.push(str[i]);
        }
        else{
            int second = op.top() - '0';
            op.pop();
            int first = op.top() - '0';
            op.pop();
            int temp = calculate(first, second, str[i]);
            op.push(temp + '0');
        }
    }

    return op.top() - '0';
}

5.栈的应用——递归

1.函数调用：函数调用时，需要用一个栈存储以下内容：

1）调用返回地址

2）实参

3）局部变量

2.适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题；递归需要考虑的是递归表达式（递归体）和边界条件（递归出口）；递归算法的缺点就是：太多层可能会导致栈溢出，也可能包含重复计算；

9.队列的应用

1.树的层序遍历

2.图的广度优先遍历

3.操作系统中的应用

1.先来先服务FCFS服务

2.I/O调度

3.进程调度

10.特殊矩阵压缩存储

1.数组的存储结构

1.各数组元素大小相同，且物理上连续存放

2.二维数组

将非线性的数据结构在物理上存储为线性的

1）行优先

2）列优先

2.普通矩阵

1、普通矩阵在计算机中的存储方式是通过二维数组存储

2、对于特殊矩阵，可以通过特殊的存储方式来节省存储空间

3、特殊矩阵：对称矩阵、上三角矩阵、稀疏矩阵

3.对称矩阵

1.只存储主对角线和下三角区；按行优先原则将各个元素存入一维数组中。

2.需要开辟的数组大小 = 1 + 2 + ... + n = (n + 1)*n/2

3.怎么样才能实现对称举证压缩存储后方便使用：

5.三对角矩阵

又称带状矩阵

6.稀疏矩阵

非零元素远远少于矩阵元素的个数