数据结构--栈代码实现

前言

本文介绍了数据结构中一种特殊的线性存储方式——栈

性质：先进后出（FILO）

例如现实生活中的叠盘子与烤串，只能从顶部存入和取出

代码实现

静态栈

头文件：

SqStack.h #include<iostream> using namespace std; #define MaxSize 10 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; }SqStack; //初始化 void InitStack(SqStack& S); //入栈 bool Push(SqStack& S, ElemType e); //出栈 bool Pop(SqStack& S, ElemType& e); //获取栈顶元素 bool GetTop(SqStack& S, ElemType& e);

函数实现文件：

SqStack.cpp #include"SqStack.h" //初始化 void InitStack(SqStack& S) { S.top = -1; } //入栈 bool Push(SqStack& S, ElemType e) { if (S.top == MaxSize - 1) return false; S.data[++S.top] = e; return true; } //出栈 bool Pop(SqStack& S, ElemType& e) { if (S.top == -1) return false; e = S.data[S.top--]; return true; } //获取栈顶元素 bool GetTop(SqStack& S, ElemType& e) { if (S.top == -1) return false; e = S.data[S.top]; return true; }

测试文件：

test1.cpp #include"SqStack.h" void fun1() { SqStack S; InitStack(S); Push(S, 1); Push(S, 2); Push(S, 3); ElemType e; if (Pop(S, e)) { cout << e << endl; } else cout << "Pop fail" << endl; if (GetTop(S, e)) { cout << e << endl; } else cout << "Get top Fail" << endl; } int main() { fun1(); return 0; }

动态栈（链表）

头文件

LiStack.h #pragma once #include<iostream> using namespace std; typedef int ElemType; typedef struct LinkNode { ElemType data; struct LinkNode* next; }*LiStack; //初始化 void InitLiStack(LiStack& S); //入栈 void Push(LiStack& S, ElemType e); //出栈 bool Pop(LiStack& S, ElemType& e); //获取栈顶元素 bool GetTop(LiStack S, ElemType& e);

实现文件：

LiStack.cpp #include"LiStack.h" //初始化 void InitLiStack(LiStack& S) { S = NULL; } //入栈 void Push(LiStack& S, ElemType e) { LinkNode* s = new LinkNode; s->data = e; s->next = S; S = s; } //出栈 bool Pop(LiStack& S, ElemType& e) { if (!S) return false; e = S->data; LinkNode* p = S; S = S->next; free(p); return true; } //获取栈顶元素 bool GetTop(LiStack S, ElemType& e) { if (!S) return false; e = S->data; return true; }

实现文件

#include"LiStack.h" //void fun1() //{ // SqStack S; // InitStack(S); // Push(S, 1); // Push(S, 2); // Push(S, 3); // // ElemType e; // if (Pop(S, e)) // { // cout << e << endl; // } // else cout << "Pop fail" << endl; // // if (GetTop(S, e)) // { // cout << e << endl; // } // else cout << "Get top Fail" << endl; // //} void fun2() { LiStack S; InitLiStack(S); Push(S, 1); Push(S, 2); Push(S, 3); ElemType e; if (Pop(S, e)) { cout << e << endl; } else cout << "Pop fail" << endl; if (GetTop(S, e)) { cout << e << endl; } else cout << "Get top Fail" << endl; } int main() { fun2(); return 0; }