首页 > 代码库 > 堆栈的公式化描述实现
堆栈的公式化描述实现
堆栈和队列可能是使用频率最高的数据结构，二者都来自于线性表数据结构（经过某种限制以后）。堆栈数据结构是通过对线性表的插入和删除操作进行限制而得到的（插入和删除操作都必须在表的同一端完成），因此，堆栈是一个后进先出（ last-in-first-out, LIFO）的数据结构。
1、定义
定义 [堆栈] 堆栈（ s t a c k）是一个线性表，其插入（也称为添加）和删除操作都在表的同一端进行。其中一端被称为栈顶（ t o p），另一端被称为栈底（ b o t t o m）。
ADT：
2、公式化描述
堆栈是一种特殊的线性表，因此它可以使用数组或链表实现。使用数组实现即使公式化描述实现。
令栈顶元素存储在 e l e m e n t [ l e n g t h - 1 ]中，栈底元素存储在 e l e m e n t [ 0 ]中。堆栈元素存储在数组s t a c k之中， t o p用于指向栈顶元素。堆栈的容量为 M a x To p + 1 。
3、代码实现
模板类：
(exceotionerror.h见队列的实现：公式化描述)
1 #ifndef ARRAYSTACK_H 2 #define ARRAYSTACK_H 3 #include "exceptionerror.h" 4 5 template<class T> 6 class ArrayStack 7 { 8 public: 9 ArrayStack(const int& MaxStackSize = 10); 10 ArrayStack(T* s, const int& n,const int& MaxStackSize=10); 11 ~ArrayStack() 12 { 13 if (stack!=NULL) 14 { 15 delete[] stack; 16 } 17 } 18 friend std::ostream& operator<<(std::ostream& output,const ArrayStack<T>& s) 19 { 20 if (s.IsEmpty()) 21 { 22 output << "Stack is empty" << std::endl; 23 } 24 else 25 { 26 for (int i = 0; i <= s.top;++i) 27 { 28 output << s.stack[i] << " "; 29 } 30 } 31 32 return output; 33 } 34 bool IsEmpty()const{ return top == -1; } 35 bool IsFull()const{ return top == MaxTop; } 36 T Top()const; 37 ArrayStack<T>& Add(const T& x); 38 ArrayStack<T>& Delete(T& x); 39 int Quantity()const 40 { 41 return top + 1; 42 } 43 private: 44 int top; 45 int MaxTop; 46 T* stack; 47 }; 48 49 template<class T> 50 ArrayStack<T>::ArrayStack(const int& MaxStackSize=10):MaxTop(MaxStackSize-1),top(-1) 51 { 52 stack = new T[MaxStackSize]; 53 } 54 55 template<class T> 56 ArrayStack<T>::ArrayStack(T* s, const int& n,const int& MaxStackSize):MaxTop(MaxStackSize-1),top(n-1) 57 { 58 if (top>MaxTop) 59 { 60 throw OutofBounds(); 61 } 62 else 63 { 64 stack = new T[MaxStackSize]; 65 memcpy(stack, s, n*sizeof(T)); 66 } 67 } 68 69 template<class T> 70 T ArrayStack<T>::Top()const 71 { 72 if (IsEmpty()) 73 { 74 throw OutofBounds(); 75 } 76 else 77 return stack[top]; 78 79 } 80 81 template<class T> 82 ArrayStack<T>& ArrayStack<T>::Add(const T& x) 83 { 84 if (IsFull()) 85 { 86 throw NoMem(); 87 } 88 else 89 { 90 stack[++top] = x; 91 return *this; 92 } 93 } 94 95 template<class T> 96 ArrayStack<T>& ArrayStack<T>::Delete(T& x) 97 { 98 if (IsEmpty()) 99 {100 throw OutofBounds();101 }102 else103 {104 x=stack[top--];105 return *this;106 }107 }108 #endif
测试代码：
1 #include "ArrayStack.h" 2 3 int main() 4 { 5 ArrayStack<int> S; 6 std::cout << "S is empty? " << S.IsEmpty() << std::endl; 7 S.Add(1); 8 S.Add(2); 9 S.Add(3);10 S.Add(4);11 S.Add(5);12 S.Add(6);13 std::cout << "S is :" << std::endl;14 std::cout << S;15 std::cout << std::endl;16 std::cout << "Quantity of S is " << S.Quantity() << std::endl;17 int x;18 S.Delete(x);19 std::cout << "Num Deleted is " << x << std::endl;20 std::cout << "S is :" << std::endl;21 std::cout << S;22 std::cout << std::endl;23 std::cout << "Quantity of S is " << S.Quantity() << std::endl;24 25 int a[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };26 ArrayStack<int> S2(a, 8);27 std::cout << "S2 is :" << std::endl;28 std::cout << S2;29 std::cout << std::endl;30 std::cout << "Quantity of S2 is " << S2.Quantity() << std::endl;31 system("pause");32 return 0;33 34 }
输出：
堆栈的公式化描述实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。