数据结构栈（C语言）

痛定思痛。 2023-07-10 12:59 34阅读 0赞

栈是一种十分常见的数据结构，其特点是**每次只对栈顶的元素进行出栈（减少）或入栈（增加）**。这样做可以确保栈中除栈顶的数据不会被改动，并且在一些场合中十分适用，例如括号匹配问题。

## 顺序栈 ##

栈通常分为两种，第一种是顺序栈。顾名思义它是一整块连续的空间组成，类似于数组。其实可以把它理解为只能在头部进行增删操作的数组。  
在创建顺序站之前我们先来思考顺序栈由什么组成，首先我们需要一个数组，一个指向栈顶部的指针，一个记录数组长度的变量stacksize。  
于是：

typedef struct Stack{
        
    	int *StackArray;
    	int top;
    	int stacksize;
    }SeqStack;

StackArray代表了顺序栈中的数组。  
top代表栈顶。  
stacksize代表栈此时的长度。

**tip：**  
最好在前面加上`#define ElemType int`之后用ElemType替换int，这样如果需要将int转换为其他数据类型的时候只需修改\#define即可。

**之后是初始化栈的过程：**

bool Init_Stack(SeqStack &S)
    {
        
    	S.StackArray = (int*)malloc(STACKSIZE * sizeof(int));
    	if(!S.StackArray)
    		return false;
    	S.top = 0;
    	S.stacksize = 0;
    	return true;
    }

这里的STACKSIZE需要读者自行在开头\#define。

**判断栈是否为空：**

bool Is_Empty(SeqStack &S)
    {
        
    	return (S.stacksize == 0);
    }

**接下来是入栈操作：**

bool Push(SeqStack &S,int InsertNUM)
    {
        
    	if(S.stacksize >= STACKSIZE)
    		return false;
    	S.StackArray[S.top] = InsertNUM;
    	S.top++;
    	S.stacksize++;
    	return true;
    }

InsertNUM是想要插入的数。插入之后top要++，因为在此程序中，top指向栈顶的后一个（读者可以自己规定）。

**出栈：**

int Pop(SeqStack &S)
    {
        
    	if(S.stacksize <= 0)
    		return false;
    	S.top--;
    	S.stacksize--;
    	return S.StackArray[S.top];
    }

与入栈操作类似。

以上是顺序栈的基本操作。接下来我们来看一下链式栈。

## 链式栈 ##

与顺序栈不同，链式栈是由在链表中加入栈的思想。相较于顺序栈，链式栈的大小不固定，较为灵活。  
其基本函数与链表类似，再次就不再赘述，值得注意的是出栈时只允许栈顶出栈，也就是头结点