栈

栈（Stack）是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。

栈的顺序实现

// 顺序栈的类型定义 
const int Maxsize = 6;      // 顺序栈的容量 
typedef struct seqstack
{
    DataType data[Maxsize]; // 存储栈中数据元素的数组 
    int top;                // 标志栈顶位置的变量，范围为 0 ~ (Maxsize - 1) 
} SeqStk;


// 初始化
int InitStack(SeqStk *stk)
{
    stk->top = 0;
    return 1;
}

// 判栈空
int EmptyStack(SeqStk *stk)
{
    if (stk->top == 0)
        return 1;
    else
        return 0;
} 

// 进栈
int Push(SeqStk *stk, DataType x)
{
    if (stk->top == Maxsize - 1) { // 判断栈是否满 
        error("栈已满");
        return 0;
    } else {
        stk->top++;
        stk->data[stk->top] = x;
        return 1;
    }
} 

// 出栈 
int Pop(SeqStk *stk)
{
    if (EmptyStack(stk)) { // 判断栈是否下溢 
        error("下溢");
        return 0;   
    } else {
        stk->top--; // 此时数据虽然仍在数组中，但它已经不是栈的数据元素了 
        return 1;
    }
}

// 取栈顶元素
DataType GetTop(SeqStk *stk)
{
    if (EmptyStack(stk)) {
        return NULLData; // 栈空，返回空元素             
    } else {
        return stk->data[stk->top];
    }
} 

栈的链接实现

// 链栈的类型定义
typedef struct node
{
    DataType data;
    struct node *next;
} LkStk;

// 初始化
void InitStack(LkStk *LS)
{
    LS = (LkStk *)malloc(sizeof(LkStk));
    LS->next = NULL;                    // 建立一个空栈 
} 

// 判栈空
int EmptyStack(LkStk *LS)
{
    if (LS->next == NULL)
        return 1;
    else 
        return 0;
} 

// 进栈
int Push(LkStk *LS, DataType x)
{
    // 在进栈操作算法中采用前插操作，新增结点始终插入到头结点之后 
    LkStk *temp;
    temp = (LkStk *)malloc(sizeof(LkStk)); // temp 指向申请的新结点
    temp->data = x;
    temp->next = LS->next;                 // temp 的 next 域指向原来的栈顶结点
    LS->next = temp;                       // 指向新的栈顶结点。说明：LS 指向链表的头结点，LS->next 指向栈顶结点，栈顶结点为首结点。 
} 

// 出栈 
int Pop(LkStk *LS)
{
    LkStk *temp;
    if (! EmptyStack(LS)) {
        temp = LS->next;       // temp 指向栈顶结点
        LS->next = temp->next; // 原栈顶的下一个结点成为新的栈顶
        free(temp);            // 释放原栈顶结点空间
        return 1; 
    } else {
        return 0;
    }
}

// 取栈顶元素
DataType GetTop(LkStk *LS)
{
    if (! EmptyStack(LS)) {
        return LS->next->data;
    } else {
        return NULLData;
    }
}