# 顺序栈的基本原理

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

# 顺序栈的基本创建

SeqStack_.h(头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define INIT_STACK_SPACE 8
#define STACK_ADD_SPACE 3
typedef int Element;
struct SeqList_Pointer
{
	Element* memeber;
	int space;
	int top;
};
void Init_Seq(struct SeqList_Pointer* S_Pointer);
void Show_Menu();
void Push(struct SeqList_Pointer* S_Pointer,Element element);
void Pop(struct SeqList_Pointer* S_Pointer);
int get_length(struct SeqList_Pointer* S_Pointer);
void Show_Stack(struct SeqList_Pointer* S_Pointer);
void Clean_Stack(struct SeqList_Pointer* S_Pointer);
void destroy_Stack(struct SeqList_Pointer* S_Pointer);
SeqStack_functions.c
#include"SeqStack_.h"
static int Check_Full(struct SeqList_Pointer* S_Pointer)
{
	if (S_Pointer->top >= INIT_STACK_SPACE)
		return 1;
	else
		return 0;
}
void Init_Seq(struct SeqList_Pointer* S_Pointer)
{
	S_Pointer->top = 0;
	S_Pointer->space = INIT_STACK_SPACE;
	S_Pointer->memeber = (Element*)malloc(sizeof(Element) * S_Pointer->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 Push(struct SeqList_Pointer* S_Pointer,Element element)
{
	assert(NULL != S_Pointer->memeber);
	if (Check_Full)
	{
		S_Pointer->space += STACK_ADD_SPACE;
		S_Pointer->memeber = (Element*)realloc(S_Pointer->memeber, sizeof(Element) * S_Pointer->space);
	}
	S_Pointer->memeber[S_Pointer->top++] = element;
	printf("%d入栈\n", S_Pointer->memeber[S_Pointer->top - 1]);
}
void Pop(struct SeqList_Pointer* S_Pointer)
{
	assert(NULL != S_Pointer->memeber);
	if (-1 == S_Pointer->top - 1)
		return;
	printf("%d 出栈\n", S_Pointer->top);
	S_Pointer->top--;
}
int get_length(struct SeqList_Pointer* S_Pointer)
{
	printf("栈内空间长度为%d\n", S_Pointer->top);
	return S_Pointer->top;
}
void Show_Stack(struct SeqList_Pointer* S_Pointer)
{
	int i = 0;
	for (i = S_Pointer->top - 1; i > -1; i--)
	{
		printf("%d\n", S_Pointer->memeber[i]);
	}
}
void Clean_Stack(struct SeqList_Pointer* S_Pointer)
{
	assert(NULL != S_Pointer->memeber);
	while (S_Pointer->top)
	{
		Pop(S_Pointer);
	}
	printf("已清空\n");
}
void destroy_Stack(struct SeqList_Pointer* S_Pointer)
{
	assert(NULL != S_Pointer->memeber);
	free(S_Pointer->memeber);
	S_Pointer->memeber = NULL;
	printf("已摧毁\n");
}
SeqStack_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqStack_.h"
int main()
{
	int option = 0;
	int element = 0;
	struct SeqList_Pointer SP;
	Init_Seq(&SP);
	Show_Menu();
	while (printf("\n选择为>"),scanf("%d", &option),option)
	{
		switch (option)
		{
		case 1:
			printf("插入的值(-1终止)>");
			while(scanf("%d", &element),-1 != element)
				Push(&SP, element);
			break;
		case 2:
			Pop(&SP);
			break;
		case 3:
			get_length(&SP);
			break;
		case 4:
			Show_Stack(&SP);
			break;
		case 5:
			Clean_Stack(&SP);
			break;
		case 6:
			destroy_Stack(&SP);
			break;
		default: printf("超出选择范围\n");
		}
		Show_Menu();
	}
	printf("已退出\n");
	return 0;
}

# LeetCode 案题

Valid Parentheses(有效括号判断)
  • →Valid Parentheses
/*
顺序栈解法 (0ms)
*/
#include<stdio.h>
#include<stdbool.h>
bool isValid(char * s){
    char Stack[10000] = {0};
    int i = 0;
    int index = 0;
    
    for(i = 0;'\0' != s[i];++i)
    {
        switch(s[i])
        {
            case ')':
                if('(' == Stack[index])
                    --index;
                else
                    return false;
                break;
            case '}':
                if('{' == Stack[index])
                    --index;
                else
                    return false;
                break;
            case ']':
                if('[' == Stack[index])
                    --index;
                else
                    return false;
                break;
            default:
                Stack[++index] = s[i];
        }
    }
    if(0 == index)
        return true;
    else
        return false;
}
Remove Duplicates from Sorted Array(有序数组排除重复项)
  • →Remove Duplicates from Sorted Array
/*
运用顺序栈理论解法 (12ms)
*/
#include<stdio.h>
int removeDuplicates(int* nums, int numsSize){
    int i = 0;
    int index = 0;
    
    for(i = 1;i < numsSize;)
    {
        nums[i] != nums[index] ? nums[++index] = nums[i] : ++i;
    }
    return index + 1;
}
Remove Element(移除数组指定值)
  • →Remove Element
/*
运用顺序栈理论解法 (0ms)
*/
#include<stdio.h>
int removeElement(int* nums, int numsSize, int val){
    int i = 0;
    int index = 0;
    
    for(i = 0;i < numsSize;++i)
    {
        val != nums[i] ? nums[index++] = nums[i] : 1;
    }
    
    return index;
}