栈是一种“先进后出”的数据结构,最先进入栈的元素位于栈的底端,最后进入的位于顶端。
其主要的接口函数为:
pop()
: 弹出顶端元素size()
: 返回栈容量empty()
: 判断栈是否为空push(T data)
: 添加元素到栈顶top()
: 返回顶端元素
注意事项
对于栈的
top()
和pop()
方法,使用前应该通过empty()
手动判断栈是否为空,确认栈中有元素再进行操作。同样,对于有容量限制的栈来说,压栈时应该也先判断栈的容量是否已满,避免占空间溢出。
当数据类型
T
是指针时,栈对象析构时不会制动释放所有的数组对象,需要自己对元素的生存周期负责。
一、使用数组实现栈
类模板声明为:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#pragma once #define uint unsigned int template <typename T, uint N> class CArrStack { public: CArrStack(); ~CArrStack(); void push(T t); T pop(); T& top() const; uint size() const; bool empty() const; private: T data[N]; uint cur; }; |
使用时需要指定类型名和栈空间大小:
1 2 |
// 声明一个容量为100的元素类型为int的栈 CArrStack<int, 100> s; |
1.1 构造和析构函数
1 2 3 4 5 6 7 8 9 10 11 12 13 |
template<typename T, uint N> inline CArrStack<T, N>::CArrStack() { memset(data, 0, N * sizeof(T)); cur = 0; } template<typename T, uint N> inline CArrStack<T, N>::~CArrStack() { memset(data, 0, N * sizeof(T)); cur = 0; } |
1.2 压栈操作push()
压栈时注意不要数组越界:
1 2 3 4 5 6 |
template<typename T, uint N> inline void CArrStack<T, N>::push(T t) { if (cur == N) return; data[cur++] = t; } |
1.3 出栈操作pop()
有些时候pop
只用于出栈,并不用返回被出栈的元素,使用前应当先判断栈是否为空。
1 2 3 4 5 |
template<typename T, uint N> inline T CArrStack<T, N>::pop() { return data[--cur]; } |
1.4 返回栈顶元素top
1 2 3 4 5 |
template<typename T, uint N> inline T& CArrStack<T, N>::top() const { return data[cur - 1]; } |
1.5 返回栈长度size(),判断栈是否为空empty()
1 2 3 4 5 6 7 8 9 10 11 |
template<typename T, uint N> inline uint CArrStack<T, N>::size() const { return cur; } template<typename T, uint N> inline bool CArrStack<T, N>::empty() const { return cur == 0; } |
二、使用vector实现栈
使用动态数组vector
创建栈的好处在于能栈自动扩容和缩小,无需手动指定大小,插入元素时会自动扩容。
2.1 stack.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <vector> #include <assert.h> using namespace std; typedef unsigned int uint; template <typename T> class CStack { public: CStack(); ~CStack(); uint size() const; bool empty() const; void push(const T t); T pop(); T top() const; private: vector<T> data; }; |
2.2 stack.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
template <typename T> CStack<T>::CStack() { } template <typename T> CStack<T>::~CStack() { } template<typename T> inline uint CStack<T>::size() const { return data.size(); } template<typename T> inline bool CStack<T>::empty() const { return data.size() == 0; } template<typename T> inline void CStack<T>::push(const T t) { data.push_back(t); } template<typename T> inline T CStack<T>::pop() { typename vector<T>::iterator it = data.end() - 1; T tmp = *it; data.pop_back(); return tmp; } template<typename T> inline T CStack<T>::top()const { return data[data.size() - 1]; } |
评论