顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设有指针top指示栈顶元素在顺序栈中的位置;另设指针base指示栈底元素在顺序栈中的位置。当top和base的值相等时,表示空栈。
#include链栈#include #include #define MAXSIZE 20 typedef struct { int nData[MAXSIZE]; int nTop; }RkStack; //初始化栈 bool InitStack(RkStack * Stack) { Stack->nTop = -1; return true; } //清理栈 bool ClearStack(RkStack * Stack) { Stack->nTop = -1; return true; } // 判断栈是否为空 bool StackEmpty(RkStack Stack) { if (Stack.nTop == -1) { return true; } else { return false; } } //或取栈的长度 int StackLength(RkStack Stack) { return Stack.nTop + 1; } //栈顶 int GetTop(RkStack Stack, int * nData) { if (Stack.nTop == -1) { return false; } else { *nData = Stack.nData[Stack.nTop]; } } //push bool push(RkStack * Stack, int nData) { if (Stack->nTop == MAXSIZE - 1) { return false; } else { Stack->nTop++; Stack->nData[Stack->nTop] = nData; return true; } } //pop bool pop(RkStack * Stack, int *nData) { if (Stack->nTop == -1) { return false; } else { *nData = Stack->nData[Stack->nTop]; Stack->nTop--; return true; } } //打印数据 bool ShowStack(RkStack Stack) { if (Stack.nTop == -1) { return false; } for (size_t i = 0; i < Stack.nTop; i++) { printf("Stack value = %dn", Stack.nData[i]); } return true; } int main() { RkStack rkStack; InitStack(&rkStack); for (size_t i = 0; i < 10; i++) { push(&rkStack, i); } ShowStack(rkStack); int nData = 0; pop(&rkStack, &nData); printf("pop value = %dn", nData); //ShowStack(rkStack); GetTop(rkStack, &nData); printf("GetTop = %dn", nData); int Size = StackLength(rkStack); printf("StackLength = %dn", Size); ClearStack(&rkStack); bool nFlag = StackEmpty(rkStack); if (nFlag) { printf("Emptyn"); } system("pause"); return 0; }
链栈是指采用链式存储结构实现的栈,通常链栈用单链表表示。
没有特殊要求,顺序栈比链栈更实用。
#include区别#include #include typedef struct _StackNode { int nData; struct _StackNode *next; }StackNode,*PStackNdoe; typedef struct RkStack { PStackNdoe top; int count; }; //初始化栈 bool InitStack(struct RkStack * Stack) { Stack->top = (PStackNdoe)malloc(sizeof(StackNode)); if (!Stack->top) { return false; } Stack->top = NULL; Stack->count = 0; return true; } //清理栈 bool ClearStack(struct RkStack * Stack) { PStackNdoe TempNode1; PStackNdoe TempNode2; TempNode1 = Stack->top; while (TempNode1) { TempNode2 = TempNode1; TempNode1 = TempNode1->next; free(TempNode2); } Stack->count = 0; } // 判断栈是否为空 bool StackEmpty(struct RkStack Stack) { if (Stack.count == 0) { return true; } else { return false; } } //或取栈的长度 int StackLength(struct RkStack Stack) { return Stack.count; } //栈顶 int GetTop(struct RkStack Stack, int * nData) { if (Stack.top == NULL) { return false; } else { *nData = Stack.top->nData; return true; } } //push bool push(struct RkStack * Stack, int nData) { PStackNdoe mStackNode = (PStackNdoe)malloc(sizeof(StackNode)); mStackNode->nData = nData; mStackNode->next = Stack->top; Stack->top = mStackNode; Stack->count++; return true; } //pop bool pop(struct RkStack * Stack, int *nData) { PStackNdoe mStackNode; if (StackEmpty(*Stack)) { return false; } else { *nData = Stack->top->nData; mStackNode = Stack->top; Stack->top = Stack->top->next; free(mStackNode); Stack->count--; return true; } } //打印数据 bool ShowStack(struct RkStack Stack) { PStackNdoe mStackNode; mStackNode = Stack.top; while (mStackNode) { printf("value = %dn", mStackNode->nData); mStackNode = mStackNode->next; } return true; } int main() { struct RkStack rkStack; int nData; InitStack(&rkStack); for (size_t i = 0; i < 10; i++) { push(&rkStack, i); } ShowStack(rkStack); pop(&rkStack, &nData); printf("pop value = %dn", nData); ShowStack(rkStack); GetTop(rkStack, &nData); printf("Get top value = %dn", nData); ClearStack(&rkStack); if (StackEmpty(rkStack)) { printf("Empty!n"); } system("pause"); return 0; }
顺序栈和链栈区别如下:
- 存储结构不同,顺序栈是静态分配的,而链栈则是动态分配的,链栈可以将很多零碎的空间利用起来,容量可变,节省空间,顺序栈则固定内存空间,容量不变。
- 使用方面,顺序栈查询速度快,链栈添加删除数据更快。



