[数据结构]5. 栈-Stack

1. 介绍

栈（stack） 是一种遵循先入后出逻辑的线性数据结构。顶部称为“栈顶”，底部称为“栈底”。把元素添加到栈顶的操作叫作“入栈”，删除栈顶元素的操作叫作“出栈”。

2. 栈的实现

2.1 基于链表的实现

2.2 基于数组的实现

3. 栈操作

Create

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

Initilizate

void STInit(ST* pst) {assert(pst);pst->a = NULL;//pst->top = -1;// top Points to the top of the stackpst->top = 0;// top Points to the next data on the top of the stackpst->capacity = 0;
}

Destory

void STDestory(ST* pst) {assert(pst);free(pst->a);pst->top = pst->capacity = 0;
}

Push

void STPush(ST* pst, STDataType x) {// Enpend capacityif (pst->top == pst->capacity) {int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;// If memblock is NULL, realloc behaves the same way as malloc and allocates a new block of size bytes. STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("relloc fail");return;}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}

Pop

void STPop(ST* pst) {assert(pst);assert(!STEmpty(pst));pst->top--;
}

Top

STDataType STTop(ST* pst) {assert(pst);assert(!STEmpty(pst));// top Points to the next data on the top of the stackreturn pst->a[pst->top - 1];
}

Empty

bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;
}

Size

int STSize(ST* pst) {assert(pst);return pst->top;
}