当前位置：首页 > news >正文

湖南网站建设公司干净磐石网络/惠州百度seo哪里强

news 2025/8/3 10:13:55

湖南网站建设公司干净磐石网络,惠州百度seo哪里强,达州网络推广,wordpress http2文章目录如何理解栈如何实现一个“栈”？支持动态扩容的顺序栈栈在表达式求值中的应用如何理解栈先进后出后进先出当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。如何实现…

文章目录

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

如何理解栈

先进后出
后进先出

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

如何实现一个“栈”？

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

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

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 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(){// 默认大小随便设个10flag = 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;
}