数据结构与算法：08 |栈

文章目录

如何理解栈如何实现一个“栈”？支持动态扩容的顺序栈栈在表达式求值中的应用

如何理解栈

先进后出 后进先出

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。

如何实现一个“栈”？

栈可以用数组或链表来实现：

用数组实现的栈，叫顺序栈，用链表实现的栈，叫链式栈。

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

顺序栈简单实现

#include <iostream> using namespace std; // 基于数组实现的栈（顺序栈） template <class T> class ArrayStack{ public: ArrayStack(); ArrayStack(int num); ~ArrayStack(); void push(const T &data); //入栈 T pop(); //出栈 T top(); // 单纯获取栈顶元素（不删除） int stackSize(); int stackMaxSize(); private: int flag; //栈顶flag（下标） int count; //容量 T *array; }; template <class T> ArrayStack<T>::ArrayStack(){ // 默认大小随便设个10 flag = 0; count = 10; array = new T[count]; if (!array) cout << "malloc error!" << endl; } template <class T> ArrayStack<T>::ArrayStack(int num){ // count指定大小 flag = 0; count = num; array = new T[count]; if (!array) cout << malloc error!<< endl; } template <class T> ArrayStack<T>::~ArrayStack(){ count = 0; flag = 0; if (array){ delete[] array; array = NULL; } } template <class T> void ArrayStack<T>::push(const T &data){ // 先检查是否栈已满 if(flag == count){ cout << "栈已满，需要扩容!!" << endl; count += count / 2; T *p = new T[count]; for (int i = 0; i < flag; ++i){ p[i] = array[i]; } delete[] array; p[flag] = data; ++flag; array = p; } else{ array[flag] = data; ++flag; } } template <class T> T ArrayStack<T>::pop(){ if (flag){ flag--; T data = array[flag]; return data; } else{ cerr << "栈为空，无法pop()！" << endl; } } template <class T> T ArrayStack<T>::top(){ if (flag){ T data = array[flag-1]; return data; } else{ cerr << "栈为空,不存在顶元素!" << endl; } } template <class T> int ArrayStack<T>::stackSize(){ return flag; } template <class T> int ArrayStack<T>::stackMaxSize(){ return count; }

链式栈简单实现：

#include <iostream> using namespace std; template<class T> class ListStack{ public: ListStack(); ~ListStack(); void push(const T &data); T pop(); T top(); int stackSize(); private: int count; //栈的大小 struct LinkedNode{ T data; LinkedNode *next; }; LinkedNode *head; }; template<class T> ListStack<T>::ListStack(){ count = 0; head = new LinkedNode; head->next = NULL; } template<class T> ListStack<T>::~ListStack(){ LinkedNode *p, *tmp; p = head; while (p->next != NULL){ tmp = p->next; p->next = tmp->next; delete tmp; } delete head; head = NULL; count = 0; } template<class T> void ListStack<T>::push(const T &data){ auto *newNode = new LinkedNode; newNode->data = data; newNode->next = head->next; head->next = newNode; ++count; } template<class T> T ListStack<T>::pop(){ if (count == 0 || head->next == NULL){ cerr << "栈为空！" << endl; return NULL; } else{ auto * tmp = head->next; head->next = tmp->next; T data = tmp->data; delete tmp; count--; return data; } } template<class T> T ListStack<T>::top(){ if (count == 0 || head->next == NULL){ cerr << "栈为空！" << endl; return NULL; } else{ return head->next->data; } } template<class T> int ListStack<T>::stackSize(){ return count; }

支持动态扩容的顺序栈

出栈时间复杂度仍然是 O(1);

对于入栈操作来说:

当栈中有空闲空间时，时间复杂度为 O(1);当空间不够时，需要重新申请内存和数据搬移，时间复杂度就变成了 O(n)。

栈在表达式求值中的应用

表达式求值通过两个栈来实现： 其中一个保存操作数，另一个保存运算符。从左向右遍历表达式，当遇到数字，就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较：

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

可以看224. 基本计算器 - 力扣（LeetCode）