数据结构（栈）

文章目录

一、概念与结构

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

（栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。一般使用数组作为栈的底层结构对栈的出栈压栈更方便）

二、栈的实现

stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


typedef int STDataType;
typedef struct Stack
  {
	 STDataType* arr;
	 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

初始化栈

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->capacity = ps->top = 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->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++;
}

出栈

bool STEmpty(ST* ps)     
{
	assert(ps);
	return ps->top == 0;    //若栈为空则返回 true
}

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty);   //若栈不为空 ，则返回false，（！false）就为 true

	--ps->top;             //直接 --top

}

取栈顶元素

STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));


	return ps->arr[ps->top - 1]; //直接返回栈顶位置，数组是由下标表示，这里记得 top-1
}

获取栈中有效元素个数

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

test.c

#include"stack.h"

void STTest()
{
	ST st;
	STInit(&st);
	//
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	

	//循环打印出栈数据
	while (!STEmpty(&st))
	{
		STDataType data = STTop(&st);
		printf("%d", data);

		STPop(&st);
	}
	printf("\n栈中的有效个数：%d\n", STSize(&st));

	STDestroy(&st);
}

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

往栈顶插入数据：

//循环打印出栈数据，直到栈为空

三、有效括号（算法题）20. 有效的括号 - 力扣（LeetCode）

下面利用栈的特点来解决一道算法题

先利用上述栈的实现函数定义一个结构体，并且初始化。

bool isValid(char* s) {
    ST st;
    STInit(&st);

    // 遍历字符串 s
    char* ps = s;
    while (*ps != '\0') {
        // 左括号，入栈
        if (*ps == '(' || *ps == '[' || *ps == '{') 
        {
            STPush(&st, *ps);
        }
       
        // 右括号，和栈顶元素比较是否能匹配
        else {
            // 栈为空，直接返回false，意思就是 *ps == 右括号 这种情况
            if (STEmpty(&st)) 
            {
                return false;
            }

            // 当存在左括号，即入栈了，栈不为空才能取栈顶元素
            // 取栈顶元素
            char a = STTop(&st);
            if ((*ps == ')' && a == '(') 
            || (*ps == ']' && a == '[') 
            || (*ps == '}' && a == '{')) 
            {
                // 出栈
                STPop(&st);
            }

            // 当只存在左括号：
            else {
                STDestroy(&st);
                return false;
            }
        }
        ps++;
    }

    // 当ps和a中的符号都能匹配完成，元素全部出栈，栈为空，返回true
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}

思路：