比特数据结构与算法（第三章_上）栈的概念和实现（力扣：20. 有效的括号）

一、栈（stack）

栈的概念：

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

② 进行数据插入的删除和操作的一端，称为栈顶 。另一端则称为 栈底 。

③ 栈中的元素遵守后进先出的原则，即 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.A

2.c

栈的结构：

数组栈和链式栈

实现栈无非就两种结构：数组结构 和 链式结构，两种结构都可以实现。

数组栈和链式栈哪种结构更好？

相对而言数组的结构实现更优，尾插尾删的效率高，缓存利用率高，它的唯一缺点只是增容，

但是增容1次扩2倍对栈来说本身就比较合理，是无伤大雅的。而链式栈虽然不会空间浪费，

用一个 malloc 申请一个，但是链式栈存在一个致命的缺点：单链表不好出数据，

必须要实现双向链表，否则尾上删除数据将会异常麻烦。

如果硬要使用链式栈：

① 如果用尾做栈顶，尾插尾删，要设计成双向链表，否则删数据效率低。

② 如果用头做栈顶，头插头删，就可以设计成单链表。

本章栈的实现将采用数组结构

二、栈的定义

（数组栈和顺序表定义差不多）

静态栈

简单介绍下静态栈：

typedef char StackDataType;
#define N 10typedef struct Stack 
{
StackDataType _array[N];  //数组
int _top;                 //栈顶
} Stack;

解读：N 给多了浪费给少了又不够用，所以静态栈在实际中是不实用的。静态栈满了就不能扩大了，

而动态栈是 malloc 出来的，不够了可以 realloc 扩容。虽然不实用，但是我们也得认识它，

知道有这么一个东西。

动态栈

本章将采用动态栈实现

typedef int StackDataType;typedef struct Stack 
{StackDataType* array;  //数组int top;               //栈顶int capacity;          //容量
} Stack;

三、栈的实现（完整代码）

实现了顺序表和链表，栈的实现很简单，直接放完整代码了

Stack.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int StackDataType;typedef struct Stack 
{StackDataType* array;  //数组int top;               //栈顶int capacity;          //容量
} Stack;void StackInit(Stack* ps);//初始化
void StackDestroy(Stack* ps);//销毁
void StackPush(Stack* ps, StackDataType x);//进栈
bool StackEmpty(Stack* ps);//判断栈是否为空
void StackPop(Stack* ps);// 出栈
StackDataType StackTop(Stack* ps);//返回栈顶数据
int StackSize(Stack* ps);//返回栈的大小

Stack.c

#include "Stack.h"void StackInit(Stack* ps)//初始化
{assert(ps);ps->array = NULL;ps->top = 0;  // ps->top = -1ps->capacity = 0;
}void StackDestroy(Stack* ps)//销毁
{assert(ps);free(ps->array);ps->array = NULL;ps->capacity = ps->top = 0;
}void StackPush(Stack* ps, StackDataType x)//进栈
{assert(ps);if (ps->top == ps->capacity) {int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);if (tmp_arr == NULL) {printf("realloc failed!\n");exit(-1);}// 更新ps->array = tmp_arr;ps->capacity = new_capacity;}ps->array[ps->top] = x;// 填入数据ps->top++;
}bool StackEmpty(Stack* ps)//判断栈是否为空
{assert(ps);return ps->top == 0; //等于0就是空，就是真
}void StackPop(Stack* ps)// 出栈
{assert(ps);//assert(ps->top > 0);  //防止top为空assert(!StackEmpty(ps));ps->top--;
}StackDataType StackTop(Stack* ps)//返回栈顶数据
{assert(ps);//assert(ps->top > 0);  //防止top为空assert(!StackEmpty(ps));return ps->array[ps->top - 1];
}int StackSize(Stack* ps) //计算栈的大小
{assert(ps);return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}

Test.c

#include "Stack.h"void TestStack1() 
{Stack st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 4);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);//StackPop(&st);printf("%d", StackTop(&st));StackDestroy(&st);
}void TestStack2() 
{// 入栈：1 2 3 4Stack st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);// 出栈：4 3 2 1while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}StackDestroy(&st);
}void TestStack3() 
{// 入栈：1 2 3 4Stack st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);// 提前出栈：4 3printf("%d ", StackTop(&st));StackPop(&st);printf("%d ", StackTop(&st));StackPop(&st);// 入栈：5  6StackPush(&st, 5);StackPush(&st, 6);// 出栈：6 5 2 1while (!StackEmpty(&st)){printf("%d ", StackTop(&st));StackPop(&st);}StackDestroy(&st);
}int main() 
{//TestStack1();//TestStack2();TestStack3();return 0;
}

四、一道栈的OJ题：

力扣链接：20. 有效的括号

难度简单

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

有效字符串需满足：

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

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

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

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

提示：

• 1 <= s.length <= 104

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

bool isValid(char * s){}

解析代码：

这道题用C++写就很简单，用C语言写就需要创建一个栈。（可以用数组什么的，但不好）

我们刚写了一个栈，直接把Stack.h和Stack.c复制粘贴过去,把头文件删掉，

再把typedef int StackDataType; 改成typedef char StackDataType;

typedef char StackDataType;typedef struct Stack 
{StackDataType* array;  //数组int top;               //栈顶int capacity;          //容量
} Stack;void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, StackDataType x);
bool StackEmpty(Stack* ps);
void StackPop(Stack* ps);
StackDataType StackTop(Stack* ps);
int StackSize(Stack* ps);void StackInit(Stack* ps)//初始化
{assert(ps);ps->array = NULL;ps->top = 0;  // ps->top = -1ps->capacity = 0;
}void StackDestroy(Stack* ps)//销毁
{assert(ps);free(ps->array);ps->array = NULL;ps->capacity = ps->top = 0;
}void StackPush(Stack* ps, StackDataType x)//进栈
{assert(ps);if (ps->top == ps->capacity) {int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2;StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity);if (tmp_arr == NULL) {printf("realloc failed!\n");exit(-1);}// 更新ps->array = tmp_arr;ps->capacity = new_capacity;}ps->array[ps->top] = x;// 填入数据ps->top++;
}bool StackEmpty(Stack* ps)//判断栈是否为空
{assert(ps);return ps->top == 0; //等于0就是空，就是真
}void StackPop(Stack* ps)// 出栈
{assert(ps);//assert(ps->top > 0);  //防止top为空assert(!StackEmpty(ps));ps->top--;
}StackDataType StackTop(Stack* ps)//返回栈顶数据
{assert(ps);//assert(ps->top > 0);  //防止top为空assert(!StackEmpty(ps));return ps->array[ps->top - 1];
}int StackSize(Stack* ps) //计算栈的大小
{assert(ps);return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size
}bool isValid(char* s) {Stack st;StackInit(&st);while (*s){if ((*s == '(') || (*s == '[') || (*s == '{')){StackPush(&st, *s);}else{//栈是空，且遇到右括号了，栈里面没有左括号if (StackEmpty(&st)){StackDestroy(&st);return false;}StackDataType top = StackTop(&st);StackPop(&st);if ((top == '(' && *s != ')')|| (top == '[' && *s != ']')|| (top == '{' && *s != '}')){StackDestroy(&st);return false;}}s++;}//如果栈不是空，说明还有左括号没出完，不合题意//此时StackEmpty返回false，相反，栈是空，返回truebool ret = StackEmpty(&st);StackDestroy(&st);return ret;
}

本篇完，下一篇：队列