栈和队列
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.稀疏矩阵
非零元素远远少于矩阵元素的个数
京公网安备 11010502036488号