【数据结构与算法】第6课—数据结构之栈

1. 栈

• 栈：也是一种线性表，其数据结构与动态顺序表的数据结构类似
• 栈分为栈顶和栈底，在栈中，插入数据和删除数据被称为入栈和出栈
• 栈的相关操作都是在栈顶实现的，而栈底通常不会改变
• 栈的底层结构可以通过数组和链表实现，但是链表在入栈和出栈操作上，会出现指针指向改变的问题，相对而言，数组反而只需要改变其size(在栈中被称为栈顶top)大小即可，因此用数组来实现栈的底层更佳

2. 栈的初始化和栈的销毁

//初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

3. 入栈和出栈（压栈）

//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//空间满了--增容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr,newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//直接尾插
	ps->arr[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps && ps->top);
	ps->top--;
}

4. 取栈顶元素并打印

//取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps && ps->arr);
	return ps->arr[ps->top - 1];
}

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

//打印
void StackPrint(Stack* ps)
{
	assert(ps);
	while (ps->top)
	{
		//栈顶元素依次出栈
		STDataType top = StackTop(ps);
		printf("%d ", top);
		//每次出栈top--
		ps->top--;
	}
}

5. 栈的练习题

5.1 有效的括号

• 题目

• 思路

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//栈的数据结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
}Stack;

//初始化
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//空间满了--增容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//直接尾插
	ps->arr[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps && ps->top);
	ps->top--;
}

//取栈顶元素
STDataType StackTop(Stack* ps)
{
	return ps->arr[ps->top - 1];
}

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

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

bool isValid(char* s)
{
	Stack st;
	StackInit(&st);
	char* pi = s;
	//遍历字符串
	while (*pi != '\0')
	{
		//入栈
		if (*pi == '(' || *pi == '[' || *pi == '{')
			StackPush(&st, *pi);
		else
		{
			//取栈顶，判断
			char top = StackTop(&st);
			if ((top == '(' && *pi == ')') || (top == '[' && *pi == ']') || (top == '{' && *pi == '}'))
				StackPop(&st);
			else
			{
				StackDestroy(&st);
				return false;
			}
		}
		pi++;
	}
	//对比结束
	bool ret = StackEmpty(&st) ? true : false;
	StackDestroy(&st);
	return ret;
}