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

链栈(不带头版本的)的初始状态是栈顶指针指向NULL.

bool STEmpty(SLStackNode* ps)//判断是否为空栈 {  if (ps == NULL)  {  return true;  }  else  return false; }

2.5 打印"栈顶"元素

栈顶元素即,栈顶指针指向的结点的数据域.

void PrintSTTop(SLStackNode* ps)//打印栈顶元素 {  assert(ps);  printf("%d ", ps->data); }

2.6 返回"栈顶"元素

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

2.7 返回"链栈"的长度(有效数据的个数)

遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).

代码:

int LengthStack(SLStackNode* ps) {  int count = 0;  if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素  {  return 0;  }  SLStackNode* tail = ps;//代替头指针遍历  while (ps)  {  count++;//如果该结点不为空,则有效数据个数+1  ps = ps->next;  }  return count;//返回有效数据的个数 }

2.8 "链栈"的销毁

与"链表"销毁类似.

void STDestory(SLStackNode* ps)//栈的销毁 {  SLStackNode* del = ps;  SLStackNode* next = ps;//用于记录下一个结点  while (next)  {  next = next->next;  free(del);  del = next;   }  //保持习惯置空  next == NULL;  del = NULL; }

总结:

虽然链表和顺序表可以实现"栈",并且效率上,二者差距不大.

但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.

寄存器:

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).

数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.

栗子:

综上,还是稍微建议使用顺序栈有一点点优势.

总代码

"顺序栈"总代码

声明区(stack.h)

#include#include#include#includetypedef int stacktype; typedef struct stack {  stacktype* data;  int top;  int capacaity; }ST; void InitST(ST* ps); void STPush(ST* ps, stacktype x);//压栈 void STPop(ST* ps);//出栈 void PrintSTTop(ST* ps);//打印栈顶元素  bool STEmpty(ST* ps);//判断是否为空栈 stacktype STTop(ST* ps);//返回栈顶元素 void STDestory(ST* ps);//栈的销毁

接口实现区( stack.c)

#include "stack.h" //初始化栈 void InitST(ST* ps) {  assert(ps);  ps->top = -1;  ps->capacaity = 4;  ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));  }  //压栈 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;  }  //出栈 void STPop(ST* ps) {  assert(ps);  assert(!STEmpty(ps));  ps->top--; }  //打印栈顶元素 void PrintSTTop(ST* ps) {  assert(ps);  printf("%d", ps->data[ps->top]); }  //判断是否为空栈,是空返回真 bool STEmpty(ST* ps) {  assert(ps);  if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;  {  return true;  }  return false; }  //返回栈顶元素 stacktype STTop(ST* ps) {  assert(ps);  return ps->data[ps->top];//反追栈顶元素 }  //栈的销毁 void STDestory(ST* ps) {  assert(ps);  free(ps->data);//释放栈空间  ps->data = NULL;  ps->top = -1;  ps->capacaity = 0; }

测试区(test.c)

#include "stack.h" void test1() {  ST st1;  InitST(&st1);  STPush(&st1, 1);//压栈  STPush(&st1, 2);//压栈  STPush(&st1, 3);//压栈  STPush(&st1, 4);//压栈  int a=STTop(&st1);  printf("栈顶元素为%d\n", a);  while (!STEmpty(&st1))  {  PrintSTTop(&st1);//打印栈顶元素  STPop(&st1);  }   STDestory(&st1);  } int main() {  test1();  return 0; }

"链栈"总代码:

声明区(SLStack.h)

#pragma once  #include#include#include#include typedef int stacktype; // 链栈的类型 typedef struct SLStackNode {  stacktype data;  struct SLStackNode* next; }SLStackNode;   //SLStackNode* InitStack();  void STPush(SLStackNode** pps, stacktype x);//压栈 void STPop(SLStackNode** pps);//出栈 void PrintSTTop(SLStackNode* ps);//打印栈顶元素  bool STEmpty(SLStackNode* ps);//判断是否为空栈 stacktype STTop(SLStackNode* ps);//返回栈顶元素  int LengthStack(SLStackNode* ps);//返回栈的长度  void STDestory(SLStackNode* ps);//栈的销毁

接口实现区(SLStack.c)

#include "SLStack.h"  //SLStackNode* InitStack() //{ // SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode)); // if (newnode == NULL) // { // perror("newnode malloc fail"); // } // return newnode; //}  SLStackNode* BuyNode(stacktype x)//创建新结点 {  SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));  assert(newnode);//防止申请结点失败  newnode->data = x;  newnode->next = NULL;  return newnode; }   //入栈 void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插 {  assert(pps);  //获取新的结点  SLStackNode* newnode = BuyNode(x);  newnode->next = *pps;  *pps = newnode; }  void STPop(SLStackNode** pps)//出栈 {  assert(pps);//二级指针不可能为空,如果为空就一定是传错了  assert(*pps);//防止空链栈的删除操作  SLStackNode* head = *pps;//记录栈顶元素的地址  *pps = (*pps)->next;//将栈顶向下移动一位  free(head);//释放栈顶空间 }  void PrintSTTop(SLStackNode* ps)//打印栈顶元素 {  assert(ps);  printf("%d ", ps->data); }  bool STEmpty(SLStackNode* ps)//判断是否为空栈 {  if (ps == NULL)  {  return true;  }  else  return false; }  stacktype STTop(SLStackNode* ps)//返回栈顶元素 {  assert(ps);  return ps->data; }  int LengthStack(SLStackNode* ps) {  int count = 0;  if (ps == NULL)  {  return 0;  }  SLStackNode* tail = ps;  while (ps)  {  count++;  ps = ps->next;  }  return count; }  void STDestory(SLStackNode* ps)//栈的销毁 {  SLStackNode* del = ps;  SLStackNode* next = ps;//用于记录下一个结点  while (next)  {  next = next->next;  free(del);  del = next;   }  //保持习惯置空  next == NULL;  del = NULL; }

测试区(test.c)

#include "SLStack.h"  void test1() {  SLStackNode* SLStack = NULL;  //SLStackNode* SLStack = InitStack();   STPush(&SLStack, 1);//压栈  STPush(&SLStack, 2);//压栈  STPush(&SLStack, 3);//压栈  STPush(&SLStack, 4);//压栈  STPush(&SLStack, 5);//压栈  STPush(&SLStack, -1);//压栈  STPush(&SLStack, -2);//压栈  int a = STTop(SLStack);  printf("栈顶元素为%d\n", a);   int length = LengthStack(SLStack);  printf("链表的长度为:%d\n", length);   while (!STEmpty(SLStack))  {  PrintSTTop(SLStack);//打印栈顶元素  STPop(&SLStack);  }   STDestory(SLStack);  } int main() {  test1();  return 0; }