这篇博客为大家带来的是 栈的概念简述、栈的概念选择题、栈的结构选择、C语言实现栈以及栈的一道OJ题。内容相对比较简单。话不多说，我们这就开始。

1. 栈的概念

栈是一个特殊的 线性表。

栈只允许在固定的一段进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，不进行操作的一端称为栈底。

栈中的元素遵守后进先出 (LIFO - Last In First Out) 的原则。也就是先进的后出，后进的先出，就像手枪的弹匣一样。后被装入的子弹，也就是弹匣顶端的子弹先被枪打出。

栈对于数据的管理主要有两种操作：

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，从栈顶进行压栈。

出栈：栈的删除操作叫做出栈，从栈顶进行出栈。

栈的操作流程：

栈的概念选择题：

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

栈的顺序是（）。

A. 12345ABCDE

B. EDCBA54321

C. ABCDE12345

D. 54321EDCBA

答案：B

首先明确栈的原则：后进先出。

将以上元素依次入栈，那么最入栈的最晚出栈，那么1应该最后一个出栈，直接选出结果：EDCBA54321

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

A. 1,4,3,2

B. 2,3,4,1

C. 3,1,4,2

D. 3,4,2,1

答案：C

做对这道题目，我们需要知道，栈不是所有数据入栈后才能出栈的，栈可以入栈部分元素，然后出栈，再入栈其他元素。

下面对每个选项进行分析：

A：1 先入栈，然后出栈，栈空；随后 2, 3, 4 依次入栈。然后将元素全部出栈，栈空。得到结果为：1, 4, 3, 2

B：1, 2 先入栈；然后出栈 2，栈中余1；再入栈 3，出栈 3，栈中余1；再入栈 4，出栈 4，栈中余1；最后出栈 1，栈空。得到结果为：2, 3, 4, 1

C：这种序列答案是绝对不可能的。通过 A、B两个选项和这道题的进栈序列我们也可以找出规律：某个元素的两个相邻元素必定有一个相邻元素与该元素差值为1。否则的话就不符合栈的结构。因为如果第一个元素为3的话，那么就是先入栈 1，2，3，然后出栈。那么无论怎么出栈，第二个元素都不可能为1。2, 4 都有可能，如果还不明白可以画图再想想。

D：1，2，3，先入栈；然后出栈3，栈中余2，1；再入栈 4，然后出栈 4，栈中余2，1；然后将栈中元素全部出栈。得到结果为：3, 4, 2, 1

2. 栈的结构

栈一般可以使用 数组或链表 实现。让我们分析一下使用这两种方法实现，栈的结构分别是什么样的。

在分析之前，我们要明确的一点是，栈只对栈顶的元素进行操作。

数组：

对于数组(顺序表)而言，最方便的就是尾插和尾删，所以我们将 顺序表的尾部 当做栈顶。顺序表的头部 则当做栈底，因为对于顺序表，头部的删除需要挪动大量数据。

链表：

对于链表而言，尤其是 单链表，尾部的插入删除是很麻烦的。但是单链表的头插和头删就很方便，所以可以把 单链表的头部 作为栈顶，单链表的尾部 作为栈底。

如果对于双向链表而言，那么就是随便选了，毕竟双向链表无论哪头插入删除数据都很方便。

抉择：

那么对于顺序栈和链式栈，那个更加好呢？那必定是顺序栈，因为使用顺序栈的尾插尾删非常方便，且 cpu缓存利用率也更高。而且对于顺序栈实现起来相对简单，所以我们接下来就实现顺序栈。

3. 栈的实现

3.1 结构设计

我们既然是实现 顺序栈，那么它的结构肯定就和 顺序表 差不多：

typedef struct Stack
{
  STDatatype* a; // 指向动态开辟的数组
  int capacity; // 栈的容量
  int top; // 标识 栈顶的下一个位置的下标 或 栈顶的下标
}ST;

这里的 top 我们需要好好理解一下。当top的初始值不同时，top可以表示 栈顶的下一个位置的下标 或 栈顶下标。

当 top = 0，top 表示栈顶的下一个位置的下标：

top 初始值为 0，那么第一次压栈就是在0下标插入元素。压栈后，top++。那么当 最后一次压栈后，元素被压在栈顶，那么top 最后的位置就是栈顶的下一个元素的下标处。此时，top就是栈中元素的个数。

