【栈与队列】——栈的实现及应用-阿里云开发者社区

【栈与队列】——栈的实现及应用

2023-04-25 92

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【栈与队列】——栈的实现及应用

概念

栈

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈

栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈

栈的删除操作叫做出栈。出数据也在栈顶。

总结起来，即栈是一种特殊的线性表，数据的插入以及删除操作都在栈顶，遵循后进先出的原则，即后进来的元素在进行出栈时先于早进来的元素。

栈的实现

这里我们发现，实现栈的话，用单链表或者数组都可以，单链表的头插与头删就满足后进先出，而数组即我们前面写过的顺序表，数组的尾插与尾删也满足后进先出的原则。这两种实现方式的时间复杂度都为O（1），并无什么差别，这里我们就用顺序表（数组）来实现。

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
  STDataType* _a;
  int _top;  // 栈顶
  int _capacity;  // 容量 
}Stack;

初始化栈

首先是初始化，这里我们先初始化为一个容量为4的栈,

// 初始化栈 
void StackInit(Stack* ps)
{
  assert(ps);
  ps->_a = (STDataType*)malloc(sizeof(STDataType)*4);
  ps->_top = 0;//栈顶元素的下一个
  ps->_capacity = 4;//栈的初始容量为4
}

这里需要注意的是，我们用_top来表示栈顶，_top== 0 和 top == -1是两个概念，等于0时表示的是栈顶的下一个，等于-1时才表示栈顶。如下图：

_top=-1

_top=0

注意两者区别即可。

入栈

接下来是入栈，这里我们由于是写的一个能动态增长的栈，所以我们再进行入元素之前，要先判断这个栈是否满了，如果满了的话，就要进行扩容。

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
  assert(ps);
  //判断增容
  //_top==_capacity说明已经满了，要进行扩容
  if (ps->_top == ps->_capacity)
  {
  //容量调整为原来的二倍
  STDataType* tmp = realloc(ps->_a, 2 * ps->_capacity * sizeof(STDataType));
  if (tmp == NULL)
  {
    perror("realloc fail");
    exit(-1);
  }
  ps->_a = tmp;
  ps->_capacity *= 2;//记得更新_capacity
  }
  //接下来才是入栈，先入元素，_top再++。（假如_top初始化是-1的话，要先++，再入元素）
  ps->_a[ps->_top] = data;
  ps->_top++;
}

出栈

出栈的实现也很简单，就相当于数组尾删，直接_top- - 即可，不过要注意的是，假如栈是个空栈，就不能进行出栈操作了。这里我们用assert进行判断

// 出栈 
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));//判断是否为空
  ps->_top--;
}

获取栈顶元素

这里需要注意的是，由于我们一开始初始化的_top=0，它表示的是栈顶的下一个元素，原因上面也已经解释过了，所以我们获取栈顶元素时的下标实际为_top-1，不过注意空栈是不能获取栈顶元素的。

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->_a[ps->_top - 1];
}

获取栈中有效元素个数

我们的_top其实就表示了我们的元素个数，因为我们是从0开始的，进一个元素之前就++了，假如是从-1开始的话，有效元素个数应为_top+1个。

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->_top;
}

判断栈是否为空

空栈就是_top等于0的情况下。

// 检测栈是否为空，如果为空返回true,否则false
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->_top == 0;
}

栈的销毁

释放malloc开辟的空间后，将所有元素置空置0

/
/ 销毁栈 
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->_a);
  ps->_capacity = ps->_top = 0;
  ps->_a = NULL;
}

栈的应用

有人可能会问，这个东西能干嘛啊，其实它的作用也很大的，就比如后面要学的一些知识，比如二叉树的层序遍历、快排的非递归实现等等，都会用得到，这里我们拿一道力扣上的题来举个应用例子。

题目如下：

对于该题，以我们的水平，假如不知道栈的话，做这个可能有点小麻烦，可能有人说用双指针遍历等等，其实都很难解决，但是用栈的特点，就很好做了。

我们直接左括号入栈，当遇到右括号时出栈进行匹配，这里就用到了后进先出的特点完美解决问题。如下：

代码实现：（由于这里我们是用C语言写的，不像C++等语言可以直接调用库来使用，所以该题我们要自己创造出一个栈，就用我们上面写的，同时由于是字符串类型，所以记得将typedef int 改为char类型…）

这里由于为了不再重复的占用字数，我只将实现的代码写在下面，上面栈的实现直接拷贝到该函数上面即可。

void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->_a);
  ps->_capacity = ps->_top = 0;
  ps->_a = NULL;
}
bool isValid(char * s){
    Stack st;
    //初始化栈
    StackInit(&st);
    while(*s)
    {
        //左括号入栈
        if(*s == '[' || *s=='('|| *s== '{')
        {
            StackPush(&st,*s);
            s++;
        }
        else
        {
            //假如没有左括号，空栈
            if(StackEmpty(&st))
            {
                return false;
            }
            //top存放栈顶元素
            char top=StackTop(&st);
            StackPop(&st);//出栈
            //进行对比
            if((*s==']'&& top !='[')
            ||(*s==')'&& top !='(')
            ||(*s=='}'&& top !='{'))
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    //栈不为空
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}