栈

栈也是线性表的一种，栈具有“先进后出”的特性，数据只能从栈顶进入从栈顶弹出，栈主要用在树的遍历、函数调用保存原函数地址等。

顺序栈

顺序栈是指栈元素在内存中顺序存储，即使用数组进行存储，确定是不够灵活，可能会浪费内存空间。

 //线性表中的线顺序栈，使用静态数组
 #include <iostream>
 using namespace std;
 ​
 #define MaxSize 50 //最大容量50
 ​
 template <class T>
 class SqStack
 {
 public:
     T data[MaxSize]; //数据
     int top;         //栈顶指针
 };
 ​
 template <class T>
 void InitStack(SqStack<T> &S) //初始化空栈
 {
     S.top = -1; //栈顶指针为-1
 }
 ​
 template <class T>
 bool StackEmpty(SqStack<T> &S) //判断栈是否为空
 {
     if (S.top == -1)
         return true;
     else
         return false;
 }
 ​
 template <class T>
 bool Push(SqStack<T> &S, T x) //进栈
 {
     if (S.top == MaxSize - 1) //判断栈满
         return false;
     S.data[++S.top] = x; //数据入栈
     return true;
 }
 ​
 template <class T>
 bool Pop(SqStack<T> &S, T &x) //出栈
 {
     if (StackEmpty(S)) //栈空
         return false;
     x = S.data[S.top--]; //数据出栈
     return true;
 }
 ​
 template <class T>
 bool GetTop(SqStack<T> S, T &x) //读栈顶元素
 {
     if (StackEmpty(S)) //栈空
         return false;
     x = S.data[S.top]; //读取数据
     return true;
 }
 ​
 template <class T>
 bool DestroyStack(SqStack<T> &S) //销毁栈
 {
     S.top = -1;
     return true;
 }
 ​
 int main()
 {
     SqStack<int> S; //定义整型栈
     InitStack(S);   //初始化
     for (int i = 0; i < 5; i++)
         Push(S, i); // 0-4顺序进栈
     int x;
     GetTop(S, x); //读取栈顶
     cout << "当前栈顶元素：" << x << endl;
     for (int i = 0; i < 2; i++)
     {
         Pop(S, x); //出栈
         cout << "出栈的元素：" << x << endl;
     }
     DestroyStack(S); //销毁栈
     cout << "销毁后的栈顶指针：" << S.top << endl;
     system("pause");
     return 0;
 }

链栈

链栈的的结构为没有头节点的单链表，栈顶指针指向表头，链表的大小动态增加，可以更好的利用内存空间。

 //线性表中的链栈,无头结点
 #include <iostream>
 using namespace std;
 ​
 template <class T>
 class LNode //单链表节点
 {
 public:
     T data;                                   //数据域
     struct LNode *next;                       //指针域
     LNode(T data) : data(data), next(NULL) {} //有参构造
     LNode() : next(NULL) {}                   //无参构造
 };
 ​
 template <class T>
 using LNode = LNode<T>; //起别名
 template <class T>
 using Stack = LNode<T> *; //起别名
 ​
 template <class T>
 void InitStack(Stack<T> &head) //初始化
 {
     head = NULL;
 }
 ​
 template <class T>
 bool StackEmpty(Stack<T> &head) //判断栈空
 {
     if (head == NULL)
         return true;
     return false;
 }
 ​
 template <class T>
 bool Push(Stack<T> &head, T data) //进栈
 {
     LNode<T> *newNode = new LNode<T>(data); //新节点
     newNode->next = head;
     head = newNode;
     return true;
 }
 ​
 template <class T>
 bool Pop(Stack<T> &head, T &data) //出栈
 {
     if (StackEmpty(head)) //栈空
         return false;
     LNode<T> *node = head;
     data = node->data;
     head = node->next;
     delete node; //删除头节点
     return true;
 }
 ​
 template <class T>
 bool GetTop(Stack<T> &head, T &data) //读取栈顶元素
 {
     if (StackEmpty(head)) //栈空
         return false;
     data = head->data;
     return true;
 }
 ​
 template <class T>
 bool DestroyStack(Stack<T> &head) //销毁
 {
     while (!StackEmpty(head)) //栈不为空
     {
         LNode<T> *node = head;
         head = head->next;
         delete node;
     }
     return true;
 }
 ​
 int main()
 {
     Stack<int> s; //整型栈
     InitStack(s); //初始化栈
     for (int i = 0; i < 5; i++)
         Push(s, i); // 0-4入栈
     int data;
     GetTop(s, data); //读取栈顶
     cout << "当前栈顶元素：" << data << endl;
     for (int i = 0; i < 2; i++)
     {
         Pop(s, data); //出栈
         cout << "出栈的元素：" << data << endl;
     }
     if (DestroyStack(s)) //销毁栈
         cout << "成功销毁栈。" << endl;
     system("pause");
     return 0;
 }

项目地址

https://gitee.com/incoparab/data-structure

标签：学习笔记, c/c++