当 top = -1，top 表示栈顶的下标：

top 初始值为 -1，那么需要先 ++top，再压栈。否则会越界。当 最后一次压栈时，为先 ++top 再压栈，top最后的位置就是栈顶的下标处。

这个需要理清楚，否则实现判空、计算大小等接口函数的时候会引起错误。

3.2 接口总览

由于 栈的结构 和 操作规则，栈的接口相对来说比较少，且比较简单：

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); // 计算栈的大小

3.3 初始化

我们实现的是顺序栈，那么就和顺序表一样，需要创建结构体变量，传结构体的地址，进行初始化。

在初始化的时候就给栈开上四个单位的空间，并且将起始容量设定为4。

注意了我们这里设定的 top = 0，那么表示 top 为栈顶的下一个位置的下标。

void StackInit(ST* ps)
{
  // 结构体一定不为空，所以需要断言
  assert(ps);
  ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = 0;
}

3.4 销毁

对于栈的销毁，那么我们就只需要释放动态开辟的空间，将指针置空。并将 capacity 和 top 两个变量置 0即可。

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

3.5 判断栈是否为空

我们起初设定 top = 0，所以判断栈是否为空，那么只需要看 top 是否为0就可以了。如果为0，返回真；不为0，返回假。

bool StackEmpty(ST* ps)
{
  assert(ps);
    // 如果 ps->top == 0，返回真
    // 如果 ps->top !=0，返回假
  return ps->top == 0;
}

3.6 压栈

在压栈之前，需要保证空间足够，所以需要先检查容量，如果不够，需要扩容，扩容成功后在考虑压栈的步骤。

我们设定 top 的初始值为 0。那么说明我们入栈的步骤为，先将元素放入，再让 top++。

void StackPush(ST* ps, STDatatype x)
{
  assert(ps);
  // 检查容量
  if (ps->top == ps->capacity)
  {
    STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  // 插入元素
  // top 为栈顶的下一个元素
  // 先插入再 ++ 
  ps->a[ps->top++] = x;
}

3.7 出栈

如果栈中没有元素则不能出栈。所以我们需要调用 StackEmpty 判断是否为空，如果栈空(!StackEmpty(ps)为假)，则断言报错。

出栈的操作和顺序表的尾删操作步骤相似，直接将top--即可。

void StackPop(ST* ps)
{
  assert(ps);
  // 如果栈空，则不能删除
  assert(!StackEmpty(ps));
  ps->top--;
}

3.8 取栈顶元素

由于我们 top 初值设定为 0，top为栈顶的下一个位置的下标，那么 top - 1 就是栈顶的下标，直接返回即可。

但是请注意：当栈为空时，无法取元素，所以需要判断一下。

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

3.9 计算栈的大小

如果一开始top = 0，那么栈的大小就直接是最后 top 的值。也非常简单~

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

4. 完整代码

Stack.h

#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int capacity;
  int top;   // 初始为0，表示栈顶位置下一个位置下标
           // 初始为-1，表示栈顶位置的下标
}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

这里我将 top = 0 和 top = -1 的方案都写了一遍，注释部分为 top = 0，未注释部分为 top = -1：

#define _CRT_SECURE_NO_WARNINGS 1 
#include "Stack.h"
// top 为栈顶的下一个元素
//void StackInit(ST* ps)
//{
//  // 结构体一定不为空
//  assert(ps);
//
//  ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
//  if (ps->a == NULL)
//  {
//    perror("malloc fail");
//    exit(-1);
//  }
//  ps->capacity = 4;
//  ps->top = 0;
//}
//
//void StackDestroy(ST* ps)
//{
//  assert(ps);
//
//  free(ps->a);
//  ps->a = NULL;
//  ps->capacity = ps->top = 0;
//}
//
//void StackPush(ST* ps, STDatatype x)
//{
//  assert(ps);
//  
//  // 检查容量
//  if (ps->top == ps->capacity)
//  {
//    STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
//    if (tmp == NULL)
//    {
//      perror("realloc fail");
//      exit(-1);
//    }
//    ps->a = tmp;
//    ps->capacity *= 2;
//  }
//  // 插入元素
//  // top 为栈顶的下一个元素
//  // 先插入再 ++ 
//  ps->a[ps->top++] = x;
//}
//
//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;
//}
// top 为栈顶 初识值为 -1
void StackInit(ST* ps)
{
  // 结构体一定不为空
  assert(ps);
  ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = -1;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDatatype x)
{
  assert(ps);
  // 检查容量
  // 此时 top 一开始为 -1，不能表示栈中元素的数目
  // top + 1 才是正确的
  if (ps->top + 1 == ps->capacity)
  {
    STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  // 插入元素
  // top 为栈顶元素
  // 先 ++ 再插入
  ps->a[++ps->top] = x;
}
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];
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == -1;
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top + 1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1 
#include "Stack.h"
void TestST1()
{
  ST st;
  StackInit(&st);
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  StackPush(&st, 4);
  StackPush(&st, 5);
  StackPop(&st);
  StackPop(&st);
  StackPop(&st);
  StackPop(&st);
  printf("%d\n", StackTop(&st));
}
int main()
{
  TestST1();
}

