【数据结构与算法】栈的实现&&有效的括号-阿里云开发者社区

👉栈的概念及结构👈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端

称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则。

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

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

知道了栈进出数据的原则，那现在我们来做两道选择题。可以先看一下题目，做完再来看答案和解析。

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出

栈的顺序是（）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

答案和解析：

1.答案：B；解析：因为栈结构符合后进先出的原则，且1、2、3、4、5、A、B、C、D、E依次入栈，所以出栈顺序为E、D、C、B、A、5、4、3、2、1。

2.答案：C；解析：A 选项元素 1 入栈后出栈，元素 2、3、4 依次入栈后依次出栈；B 选项元素 1 入栈，元素 2 入栈后出栈，元素 3 入栈后出栈，元素 4 入栈后出栈，最后元素 1 出栈；D 选项元素 1、2、3 依次入栈，元素 3 出栈，元素 4 入栈后出栈，最后元素 2 、1 依次出栈。

👉栈的实现👈

栈的实现一般可以使用顺序表或者链表实现，相对而言顺序表的结构实现更优一些。因为顺序表在尾上插入数据的代价比较小。如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，顺序表的尾插和尾删不需要搬移元素效率非常高，因此使用顺序结构实现栈更简单.。

注意：本篇博客所讲述的栈是数据结构里的栈，而不是操作系统里内存的栈区（大约8M）。这两者是有区别的，但它们都符合后进先出的原则。

栈可以用数组或者链表来实现，在这里博主采用数组的形式来实现。大家也可以尝试采用链表的形式来实现栈。

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// ̬静态栈
//#define N 100
//typedef int STDataType;
//struct Stack
//{
//  STDataType a[N];
//  int top;
//};
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);

栈的实现相较于顺序表的实现简单太多了。栈要实现的函数接口有初始化栈、销毁栈、数据入栈、数据出栈、返回栈顶元素、判断栈是否为空以及栈中元素的个数。

Stack.c

#include "Stack.h"
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

初始化栈

1.对ps进行断言

2.ps->a = NULL不指向任何空间

3.ps->top = ps->capacity = 0

4.注意：ps->top = 0表示top为栈顶元素位置的下一个位置，其大小也表示栈中元素的个数；ps->top = -1表示top为栈顶元素的位置。

void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

销毁栈

1.释放a指向的空间free(ps->a)，并将a置为空ps->a = NULL

2.ps->top = ps->capacity = 0

void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

数据入栈

1.判断是否需要扩容。扩容分两种情况：1.容量为 0 时，先给四个空间；2.容量不为 0 时，容量扩大到两倍

2.数据入栈ps->a[ps->top] = x，元素个数加一ps->top++

void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}

数据出栈

1.调用StackEmpty函数判断栈是否为空

2.数据出栈--ps->top

void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}

返回栈顶元素

1.调用StackEmpty函数判断栈是否为空

2.返回栈顶元素return ps->a[ps->top - 1]

STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}

判断栈是否为空

因为ps->top表示栈中元素的个数，所以返回ps->top == 0就能判断栈是否为空了

bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}

栈中元素的个数

直接返回元素个数return ps->top

int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

Test.c

以下为栈函数接口的测试代码，大家可以参考一下。因为函数接口比较简单，所以就没有弄出多个函数来一一测试它们的功能。虽然栈的函数接口都很简单，但是我们也要通过函数接口来操作栈，而不能通过下图的方式。还要值得注意的是：打印栈中的数据是通过打印栈顶数据、Pop掉栈顶数据的方式来实现的。

原因就是我们并不知道人家的函数接口时怎么实现的。比如：栈的初始化有两种方式 top = 0 和 top = -1。

#include "Stack.h"
// 解耦 -- 低耦合 高内聚
// 数据结构建议不要直接访问结构数据，一定要通过函数接口访问
void StackTest()
{
  ST st;
  StackInit(&st);
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  printf("%d ", StackTop(&st));
  StackPop(&st);
  printf("%d ", StackTop(&st));
  StackPop(&st);
  StackPush(&st, 4);
  StackPush(&st, 5);
  while (!StackEmpty(&st))
  {
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  printf("\n");
  StackDestroy(&st);
}
int main()
{
  StackTest();
  return 0;
}

👉有效的括号👈

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

提示：

1 <= s.length <= 10^4

s 仅由括号 ‘()[]{}’ 组成

思路：这道题目可以使用上面实现的栈来解决。利用while循环变量字符串s，当遇到左括号，那么左括号入栈；如果遇到右括号，那么左括号出栈匹配。如果左括号和右括号不匹配或者栈里没有左括号了，就直接返回false。循环结束时，如果栈不为空，那么就说明说明栈中还有左括号没有和右括号匹配上。没有匹配上，就返回false。

typedef char STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);
STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  // 扩容
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  --ps->top;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
/以上是自己实现的栈，以下是括号匹配函数
bool isValid(char * s)
{
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '{' || *s == '[')
        {
            StackPush(&st, *s);
        }
        else
        {
            // 遇到右括号了，但是栈为空，说明
            // 没有左括号和右括号匹配了，返回false
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            StackPop(&st);
            // 左括号和右括号匹配不上
            if((top == '(' && *s != ')') 
            ||(top == '{' && *s != '}')
            ||(top == '[' && *s != ']'))
            {
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }
    // 如果栈不是空，说明栈中还有左括号没有和右括号匹配上
    // 没有匹配，返回的是false
    bool flag = StackEmpty(&st);
    StackDestroy(&st);
    return flag;
}

【数据结构与算法】栈的实现&&有效的括号

👉栈的概念及结构👈

👉栈的实现👈

Stack.h

Stack.c

Test.c

👉有效的括号👈

热门文章

最新文章

相关课程

相关电子书

相关实验场景