双栈的基本操作代码c语言

以下是双栈的基本操作代码C语言实现：

1. 采用顺序存储结构实现双栈

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top1; // 栈1的栈顶指针
    int top2; // 栈2的栈顶指针
} DoubleStack;

// 初始化双栈
void InitDoubleStack(DoubleStack *S) {
    S->top1 = -1;
    S->top2 = MAXSIZE;
}

// 判断栈1是否为空
int IsEmpty1(DoubleStack *S) {
    return S->top1 == -1;
}

// 判断栈2是否为空
int IsEmpty2(DoubleStack *S) {
    return S->top2 == MAXSIZE;
}

// 判断双栈是否为空
int IsEmpty(DoubleStack *S) {
    return IsEmpty1(S) && IsEmpty2(S);
}

// 判断栈1是否已满
int IsFull1(DoubleStack *S) {
    return S->top1 + 1 == S->top2;
}

// 判断栈2是否已满
int IsFull2(DoubleStack *S) {
    return S->top2 - 1 == S->top1;
}

// 判断双栈是否已满
int IsFull(DoubleStack *S) {
    return IsFull1(S) || IsFull2(S);
}

// 栈1入栈
void Push1(DoubleStack *S, int x) {
    if (IsFull1(S)) {
        printf("Stack1 is full.\n");
        return;
    }
    S->data[++S->top1] = x;
}

// 栈2入栈
void Push2(DoubleStack *S, int x) {
    if (IsFull2(S)) {
        printf("Stack2 is full.\n");
        return;
    }
    S->data[--S->top2] = x;
}

// 栈1出栈
int Pop1(DoubleStack *S) {
    if (IsEmpty1(S)) {
        printf("Stack1 is empty.\n");
        return -1;
    }
    return S->data[S->top1--];
}

// 栈2出栈
int Pop2(DoubleStack *S) {
    if (IsEmpty2(S)) {
        printf("Stack2 is empty.\n");
        return -1;
    }
    return S->data[S->top2++];
}

2. 采用链表结构实现双栈

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

typedef struct {
    LinkStackPtr top1; // 栈1的栈顶指针
    LinkStackPtr top2; // 栈2的栈顶指针
} DoubleLinkStack;

// 初始化双栈
void InitDoubleLinkStack(DoubleLinkStack *S) {
    S->top1 = NULL;
    S->top2 = NULL;
}

// 判断栈1是否为空
int IsEmpty1(DoubleLinkStack *S) {
    return S->top1 == NULL;
}

// 判断栈2是否为空
int IsEmpty2(DoubleLinkStack *S) {
    return S->top2 == NULL;
}

// 判断双栈是否为空
int IsEmpty(DoubleLinkStack *S) {
    return IsEmpty1(S) && IsEmpty2(S);
}

// 栈1入栈
void Push1(DoubleLinkStack *S, int x) {
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = x;
    p->next = S->top1;
    S->top1 = p;
}

// 栈2入栈
void Push2(DoubleLinkStack *S, int x) {
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = x;
    p->next = S->top2;
    S->top2 = p;
}

// 栈1出栈
int Pop1(DoubleLinkStack *S) {
    if (IsEmpty1(S)) {
        printf("Stack1 is empty.\n");
        return -1;
    }
    LinkStackPtr p = S->top1;
    int x = p->data;
    S->top1 = p->next;
    free(p);
    return x;
}

// 栈2出栈
int Pop2(DoubleLinkStack *S) {
    if (IsEmpty2(S)) {
        printf("Stack2 is empty.\n");
        return -1;
    }
    LinkStackPtr p = S->top2;
    int x = p->data;
    S->top2 = p->next;
    free(p);
    return x;
}