数据结构入门：栈的基本概念与操作

一、栈的概念

栈是一种特殊的线性表，遵循“后进先出”（LIFO, Last In First Out）的原则。所有插入和删除操作都只能在栈顶进行。栈顶是最后一个插入元素的位置，而栈底则是栈的起始位置。

二、栈的操作

1. 入栈操作 (Push)

入栈操作是指将一个新元素添加到栈顶。每次入栈时，栈顶指针会向上移动一位。如果栈已满，则需要动态扩展栈的空间。

2. 出栈操作 (Pop)

出栈操作是从栈顶移除一个元素，并将栈顶指针向下移动一位。如果栈为空，则无法进行出栈操作。

3. 清空栈

清空栈是指将栈中的所有元素移除，但不释放栈所占用的物理内存空间。可以通过将栈顶指针重新指向栈底来实现。

4. 销毁栈

销毁栈不仅清空栈中的元素，还会释放栈所占用的物理内存空间，使栈完全消失。

三、栈的顺序存储结构

栈可以采用顺序存储结构，即使用数组来实现。顺序栈包含三个主要属性：base（栈底指针）、top（栈顶指针）和stackSize（栈的最大容量）。以下是两种常见的定义方式：

typedef struct {
    ElemType *base;
    ElemType *top;
    int stackSize;
} sqStack;

// 或者

typedef struct {
    ElemType data[MAXSIZE];
    int top;
    int stackSize;
} sqStack;

四、创建一个栈

初始化一个栈时，需要分配初始内存空间，并设置栈顶和栈底指针。以下是一个简单的初始化函数：

#define STACK_INIT_SIZE 100
void initStack(sqStack *s) {
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base) exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

五、计算栈的当前容量

栈的当前容量是指栈中实际存放的元素个数，可以通过计算栈顶指针与栈底指针之间的差值来获得。栈的最大容量则是指栈所能容纳的最大元素数量。

int StackLen(sqStack s) {
    return (s.top - s.base);
}

六、二进制转十进制

栈的特点使得它可以方便地用于二进制转十进制的转换。输入的二进制数字从低位到高位依次入栈，然后从栈顶开始逐位弹出并计算对应的十进制值。

#include 
#include 
#include 

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;

typedef struct {
    ElemType *base;
    ElemType *top;
    int stackSize;
} sqStack;

void InitStack(sqStack *s) {
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base) exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

void Push(sqStack *s, ElemType e) {
    if (s->top - s->base >= s->stackSize) {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if (!s->base) exit(0);
        s->top = s->base + s->stackSize;
        s->stackSize += STACKINCREMENT;
    }
    *s->top++ = e;
}

void Pop(sqStack *s, ElemType *e) {
    if (s->top == s->base) return;
    *e = *--s->top;
}

int main() {
    ElemType c;
    sqStack s;
    int len, i, sum = 0;
    InitStack(&s);
    printf("请输入二进制数，输入#符号表示结束\n");
    while ((c = getchar()) != '#') {
        Push(&s, c);
    }
    len = StackLen(s);
    printf("栈的当前容量是：%d\n", len);
    for (i = 0; i         Pop(&s, &c);
        sum += (c - '0') * pow(2, i);
    }
    printf("转化为十进制数是：%d\n", sum);
    return 0;
}