28 线性表 · 栈

目录

一、概念与结构

（一）概念

1、栈

2、压栈

3、出栈

4、底层实现       

二、栈的实现

三、栈的算法题

一、概念与结构

（一）概念

1、栈

        一种特殊的线性表，只允许在固定的一端进行插入和删除操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。

2、压栈

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

3、出栈

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

4、底层实现       

        底层使用数组、单链表、双向链表来实现都是没问题的。

        从内存角度出发，双向链表的节点比单链表节点多一个指正，在32位机器中就多出了4字节内存，在64位机器中就多出了8字节内存。在优化的角度来看，可以先排除掉双向链表。

        从增容的效率出发，数组每次是空间×2地去增容，相比单链表的尾插每增加一个节点就要动态申请一个节点大小的内存的频率，数组的增容频率要小很多，会减少系统的开销。

        从数据读取角度来看，数组的读取频率也比单链表的读取频率要低，因为从主存中读取数据时是取一块连续的空间到缓存中读取，而单链表的地址不一定是连续的，可能要多次从主存中进行读取，所以综合上面增容效率的论述，在优化的角度来看，可以排除单链表。

        综上所述，栈的底层为数组会更优。

二、栈的实现

        栈的常用名：Stack。

栈的编写：

① 头文件：定义栈的结构体，声明要提供的操作（起到目录作用）。

② cpp文件：编写具体实现各种操作（起到内容作用）。

③ 测试文件：测试是否可以正常运行。

Stack.h

#pragma once
#include<stdlib.h>
#include<iostream>
#include<assert.h>
#include<stdbool.h>

using namespace std;
typedef int STDatapype;
//定义栈结构
typedef struct Stack
{
	STDatapype* arr;//栈底层为数组
	int capecity;//栈底层数组的总元素个数
	int top;//栈顶，相当于顺序表中的有效元素个数size
}ST;

//一、初始化栈、销毁栈、增容栈的数组、判断栈是否为空、取栈顶元素、获取栈中有效元素个数
//（一）初始化栈
void STInit(ST& st);
//（二）销毁栈
void STDestroy(ST& st);
//（三）增容栈的数组
void STCapacity(ST& st);
//（四）判断栈是否为空
bool STEmpty(ST& st);
//（五）取栈顶元素
STDatapype STGetTop(ST& st);
//（六）获取栈中有效元素个数
int STGetSize(ST& st);

//二、栈顶插入
void STPush(ST& st, STDatapype num);

//三、栈顶删除
void STPop(ST& st);

Stack.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

//一、初始化栈、销毁栈、增容栈的数组、判断栈是否为空、取栈顶元素、获取栈中有效元素个数
//（一）初始化栈
void STInit(ST& st)
{
	st.arr = nullptr;
	st.capecity = st.top = 0;
}
//（二）销毁栈
void STDestroy(ST& st)
{
	if (st.arr)
	{
		free(st.arr);
		st.arr = nullptr;
	}
	st.capecity = st.top = 0;
}
//（三）增容栈的数组
void STCapacity(ST& st)
{
	if (st.capecity == st.top)
	{
		st.capecity = st.capecity == 0 ? 4 : st.capecity * 2;
		STDatapype* new_st = (STDatapype*)realloc(st.arr, sizeof(STDatapype) * (st.capecity));
		if (new_st == nullptr)
		{
			perror("STCapecity reallco fail");
			exit(1);
		}
		st.arr = new_st;
	}
}
//（四）判断栈是否为空
bool STEmpty(ST& st)
{
	return st.top == 0;
}
//（五）取栈顶元素(只能取到栈顶元素)
STDatapype STGetTop(ST& st)
{
	assert(!STEmpty(st));
	return st.arr[st.top - 1];

}
//（六）获取栈中有效元素个数
int STGetSize(ST& st)
{
	return st.top;
}

//二、栈顶插入
void STPush(ST& st, STDatapype num)
{
	STCapacity(st);
	/*st.arr[st.top] = num;
	st.top++;*/
	st.arr[st.top++] = num;
}

//三、栈顶删除
void STPop(ST& st)
{
	//assert(st.arr);
	assert(!STEmpty(st));
	st.top--;
	if (st.top <= 0)
		st.arr = nullptr;
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void test()
{
	ST st;
	STInit(st);

	for (int i = 1; i < 6; i++)
	{
		STPush(st, i);
	}

	/*for (int i = 1; i < 11; i++)
	{
		STPop(st);
		STPrint(st);
	}
	STPrint(st);*/

	while (!STEmpty(st))
	{
		STDatapype num = STGetTop(st);
		cout << num << " ";
		STPop(st);
	}
	cout << endl;
 }

int main()
{
	test();
	return 0;
}

        注意：

                ① 栈没有遍历打印的操作，因为栈不能通过下标进行随机访问其中的数据，只能通过下标拿到栈顶元素。

                ② 空栈的时候，栈底等于栈顶。

三、栈的算法题

        题目链接如下：

                https://leetcode.cn/problems/valid-parentheses/description/

        解题思路：

                使用栈的结构与方法，先遍历字符串数组，若字符串数组中为左括号（无论大中小括号），把该元素压入自定义的栈中；若字符串数组中为右括号（无论大中小括号）则取出栈顶元素进行判断，看看是否为一对，若为一对就把栈顶元素出栈，不是则return false；到最后要销毁栈

        注意点：

                ① 循环结束后要检查栈是否为空，若为空则是括号对应的情况，return true；否则 return false。

                ② 在取出栈顶元素时，要判断栈顶元素是否为空，若为空则 return false，因为要考虑只存在右括号的情况。

        答案代码如下：

typedef char STDataType;
//定义栈结构
typedef struct Stack
{
	STDataType* arr;//栈底层为数组
	int capacity;//栈底层数组的总元素个数
	int top;//栈顶，相当于顺序表中的有效元素个数size
}ST;
//初始化栈
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
//销毁栈
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//插入
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	
	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		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;
}
//判断是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//删除尾元素
void STPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}
//取栈顶元素
STDataType STGetTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
 
bool isValid(char* s) {
    //创建栈结构并初始化
    ST st;
    STInit(&st);

    //遍历s，若为左括号就入栈；若为右括号就与栈顶元素进行比较
    char* ps = s;
    while(*ps)
    {
        if(*ps == '(' || *ps == '[' || *ps == '{')
        {
            STPush(&st, *ps);
        }
        else
        {
            if(StackEmpty(&st))//栈不为空才能取栈顶元素，若为空直接返回false
                return false;
            char top_ele = STGetTop(&st);
            if((*ps == ')' && top_ele == '(')
            || (*ps == ']' && top_ele == '[')
            || (*ps == '}' && top_ele == '{'))
            {
                STPop(&st);
            }
            else
            {
                STDestroy(&st);
                return false;
            }
        }
        ps++;
    }
    //销毁栈
    bool re = StackEmpty(&st);
    STDestroy(&st);
    return re;
}

        以上内容仅供分享，若有错误，请多指正。