C++ 顺序栈、链式栈、循环队列、链式队列实现及基本操作

顺序栈 (SeqStack) 的设计：

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;
} SeqStack;

void InitStack(SeqStack* S) {
    S->top = -1;
}

bool StackEmpty(SeqStack S) {
    return (S.top == -1);
}

bool Push(SeqStack* S, int x) {
    if (S->top == MAXSIZE - 1) {
        return false;
    }
    S->top++;
    S->data[S->top] = x;
    return true;
}

bool Pop(SeqStack* S, int* x) {
    if (S->top == -1) {
        return false;
    }
    *x = S->data[S->top];
    S->top--;
    return true;
}

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

链式栈 (LinkStack) 的设计：

typedef struct StackNode {
    int data;
    struct StackNode* next;
} StackNode;

typedef struct {
    StackNode* top;
} LinkStack;

void InitStack(LinkStack* S) {
    S->top = NULL;
}

bool StackEmpty(LinkStack S) {
    return (S.top == NULL);
}

bool Push(LinkStack* S, int x) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        return false;
    }
    newNode->data = x;
    newNode->next = S->top;
    S->top = newNode;
    return true;
}

bool Pop(LinkStack* S, int* x) {
    if (S->top == NULL) {
        return false;
    }
    StackNode* temp = S->top;
    *x = temp->data;
    S->top = temp->next;
    free(temp);
    return true;
}

bool GetTop(LinkStack S, int* x) {
    if (S.top == NULL) {
        return false;
    }
    *x = S.top->data;
    return true;
}

循环队列 (CirQueue) 的设计：

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
} CirQueue;

void InitQueue(CirQueue* Q) {
    Q->front = Q->rear = 0;
}

bool QueueEmpty(CirQueue Q) {
    return (Q.front == Q.rear);
}

bool EnQueue(CirQueue* Q, int 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(CirQueue* Q, int* x) {
    if (Q->front == Q.rear) {
        return false;
    }
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return true;
}

bool GetFront(CirQueue Q, int* x) {
    if (Q.front == Q.rear) {
        return false;
    }
    *x = Q.data[Q.front];
    return true;
}

链式队列 (LinkQueue) 的设计：

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
} LinkQueue;

void InitQueue(LinkQueue* Q) {
    Q->front = Q->rear = NULL;
}

bool QueueEmpty(LinkQueue Q) {
    return (Q.front == NULL);
}

bool EnQueue(LinkQueue* Q, int x) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        return false;
    }
    newNode->data = x;
    newNode->next = NULL;
    if (Q->rear == NULL) {
        Q->front = Q->rear = newNode;
    } else {
        Q->rear->next = newNode;
        Q->rear = newNode;
    }
    return true;
}

bool DeQueue(LinkQueue* Q, int* x) {
    if (Q->front == NULL) {
        return false;
    }
    QueueNode* temp = Q->front;
    *x = temp->data;
    Q->front = temp->next;
    if (Q->front == NULL) {
        Q->rear = NULL;
    }
    free(temp);
    return true;
}

bool GetFront(LinkQueue Q, int* x) {
    if (Q.front == NULL) {
        return false;
    }
    *x = Q.front->data;
    return true;
}