栈和队列(一) 栈操作详解

一、物理结构和逻辑结构

栈和队列都属于逻辑结构，它们既可以用数组实现也可以用链表实现。

二、栈

1、什么是栈

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

2、栈中一些基本操作的实现

利用数组来实现栈的基本操作

代码结构设计：

• Stack.h: 存放链表结构及需要用到的头文件，函数声明等
• Stack.c: 各种操作函数的具体实现

Stack.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>
//方便修改类型
typedef int STDataType;
//栈
typedef struct Stack
{STDataType* a;//实现栈的数组int top;//栈顶int capacity;//栈容量
}ST;//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获得栈顶元素
STDataType STTop(ST* ps);
//获得栈的元素数
int STSize(ST* ps);
//判断栈空
bool STEmpty(ST* ps);

Stack.c

#include "Stack.h"

栈的初始化

void STInit(ST* ps)
{assert(ps);ps->a = NULL;//栈顶元素的下一个ps->top = 0;ps->capacity = 0;
}

栈的销毁

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

入栈

void STPush(ST* ps, STDataType x)
{assert(ps);//空间不足，扩容if (ps->capacity == ps->top){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}//更新入栈后内容ps->a[ps->top] = x;ps->top++;
}

出栈

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

获得栈顶元素

top初始化时是0，是栈顶元素的下一个位置，所以栈顶元素下标是top-1

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

获得栈的元素数

top从0开始，栈内多一个元素它就加1，所以top与元素树大小一致

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

判断栈空

top等于0时栈空

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

三、利用栈解决问题

本题来自LeetCode：有效的括号

有效的括号

示例1：

输入：s=“( )”
输出：true

示例2：

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

示例3：

输入：s=“( ]”
输出：false

• 1 <= s.length <= 104
• s 仅由括号 ‘( )[ ]{ }’ 组成

题目分析：

1. 对于这个题我们需要将字符串内括号的左一半与右一半进行匹配，有"( { [ ] })“、”( ) [ ] { }“等多种情况都是符合情况的，也有像”( { ) }"这种不符合情况的都需要考虑。
2. 如果是左括号则入栈
3. 如果是右括号，取出栈顶元素与之匹配
4. 如果右边括号匹配时栈内已经空了则数量不匹配
5. 匹配结束后栈内不为空则数量不匹配

代码：

这里我们用上面实现的栈操作来完成

bool isValid(char * s){ST st;STInit(&st);char topval;while(*s){if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{//如果栈内为空说明数量不匹配if(STEmpty(&st)){STDestroy(&st);return false;}//取出栈顶元素，然后栈顶元素出栈topval=STTop(&st);STPop(&st);//匹配不成功的情况if((*s==')'&&topval!='(')|| (*s=='}'&&topval!='{')|| (*s==']'&&topval!='[')){STDestroy(&st);return false;}}s++;}//匹配完后如果栈内不为空说明数量不匹配bool ret=STEmpty(&st);STDestroy(&st);return ret;
}