5. OJ题 —— 有效的括号

由于我们刚刚学习了栈，而栈实现也比较简单，那么我们就趁热打铁做上一道OJ吧！

链接：20. 有效的括号

描述：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

示例1：

输入：s = “()”

输出：true

示例2：

输入：s = “()[]{}”

输出：true

示例3：

输入：s = “(]”

输出：false

提示：

1 <= s.length <= 104

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

思路：

既然这道题目出现在这篇博客中，那么一定是用栈来解决，而且这道题目的解题思路是十分符合栈的。

首先，我们先要实现一个栈，并创建变量和初始化。

题目要求左括号需要以正确的顺序闭合，且左右括号成对，那么我们可以遍历字符串 s。

遍历过程中让左括号入栈，一旦遇到右括号便取栈顶元素和右括号匹配，并出栈元素。

一旦匹配失败，便返回 false。如果匹配成功，则让 s++ 往后走。

当字符串遍历结束时，判断栈是否为空，如果栈空，则说明为有效的括号；如果栈非空，则说明有左括号没有匹配，那么返回假。(这里只需要返回栈是否为空的值即可)

但是也有一些 易错情况，比如字符串遍历结束，栈中仍有元素：

只有右括号，无左括号，栈空，取元素时越界访问：

注：只有右括号时为提前返回状况。提前返回需要注意栈的销毁，否则会内存泄漏！！！

代码：

typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int capacity;
  int top;   // 初始为0，表示栈顶位置下一个位置下标
}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 = (STDatatype*)malloc(sizeof(STDatatype) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  ps->capacity = 4;
  ps->top = 0;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDatatype x)
{
  assert(ps);
  // 检查容量
  if (ps->top == ps->capacity)
  {
    STDatatype* tmp = (STDatatype*)realloc(ps->a, sizeof(STDatatype) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  // 插入元素
  // top 为栈顶的下一个元素
  // 先插入再 ++ 
  ps->a[ps->top++] = x;
}
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);
            s++;
        }
        else
        {
            // 右括号匹配，栈为空
            if (StackEmpty(&st))
            {
                // 防止内存泄漏
                StackDestroy(&st);
                return false;
            }
            // 取栈顶元素，并出栈
            STDatatype top = StackTop(&st);
            StackPop(&st);
            if ((*s == ')' && top != '(')
                || (*s == ']' && top != '[')
                || (*s == '}' && top != '{'))
            {
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    // 判断遍历结束后，栈是否为空
    bool ans = StackEmpty(&st);
    // 销毁栈
    StackDestroy(&st);
    return ans;
}

【数据结构】C语言实现顺序栈 && OJ题 —— 有效的括号

1. 栈的概念

2. 栈的结构

3. 栈的实现

3.1 结构设计

3.2 接口总览

3.3 初始化

3.4 销毁

3.5 判断栈是否为空

3.6 压栈

3.7 出栈

3.8 取栈顶元素

3.9 计算栈的大小

4. 完整代码

Stack.h

Stack.c

test.c

5. OJ题 —— 有效的括号

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】C语言实现顺序栈 && OJ题 —— 有效的括号

1. 栈的概念

2. 栈的结构

3. 栈的实现

3.1 结构设计

3.2 接口总览

3.3 初始化

3.4 销毁

3.5 判断栈是否为空

3.6 压栈

3.7 出栈

3.8 取栈顶元素

3.9 计算栈的大小

4. 完整代码

Stack.h

Stack.c

test.c

5. OJ题 —— 有效的括号

热门文章

最新文章

相关课程

相关电子书