数据结构：多栈共享技术

一个程序中出现需要同时使用多个栈的情况，难以对栈空间的大小进行估计。

初始化和定义

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top1;  // 第一个栈的栈顶指针//这里的int是栈的数据类型
    int top2;  // 第二个栈的栈顶指针
} SharedStack;

// 初始化两栈共享技术的数据结构
void initSharedStack(SharedStack *stack) {
    stack->top1 = -1;  // 第一个栈的栈顶指针初始化为-1
    stack->top2 = MAX_SIZE;  // 第二个栈的栈顶指针初始化为MAX_SIZE
}

进栈和出栈操作

这一个为封装的明显简单了许多，其实还有一个没分开的就不写出来了

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top1;  // 第一个栈的栈顶指针
    int top2;  // 第二个栈的栈顶指针
} SharedStack;

// 初始化两栈共享技术的数据结构
void initSharedStack(SharedStack *stack) {
    stack->top1 = -1;  // 第一个栈的栈顶指针初始化为-1
    stack->top2 = MAX_SIZE;  // 第二个栈的栈顶指针初始化为MAX_SIZE
}

// 判断第一个栈是否为空
int isEmpty1(SharedStack *stack) {
    return stack->top1 == -1;
}

// 判断第二个栈是否为空
int isEmpty2(SharedStack *stack) {
    return stack->top2 == MAX_SIZE;
}

// 判断第一个栈是否已满
int isFull1(SharedStack *stack) {
    return stack->top1 + 1 == stack->top2;
}

// 判断第二个栈是否已满
int isFull2(SharedStack *stack) {
    return stack->top2 - 1 == stack->top1;
}

// 向第一个栈中压入元素
void push1(SharedStack *stack, int value) {
    if (isFull1(stack)) {
        printf("Stack 1 is full.\n");
        return;
    }
    stack->data[++stack->top1] = value;
}

// 向第二个栈中压入元素
void push2(SharedStack *stack, int value) {
    if (isFull2(stack)) {
        printf("Stack 2 is full.\n");
        return;
    }
    stack->data[--stack->top2] = value;
}

// 从第一个栈中弹出元素
int pop1(SharedStack *stack) {
    if (isEmpty1(stack)) {
        printf("Stack 1 is empty.\n");
        return -1;
    }
    return stack->data[stack->top1--];
}

// 从第二个栈中弹出元素
int pop2(SharedStack *stack) {
    if (isEmpty2(stack)) {
        printf("Stack 2 is empty.\n");
        return -1;
    }
    return stack->data[stack->top2++];
}

2.栈的空闲结点的申请和释放，和链表申请结点的方法是一样的，准确来说系统的分配空间就有点类似于栈

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* freeNodePool = NULL; // 空闲结点池

// 申请一个新结点
Node* allocateNode() {
    if (freeNodePool == NULL) {
        cout << "无法申请新结点，空闲结点池为空" << endl;
        return NULL;
    }
    
    Node* newNode = freeNodePool;
    freeNodePool = freeNodePool->next;
    newNode->next = NULL;
    
    return newNode;
}

// 归还空闲结点
bool deallocateNode(Node* node) {
    if (node == NULL) {
        cout << "无需归还空结点" << endl;
        return false;
    }
    
    node->data = 0;
    node->next = freeNodePool;
    freeNodePool = node;
    
    return true;
}

int main() {
    // 初始化空闲结点池
    Node* node1 = new Node();
    Node* node2 = new Node();
    Node* node3 = new Node();
    freeNodePool = node1;
    node1->next = node2;
    node2->next = node3;
    
    // 申请一个新结点
    Node* newNode = allocateNode();
    if (newNode != NULL) {
        cout << "申请到的新结点地址：" << newNode << endl;
    }
    
    // 归还空闲结点
    bool success = deallocateNode(newNode);
    if (success) {
        cout << "归还空闲结点成功" << endl;
    }
    
    return 0;
}