第三章

栈、队列、数组

1.栈

1.1 顺序栈

#define MaxSize 20
typedef int ElemType;
//顺序栈的定义
typedef struct {ElemType data[MaxSize];int top;
}SqStack;
// 初始化顺序栈
void InitSqStack(SqStack &S){S.top = -1;
};
// 入栈(增)
bool Push(SqStack &S,ElemType x){if(S.top == MaxSize-1)return false;//栈已满S.data[++S.top] = x;return true;
}
// 出栈(删)
bool Pop(SqStack&S,ElemType &x){if(top==-1) return false;//栈为空x = S.data[S.top--];return true;
}
// 取栈顶
bool GetTop(SqStack S,ElemType &x){if(S.top==-1)return false;//栈空x = S.data[S.top];return true;
}
// 栈判空
bool IsEmpty(SqStack &s){return S.top==-1? true:false;
}
// 清空栈（逻辑清空）void DestroyStack(SqStack&S){S.top=-1;
}
// 判满
bool IsFull(SqStack&S){//注意：判满的条件可能不同，请根据题意要求设计if(S.top==MaxSize-1)return true;return false;
}

1.2链栈

typedef  int ElemType ;
//链栈的定义(本质上就是单链表，只是所有的操作都限制在表头进行)
typedef struct Stack{ElemType data;struct Stack *next;
} liStack ,*LiStack;// 初始化// 带头结点的链栈
bool InitLiStack(LiStack&S){S = new liStack;if(S==nullptr)return false;S->next = nullptr;return true;
}
//不带头结点的链栈
bool InitLiStack2(LiStack &S){S  = nullptr;return true;
}
void Push(LiStack &S, ElemType x) {LiStack t = new Stack;if (!t) {std::cerr << "Memory allocation failed for new stack node." << std::endl;return;}t->data = x;t->next = S->next;S->next = t;
}//入栈（不带头结点）
void Push2(LiStack&S,ElemType x){//cout<<"insert ele:"<<x<<endl; //ouput DebugliStack*t = new liStack;t->data = x;t->next = S;S = t;
}
// 出栈
bool Pop(LiStack&S,ElemType &x){if(!S->next)return false;liStack*q = S->next;x = q->data;S->next = q->next;delete q;return true;
}
// 出栈（不带头节点）bool Pop2(LiStack&S,ElemType &x){if(S==nullptr)return false;liStack*q = S;x = q->data;S = q->next;delete q;return true;
}// 取栈顶（带头结点）
bool GetTop(LiStack S,ElemType &x){if(S->next==nullptr)return false;x = S->next->data;return true;
}
// 取栈顶（不带头结点）
bool GetTop2(LiStack S ,ElemType &x){if(S==nullptr)return false;x = S->data;return true;
}//工具函数（生成随机数）
int MyRandom(int low,int high) {// 创建一个随机数引擎std::random_device rd;std::mt19937 gen(rd()); // 使用 Mersenne Twister 引擎// 定义随机数分布std::uniform_int_distribution<> dis(low, high); // 生成范围在 [1, 100] 内的整数// 生成随机数int random_number = dis(gen);return random_number;
}
void print(LiStack&S){liStack* p = S;while(p){cout<<p->data<<"->";p = p->next;}cout<<"NULL"<<endl;
}while(p){cout<<p->data<<"->";p = p->next;}cout<<"NULL"<<endl;
}