栈的三种实现

一、基于deque实现

优点：利用deque动态管理内存，栈的内存无上限，STL中的栈也是基于deque实现的。

 template<class T> class MyStack{
     deque<T> dq;
 public:
     void push(T element){
         dq.push_back(element);
     }
     void pop(){
         assert(!empty());
         dq.pop_back();
     }
     bool empty(){
         return dq.empty(); 
     }
     T& top(){
         assert(!empty());
         return dq.back();
     }
 };

二、基于数组实现

数组可选静态数组或动态数组，两种实现方式类似，都需要预选设定一个栈的最大容量。优点在于：实现简单，支持随机存储；缺点是空间受限。

typedef int TYPE;
const int STACK_SIZE = 100;
TYPE MysSack[STACK_SIZE]; 
int top_pos = -1;  

bool isEmpty(){
    return top_pos == -1;
}
bool isFull(){
    return top_pos == STACK_SIZE - 1;
}
 void push(TYPE element){
     assert(!isFull());
     MysSack[++top_pos] = element;
 }
 void pop(){
     assert(!isEmpty());
     --top_pos;
 }
 TYPE& top(){
     assert(!isEmpty());
     return MysSack[top_pos];
 }

3、基于链表实现

优点是：存储空间不收限制；缺点是，需要存储额外的链接信息，并且
销毁栈需要O(n)的时间。

 typedef int TYPE;
 typedef struct STACK_NODE {   
     TYPE value;  
     struct STACK_NODE *next;  
 } StackNode;  
 static StackNode *MyStack;  

 int isEmpty(void){  
     return MyStack == NULL;  
 }  
 int isFull(void){  
     return FALSE;  
 }
 void pop(void)  {  
     StackNode *first_node;  
     assert(!isEmpty());  
     first_node = MyStack;  
     MyStack = first_node->next;  
     free(first_node);  
 }  
 void push(TYPE value) {  
     StackNode *new_node;  
     new_node = (StackNode *)malloc(sizeof(StackNode));  
     if(new_node == NULL)  
         perror("malloc fail");  
     new_node->value = value;  
     new_node->next = MyStack;  /* 新元素插入链表头部 */  
     MyStack = new_node;       /* stack 重新指向链表头部 */  
 }  
 TYPE top(void)  {  
     assert(!isEmpty());  
     return MyStack->value;  
 }  
 void destroy_stack(void)  {  
     while(!isEmpty())  
         pop();  /* 逐个弹出元素，逐个释放节点内存 */  
 }