栈

栈（也叫堆栈，Stack）是一种特殊的线性表，它只能在在表尾进行插入和删除操作，就像下面这样：

我们只能在一端进行插入和删除,当我们依次插入1、2、3、4这四个元素后，连续进行四次删除操作，删除的顺序刚好相反:4、3、2、1,我们可以竖着看：

底部称为栈底，顶部称为栈顶，所有的操作只能在栈顶进行，也就是说，被压在下方的元素，只能等待其上方的元素出栈之后才能取出，就像我们往箱子里里面放的书一样，因为只有一个口取出里面的物品，所以被压在下面的书只能等上面的书被拿出来之后才能取出，这就是栈的思想，它是一种先进后出的数据结构

实现栈也是非常简单的，可以基于我们前面的顺序表或是链表，这里我们先使用顺序表来实现一下，这里我们需要实现两个新的操作：

• pop:出栈操作，从栈顶取出一个元素。
• push：入栈操作，向栈中压入一个新的元素。

首先还是按照我们的顺序表进行编写：

typedef int E;

struct Stack{
    E * array;
    int capacity;
    int top; //这里使用top来表示当前的栈顶位置，存的是栈顶元素的下标
};

typedef  struct  Stack * ArrayStack; //起个别名

接着我们需要写一个初始化方法:

_Bool initStack(ArrayStack stack){
    stack->array = malloc(sizeof(E) * 10);//申请内存空间为十
    if(stack->array == NULL) return 0;
    stack->capacity = 10;
    stack->top = -1;//栈顶默认为-1
    return 1;//每进一个元素top往前进一位
}

int main() {
    struct Stack stack;//建栈
    initStack(&stack);//初始化
}

接着就是栈的两个操作，一个是入栈操作，一个是出栈操作:

_Bool pushStack(ArrayStack stack, E element){
    //入栈操作只需要给元素就可以，不需要index，因为只能从尾部入栈
}

入栈插入到尾部。

_Bool pushStack(ArrayStack stack,E element){
    stack->array[++stack->top] = element;//直接设定栈顶元素
    return 1;
}

主函数测试:

void printStack(ArrayStack stack){
    printf("| ");//栈顶
    for (int i = 0; i < stack->top + 1; ++i) {
        printf("%d, ", stack->array[i]);
    }
    printf("\n");
}

int main() {
    struct Stack stack;//建栈
    initStack(&stack);//初始化
    for (int i = 0; i < 3; ++i) {
        pushStack(&stack,i * 100);//100的倍数，循环3次
    }
    printStack(&stack);
}

测试结果:

可以看到，从栈底到栈顶一次是0、100、200，不过我们现在的push操作还不够完美，因为栈有可能塞满，所以要进行扩容处理：

_Bool pushStack(ArrayStack stack, E element){
    if(stack->top + 1 == stack->capacity) {  //栈顶+1如果等于容量的话，那么说明已经塞满了
        int newCapacity = stack->capacity + (stack->capacity >> 1);   //大体操作和顺序表一致
        E * newArray = realloc(stack->array, newCapacity * sizeof(E));
        if(newArray == NULL) return 0;
        stack->array = newArray;
        stack->capacity = newCapacity;
    }
    stack->array[++stack->top] = element;
    return 1;
}

这样我们的入栈操作就编写完成了，接着是出栈操作，出栈操作我们只需要将栈顶元素取出即可：

_Bool isEmpty(ArrayStack stack){   //在出栈之前，我们还需要使用isEmpty判断一下栈是否为空，空栈元素都没有出个毛
    return stack->top == -1;   
}

E popStack(ArrayStack stack){
    return stack->array[stack->top--];   //直接返回栈顶元素，注意多加一个自减操作
}

出栈测试

int main(){
    struct Stack stack;
    initStack(&stack);
    for (int i = 0; i < 3; ++i) {
        pushStack(&stack, i*100);
    }
    printStack(&stack);
    while (!isEmpty(&stack)) {//当栈不为空
        printf("%d ", popStack(&stack));   //将栈中所有元素依次出栈
    }
}

可以看到，出栈顺序和入栈顺序是完全相反的：

使用数组实现栈除了这种可以自己扩容的之外，也有固定大小的栈，当栈已满时，就无法再进行入栈操作了。

不过有些时候，栈的利用率可能会很低，这个时候我们可以将一个固定长度的数组共享给两个栈来使用：

数组的两头分别作为两个栈的栈底，当两个栈的栈顶指针相遇时（栈顶指针下标之差绝对值为1时），表示栈已满。通过这种方式，我们就可以将数组占用的空间更充分地使用，这样的栈我们称为共享栈。

前面演示了使用顺序表实现栈，接着来看如何使用链表来实现栈，实际上使用链表会更加的方便，可以直接将头结点指向栈顶结点，而栈顶结点连接后续的栈内结点：

当有新的元素入栈，只需要在链表头部插入新的结点即可，我们来尝试编写一下：

typedef int E;

struct LNode {
    E element;
    struct LNode * next;
};

typedef struct LNode * Node;
//初始化
void initStack(Node head){
    head->next = NULL;
}

int main(){
    struct LNode head;
    initStack(&head);
}

接着来编写一下入栈操作：

代码如下:

_Bool pushStack(Node head, E element){//创建头结点，插入元素
    Node node = malloc(sizeof (struct  LNode)); //创建新的节点
    if(node == NULL) return 0; //创建失败就返回0；
    node->next = head->next; //将当前结点的下一个设定为头结点的下一个
    node->element = element; //设置元素
    head->next = node; //将头结点的下一个设定为当前节点
    return 1;
}

编写一个测试：

void printStack(Node head){
    head = head->next;
    while (head){//头结点依次向后遍历
        printf("%d ", head->element);
        head = head->next;
    }
    printf("|\n");//栈顶
}
int main(){
    struct LNode head;
    initStack(&head);
    for (int i = 0; i < 3; ++i) {
        pushStack(&head, i*100);
    }
    printStack(&head);
}

得到结果：

出栈也是同理，所以我们只需要将第一个元素移除即可：

_Bool isEmpty(Node head){
    return head->next == NULL;   //判断栈是否为空只需要看头结点下一个是否为NULL即可
}

E popStack(Node head){
    Node top = head->next;//移除元素
    head->next = head->next->next;//指向下一个元素
    E e = top->element;
    free(top);  //别忘了释放结点的内存
    return e;   //返回出栈元素
}

测试：

int main(){
    struct ListNode head;
    initStack(&head);
    for (int i = 0; i < 3; ++i) {
        pushStack(&head, i*100);
    }
    printStack(&head);
    while (!isEmpty(&head)) {
        printf("%d ", popStack(&head));   //将栈中所有元素依次出栈
    }
}