第三章

栈、队列、数组

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 Debug
    liStack*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;
}