stack栈

头文件

```
#include <stack>
```

初始化

```
//stack <类型> 名字;
stack<int> a;
```

方法函数
知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。

## 相关方法函数如下：

| 代码   | 含义                          |
| -------- | ------------------------------- |
| push() | 压栈，增加元素 O(1)           |
| pop()  | 移除栈顶元素 O(1)             |
| top()  | 取得栈顶元素（但不删除）O(1)  |
| empty  | 检测栈内是否为空，空为真 O(1) |
| size() | 返回stack内元素的个数 O(1)    |

## 遍历

栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中

## 模拟栈

```
//顺序表实现
#define DataType int
#define bool int
#define maxn 100010

struct Stack {
    DataType data[maxn];
    int top;
};

void StackClear(struct Stack* stk) {
    stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
    stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
    --stk->top;
}
DataType StackGetTop(struct Stack* stk) {
    return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
    return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}
```

```
//链表实现
typedef int DataType;

struct StackNode;
 
struct StackNode {
    DataType data;
    struct StackNode *next;
};

struct Stack {
    struct StackNode *top;
    int size;
};

void StackPushStack(struct Stack *stk, DataType dt) {
    struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
    insertNode->next = stk->top;
    insertNode->data = dt;
    stk->top = insertNode;
    ++ stk->size;
}
void StackPopStack(struct Stack* stk) {
    struct StackNode *temp = stk->top;
    stk->top = temp->next;
    --stk->size; 
    free(temp);
}

DataType StackGetTop(struct Stack* stk) {
    return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
    return stk->size;
}

int StackIsEmpty(struct Stack* stk) {
    return !StackGetSize(stk);
}

void StackClear(struct Stack* stk) {
    while(!StackIsEmpty(stk)) {
        StackPopStack(stk);
    }
    stk->top = NULL; 
    stk->size = 0;
}
```

原文章：https://blog.csdn.net/qq_50285142/article/details/122303786