栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

"栈"的常见接口实现

• InitST:初始化栈

• STPush:入栈

• STPop:出栈

• STEmpty:判空(判断是否为空栈)

• PrintSTTop:打印栈顶元素

• STTop:返回栈顶元素(返回值类型:stacktype)

一、顺序栈

"顺序栈"的类型定义

如果友友们学过顺序表,这种类型可以随便拿捏.

代码:

typedef struct stack {  stacktype* data;//一个指向连续内存空间的指针  int top;//记录栈顶元素的下标  int capacaity; }ST;

1.1 初始化栈

top指针:

由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.

capacaity :

同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.

void InitST(ST* ps) {  assert(ps);  ps->top = -1;//此时栈中无数据  ps->capacaity = 4;//设置初始最大容量  ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));  }

此处初始化后:

1.2 入栈(压栈,向"栈"中插入数据)

学到这里(顺序表和链表),对于"栈"的压栈操作很简单.

1. 由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.

1. top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.

1. 将新元素插入.此时刚好top为新的栈顶的下标.

图解:

代码:

void STPush(ST* ps, stacktype x)//压栈 {  assert(ps);  if (ps->top+1 == ps->capacaity)//检查"栈"满  {  ps->capacaity *= 2;//扩容  stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));  if(tmp == NULL)  {  printf("增容失败\n");  }  ps->data = tmp;  }  //将"栈顶指针"指向待插入位置  ps->top++;  //将元素压栈  ps->data[ps->top] = x;  }

1.3 “出栈”,删除"栈"中的数据

步骤:

1. 删除数据时,需要判断"栈"是否为空.

1. 将top向前(下)移动一位,即表示有效数据位减1.

代码:

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

1.4 判空(判断"栈"是否为空)

当栈为空时,top为初始状态-1.

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真 {  assert(ps);  if (ps->top == -1)  {  return true;  }  return false; }

1.5 打印"栈顶"元素

void PrintSTTop(ST* ps) {  assert(ps);  printf("%d", ps->data[ps->top]); }

1.6 返回"栈顶"元素

stacktype STTop(ST* ps)//返回栈顶元素 {  assert(ps);  return ps->data[ps->top]; }

1.7 "栈"的销毁

栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.

void STDestory(ST* ps) {  assert(ps);  free(ps->data);  ps->data = NULL;  ps->top = -1;  ps->capacaity = 0; }

二、链栈

"链栈"的类型定义

typedef int stacktype; // 链栈的类型 typedef struct SLStackNode {  stacktype data;  struct SLStackNode* next; }SLStackNode;

其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.

同时为了提高效率:

综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.

2.1 初始化"链栈"

对于链表实现的栈,如果不带头结点:

我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)

//创建一个栈顶指针,并完成初始化 SLStackNode* SLStack = NULL;

如果是带头结点的单链表:

我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.

//stack.c SLStackNode* InitStack() {  SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));  if (newnode == NULL)  {  perror("newnode malloc fail");  }  return newnode; }  //test.c SLStackNode* SLStack = InitStack();

2.2 入栈(压栈,向"栈"中插入数据)

步骤:(与单链表的头插类似)

1. 创建一个新节点.

1. 将新节点的next指针指向原"栈"的顶点

1. 更新栈顶指针(将栈顶指针指向新节点)

图解:

代码:

//入栈 void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插 {  assert(pps);  //获取新的结点  SLStackNode* newnode = BuyNode(x);  newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点  *pps = newnode;//更新栈顶 }

2.3 “出栈”,删除"栈"中的数据

步骤:(与链表的头删操作类似)

1. 判空,防止空链栈的删除操作

1. 记录原栈顶元素的地址.

1. 更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).

1. 释放原栈顶空间

图解:

void STPop(SLStackNode** pps)//出栈 {  assert(pps);//二级指针不可能为空,如果为空就一定是传错了  assert(*pps);//防止空链栈的删除操作  SLStackNode* head = *pps;//记录栈顶元素的地址  *pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点  free(head);//释放原栈顶空间 }