STL学习(5)：stack

STL学习网址：

C语言中文网：http://c.biancheng.net/stl/

在数据结构中，栈是一种先入后出的容器，增加元素叫压栈或者入栈。移除元素通常叫做出栈。

STL提供的stack容器，也是这种基本类型。这里我们演示一下基本元素类型和复杂元素类型。

stack<int> s;s.push(x)      无返回值，将元素x压栈s.pop();       退栈，无返回值s.top();        取栈顶元素，返回栈顶元素s.empty();     判断栈是否为空，如果是空，返回1，否则返回0s.size();      返回栈中元素的个数 std::vector<int> data(100, 99);// Contains 100 elements initialized to 99 data.clear(); // Remove all elements

第一条语句创建了一个有 100 个 int 型元素的 vector 对象，它的大小和容量都是 100；所有元素的初始值都是 99。第二条语句移除了所有的元素，因此大小变为 0，因为这个操作并没有改变容器的容量，所以容量还是 100。

 

简单实例代码：

查找一维有序数组

#include <stdio.h> #include <iostream> #include <string.h> #include <stdlib.h> #include <ctype.h> #include <vector> #include <stack> #include <list> #include <algorithm> #include <time.h> using namespace std; int main(int argc, const char * argv[]) { vector<int> my_list1(10); srand((unsigned int) time(NULL)); for(int i = 0; i < my_list1.size(); i++) { my_list1[i] = rand() % 100; } cout<<"aaaaa"<<endl; sort(my_list1.begin(), my_list1.end()); stack<int> my_stack; int low; int hight; int mid; int test; my_stack.push(0); my_stack.push(my_list1.size() - 1); for(int i = 0; i < my_list1.size(); i++) { cout<<i<<":"<< my_list1[i] <<endl; } cout<<"input"<<endl; cin>>test; while (!my_stack.empty()) { hight = my_stack.top();//取数 my_stack.pop(); //出来 low = my_stack.top(); my_stack.pop(); mid = (hight + low) / 2; cout<<low<<" "<<hight<<endl; if (test == my_list1[mid]) { cout<< mid <<endl; break; }else if (test < my_list1[mid]) hight = mid - 1; else low = mid + 1; if (low < hight) { my_stack.push(low); my_stack.push(hight); } } return 0; }

基础数据类型的stack

#include <stdio.h> #include <iostream> #include <vector> #include <stack> using namespace std; int main(void ) { //定义stack对象 stack<int> s1; //入栈 s1.push(1); s1.push(2); s1.push(3); s1.push(4); //打印栈顶元素，并出栈 while (!s1.empty()) { //取出栈顶元素 cout << "top = " << s1.top() << endl; //获取栈的大小 cout << "size = " << s1.size() << endl; //出栈 s1.pop(); } return 0; }

 复杂数据类型的stack

//定义类 class Teacher { public: char name[32]; int age; void printT() { cout << "age = " << age << endl; } }; int main(int argc, const char * argv[]) { Teacher t1, t2, t3; t1.age = 22; t2.age = 33; t3.age = 44; //定义栈容器 stack<Teacher> s1; //入栈 s1.push(t1); s1.push(t2); s1.push(t3); //出栈并打印 while (!s1.empty()) { //打印栈顶元素 Teacher tmp = s1.top(); tmp.printT(); //出栈 s1.pop(); } return 0; }

容器适配器

能成为queue基本容器类Container的条件是它应当支持size，empty，push_back，pop_front，front，back方法，可对数据的两端分别进行插入、删除操作，而deque、list都具有这些函数，所以它们可成为queue的基本容器类Container；

能成为stack基本容器类Container的条件是它应当支持size，empty，push_back, pop_back，back方法，可对数据的一端进行插入、删除操作，而deque、list、vector都具有这些函数，所以它们可成为stack的基本容器类Container。

注意：vector不能作为queue的基本容器类，因为vector没有pop_front方法。

stack基本函数操作示例

#include <iostream> #include <string> #include <vector> #include <list> #include <stack> using namespace std; template <class T, class Container> void PrintStack(stack<T, Container > obj) //堆栈遍历模板函数 { while(!obj.empty()) { cout << obj.top() << "\t"; obj.pop(); } } void main() { stack<int, vector<int> > s; //整形堆栈 for(int i=0; i<4; i++) { s.push(i+1); } PrintStack(s); //4 3 2 1 cout << endl; string str = "a"; //字符串堆栈 stack<string, list<string> > t; for(i=0; i<4; i++) { t.push(str); str += "a"; } PrintStack(t); //aaaa aaa aa a cout << endl; stack<float, deque<float> > u;//符点堆栈 for(i=0; i<4; i++) { u.push(i+1); } PrintStack(u); //4 3 2 1 }

综合操作示例

编一个固定大小的堆栈类。

分析：标准模板库中stack中元素个数没有限制，与题意不符，那么如何既能用上stack固有功能，又能加上特有的限制呢，其实在这句话中已经体现出了具体思路：

（1）从stack派生出自己定义的堆栈类mystack。 这样，mystack类就继承了stack的固有特性；

（2）在mystack类中加入特有的功能，题意中要求限制大小，那么一方面要定义一个成员变量m_nMaxSize, 通过构造函数传入堆栈大小，并赋给m_nMaxSize;另一方面要重载push函数，如果当前堆栈元素个数小于m_nMaxSize，则把新元素压入堆栈。

#include <iostream> #include <deque> #include <stack> using namespace std; template<class T, class Container=deque<T> > class mystack : public stack<T, Container> { private: int m_nMaxSize; //堆栈大小 public: mystack(int maxsize) { m_nMaxSize = maxsize; } void push(const T &t)//重载push函数 { if(size()<m_nMaxSize) //如果堆栈元素个数小于m_nMaxSize { stack<T, Container>::push(t); //则压入堆栈 } else //否则堆栈已满 { cout << "stack is fill." << "the term " << t << " is not pushed" <<endl; } } }; void main() { mystack<int,deque<int> > obj(2); //设置堆栈大小为2 obj.push(1); //可以入栈 size=1 obj.push(2); //可以入栈 size=2 obj.push(3); //栈已满，不能入栈 }