数据结构之栈与队列代码

一，顺序栈

顺序栈的定义：

#define MaxSize 10           //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];  //静态数组存放栈中元素
    int top;                 //栈顶元素
}SqStack;

顺序栈的初始化：

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

// 初始化栈
void InitStack(SqStack &S){
    S.top = -1;//初始化栈顶指针
}

// 判断栈是否为空
bool StackEmpty(SqStack S){
    if(S.top == -1)
        return true;
    else
        return false;
}

入栈出栈：

// 新元素进栈
bool Push(SqStack &S, ElemType x){
    // 判断栈是否已满
    if(S.top == MaxSize - 1)
        return false;
    S.data[++S.top] = x;
    return true;
}

// 出栈
bool Pop(SqStack &x, ElemType &x){
    // 判断栈是否为空
    if(S.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;
}

共享栈（两个栈共享同一片空间）：

#define MaxSize 10      //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];//静态数组存放栈中元素
    int top0;                        //0号栈栈顶指针
    int top1;                       //1号栈栈顶指针
}ShStack;

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

二，链栈

链栈的定义：

typedef struct Linknode{
    ElemType data;//数据域
    Linknode *next;//指针域
}Linknode,*LiStack;

void testStack(){
    LiStack L;//声明一个链栈
}

链栈的初始化：

typedef struct Linknode{
    ElemType data;
    Linknode *next;
}Linknode,*LiStack;

// 初始化栈
bool InitStack(LiStack &L){
    L = (Linknode *)malloc(sizeof(Linknode));
    if(L == NULL)
        return false;
    L->next = NULL;
    return true;
}

// 判断栈是否为空
bool isEmpty(LiStack &L){
    if(L->next == NULL)
        return true;
    else
        return false;
}

入栈出栈：

// 新元素入栈
bool pushStack(LiStack &L,ElemType x){
    Linknode *s = (Linknode *)malloc(sizeof(Linknode));
    if(s == NULL)
        return false;
    s->data = x;
    // 头插法
    s->next = L->next;
    L->next = s;
    return true;
}

// 出栈
bool popStack(LiStack &L, int &x){
    // 栈空不能出栈
    if(L->next == NULL)
        return false;
    Linknode *s = L->next;
    x = s->data;
    L->next = s->next;
    free(s);
    return true;
}

三，顺序队列

顺序队列的定义：

#define MaxSize 10;//定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];//用静态数组存放队列元素
    int front, rear;                //队头指针和队尾指针
}SqQueue;

void test{
    SqQueue Q;//声明一个队列
}

顺序队列的初始化：

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

// 初始化队列
void InitQueue(SqQueue &Q){
    // 初始化时，队头、队尾指针指向0
    // 队尾指针指向的是即将插入数据的数组下标
    // 队头指针指向的是队头元素的数组下标
    Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front)
        return true;
    else
        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;
}

四，链队列

链队列的定义：

// 链式队列结点
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}

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

链队列的初始化（带头结点）：

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

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

// 初始化队列
void InitQueue(LinkQueue &Q){
    // 初始化时，front、rear都指向头结点
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}

// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
    else
        return false;
}

入队出队：

// 新元素入队
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;
}

// 队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    // 如果p是最后一个结点，则将队头指针也指向NULL
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}

以上是带头结点的链队列，下面是不带头结点的操作：

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

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

// 初始化队列
void InitQueue(LinkQueue &Q){
    // 不带头结点的链队列初始化，头指针和尾指针都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}

// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == NULL)
        return true;
    else
        return false;
}

// 新元素入队
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;
    }
}

//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == NULL)
        return false;
    LinkNode *s = Q.front;
    x = s->data;
    if(Q.front == Q.rear){
        Q.front = Q.rear = NULL;
    }else{
        Q.front = Q.front->next;
    }
    free(s);
    return true;
}

参考自：https://blog.csdn.net/qq_55593227/article/details/123598044