# 链栈的基本原理

从数据结构角度看,栈也属于线性表范畴,但在基本的实现方面却受到限制。
对于链栈来说,就是受限的链表,
并且,栈内元素应满足`先入后出``后入先出`的原则,
此外,当栈内不含任何元素时,称为`空栈`

# 链栈的基本实现

Link_Stack_.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Element;
struct Link_Node
{
	Element element;
	struct Link_Node* next;
};
struct Link_Stack_Pointer
{
	struct Link_Node* top;
	int space;
};
void Init_Stack(struct Link_Stack_Pointer* L_S);
void Push(struct Link_Stack_Pointer* L_S,Element element);
void Pop(struct Link_Stack_Pointer* L_S);
int get_length(struct Link_Stack_Pointer* L_S);
void Show_Menu();
void Show_Stack(struct Link_Stack_Pointer* L_S);
void Clean_Stack(struct Link_Stack_Pointer* L_S);
void destroy_Stack(struct Link_Stack_Pointer* L_S);
Link_Stack_functions.c
#include"Link_Stack_.h"
void Init_Stack(struct Link_Stack_Pointer* L_S)
{
	L_S->top = NULL;
	L_S->space = 0;
}
void Push(struct Link_Stack_Pointer* L_S, Element element)
{
	struct Link_Node* L_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	L_Node->element = element;
	L_Node->next = NULL;
	if (!(L_S->space))
	{
		L_S->top = L_Node;
		L_S->space++;
	}
	else
	{
		L_Node->next = L_S->top;
		L_S->space++;
		L_S->top = L_Node;
	}
	printf("%d入栈\n", L_Node->element);
}
void Pop(struct Link_Stack_Pointer* L_S)
{
	struct Link_Node* L_Node = L_S->top;
	printf("%d出栈\n", L_Node->element);
	L_S->top = L_Node->next;
	free(L_Node);
	L_S->space--;
}
int get_length(struct Link_Stack_Pointer* L_S)
{
	printf("当前存储空间长度为%d\n", L_S->space);
	return L_S->space;
}
void Show_Menu()
{
	printf("\n*****************************************\n");
	printf(" [1] Push        ******[2] Pop          *\n");
	printf(" [3] get_length  ******[4] Show_Stack   *\n");
	printf(" [5] Clean_Stack*******[6] destroy_Stack*\n");
	printf(" [0] Exit_System******                  *");
	printf("\n*****************************************\n");
}
void Show_Stack(struct Link_Stack_Pointer* L_S)
{
	struct Link_Node* L_Node = L_S->top;
	while (NULL != L_Node->next)
	{
		printf("%d\n", L_Node->element);
		L_Node = L_Node->next;
	}
	printf("%d\n", L_Node->element);
}
void Clean_Stack(struct Link_Stack_Pointer* L_S)
{
	struct Link_Node* L_Node = L_S->top;
	while (L_Node->next)
	{
		printf("%d出栈\n", L_Node->element);
		L_Node = L_Node->next;
	}
	printf("%d出栈\n", L_Node->element);
}
void destroy_Stack(struct Link_Stack_Pointer* L_S)
{
	struct Link_Node* L_Node = L_S->top;
	while(L_S->space)
	{
		Pop(L_S);
	}
	L_S->top = NULL;
}
Link_Stack_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Link_Stack_.h"
int main()
{
	int option = 0;
	int element = 0;
	struct Link_Stack_Pointer LS_P;
	Init_Stack(&LS_P);
	Show_Menu();
	while (printf("\n选择为>"), scanf("%d", &option), option)
	{
		switch (option)
		{
		case 1:
			printf("插入值(-1终止)>");
			while (scanf("%d", &element),-1 != element)
			{
				Push(&LS_P, element);
			}
			break;
		case 2:
			Pop(&LS_P);
			break;
		case 3:
			get_length(&LS_P);
			break;
		case 4:
			Show_Stack(&LS_P);
			break;
		case 5:
			Clean_Stack(&LS_P);
			break;
		case 6:
			destroy_Stack(&LS_P);
			break;
		default: printf("超出选择范围\n");
		}
		Show_Menu();
	}
	destroy_Stack(&LS_P);
	printf("已退出\n");
}

# LeetCode 案题

Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in the correct order.
3.Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
// 链栈解法 (3ms)
struct Stack_Node
{
    char data;
    struct StacK_Node* Next;
};
void Stack_Insert(struct Stack_Node** ST,const char data)
{
    struct Stack_Node* P_SN = (struct Stack_Node*)malloc(sizeof(struct Stack_Node));
    assert(NULL != P_SN);
    
    P_SN->data = data;
    P_SN->Next = NULL;
    
    if(NULL == *ST)
        *ST = P_SN;
    else
    {
        P_SN->Next = *ST;   
        *ST = P_SN;
    }
         
}
void Stack_Pop(struct Stack_Node** ST)
{
    struct Stack_Node* P_ST = *ST;
    
    *ST = P_ST->Next;
    free(P_ST);
    P_ST = NULL;
}
bool isValid(char * s){
    struct Stack_Node* ST = NULL;
    
    while('\0' != *s)
    {
        switch(*s)
        {
            case ')':
                if(NULL != ST && '(' == ST->data)
                    Stack_Pop(&ST);
                else
                    return false;
                break;
            case '}':
                if(NULL != ST && '{' == ST->data)
                    Stack_Pop(&ST);
                else
                    return false;
                break;
            case ']':
                if(NULL != ST && '[' == ST->data)
                    Stack_Pop(&ST);
                else
                    return false;
                break;
            default:
                Stack_Insert(&ST,*s);
        }
        ++s;
    }
    if(NULL == ST)
        return true;
    
    return false;
}