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 <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef 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 <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> 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; }
