栈

栈的概念和结构

栈的实现

栈有数组栈和链式栈。数据结构没有规定栈的实现要用数组还是链式，根据自身需要选择即可。

在数组栈中，左边是栈底，右边是栈顶。因为数组尾插尾删方便，也符合栈顶元素先出。

在用单链表实现时，栈顶只能是左边。因为单链表的头插头删方便。

数组栈的实现

总的声明

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>


typedef int STDataType;

typedef struct Stack
{
   
   
    int* a;
    int top;   //标识栈的位置
    int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

//栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

初始化

void STInit(ST* pst)
{
   
   
    assert(pst);

    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;
    //pst->top = -1;
}

上方代码中，pst->top可以初始化为0，也可以为-1。不过两种方法需要区分：

第一种

top指向栈顶元素，当top初始化为0时，会产生歧义，即当有一个数据或者为空时，top都等于0。

下面是解决方法：

分析：当它为空时，top==0。当有一个数据时，top==1，即top是指向栈顶元素的下一个位置。

如果我们想用这种方式实现数组栈，尾插时，就直接把x赋给top位置，然后再让top指向下一位置。

第二种：

分析：我们初始化top为-1，此时为空。当有一个数据时，top==0，刚好指向栈顶元素。尾插时，需要先让top指向下一位置，再插入元素。

两种方法都可以使用，这里我们使用初始化top为0的方法。 注意：使用不同的方法，其他操作的实现会略微不同。

插入

void STPush(ST* pst, STDataType x)
{
   
   
    assert(pst);
    if (pst->top == pst->capacity)
    {
   
   
        int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
   
   
            perror("realloc fail");
            return;
        }
        pst->a = tmp;
        pst->capacity = newcapacity;
    }
    pst->a[pst->top] = x;
    pst->top++;
}

删除

void STPop(ST* pst)
{
   
   
    assert(pst);
    assert(pst->top > 0);
    pst->top--;
}

取栈顶元素

STDataType STTop(ST* pst)
{
   
   
    assert(pst);
    assert(pst->top > 0);
    return    pst->a[pst->top - 1];
}

销毁

void STDestroy(ST* pst)
{
   
   
    free(pst->a);
    pst->a = NULL;
    pst->capacity = pst->top = 0;

}

判断是否为空

bool STEmpty(ST* pst)
{
   
   
    assert(pst);
    //if (pst->top == 0)
    //{
   
   
    //    return true;
    //}
    //else
    //{
   
   
    //    return    false;
    //}
    return pst->top == 0;
}

返回栈的大小

int STSize(ST* pst)
{
   
   
    assert(pst);
    return pst->top;
}

栈的一对多关系

如上图，我们的入栈顺序是123456，出栈顺序是346521。可知入栈顺序和出栈顺序是一对多的关系。入栈顺序只有一种，但出栈的顺序是多样的，不过出栈顺序也要符合先出栈顶元素，不是想出啥就出啥 。

不同的栈

栈有两种，一种是数据结构的栈，一种是内存区域的栈。我们这里的栈是数据结构的栈。而我们所说的栈溢出是指内存区域的栈，在递归中，返回条件出现问题时，容易出现栈溢出。