数据结构面试之三——栈的常见操作

3.1用数组构造栈

【注意以下几点】：

1.基于数组的栈的三要素：1）栈的最大容量maxSize; 2)栈的当前容量=当前栈中元素的个数=栈顶top-1；3）动态数组存储栈的元素 Type* list；

2.对于出栈、入栈的操作要对应先判断栈空、栈满；如果空、满要有异常处理或错误提示。

3.注意入栈push操作，先入栈后top+1；出栈pop则相反，先top-1，再出栈。【注意因为，top指向数组中最后一个元素的下一个位置】。

4.拷贝构造函数和赋值函数要注意，尤其赋值的时候，避免自身赋值、同时要注意大小不一致的不能完成赋值操作，要有相关提示。

 template<typenameType>
class arrStack
{
public:
       arrStack(intnSize=100);
       ~arrStack();
       arrStack(constarrStack& copyStack);
       arrStack&operator=(const arrStack& otherStack);
 
       voidinitializeStack();
       void destroyStack();
       bool isStackEmpty();
       bool isStackFull();
       void push(constType& item);
       void pop(Type&poppedItem);
 
private:
       int maxSize;
       int top;
       Type* list;
};
 
template<typename Type>
arrStack<Type>::arrStack(int nSize=100)
{
       if(nSize < 0)
       {
              nSize = 100;
              list = newType[nSize];
              top = 0;
              maxSize = 100;
       }
       else
       {
              list = newType[nSize];
              top = 0;
              maxSize =nSize;
       }
}
 
template<typename Type>
arrStack<Type>::~arrStack()
{
       if(!list)
       {
              delete[]list;                //注意数组的删除，为delete []list;
              list = NULL;
       }
}
 
template<typename Type>
arrStack<Type>::arrStack(const arrStack& copyStack)
{
       maxSize =copyStack.maxSize;
       top = copyStack.top;
       list = newType[maxSize];           //注意需要自定义大小,容易出错.
       for( int i = 0; i <top; i++)
       {
              list[i] =copyStack.list[i];
       }
}
 
template<typename Type>
arrStack<Type>& arrStack<Type>::operator=(constarrStack& otherStack)
{
       if(this ==&otherStack)
       {
              cout <<"can't copy oneSelf!" << endl;
              return *this;
       }
       else
       {
              if(maxSize !=otherStack.maxSize)
              {
                     cout<< "The Size of two stack are not equal!" << endl;
                     return*this;
              }
              else
              {
                     maxSize= otherStack.maxSize;
                     top =otherStack.top;
                     for( inti = 0; i < top; i++)
                     {
                            list[i]= otherStack.list[i];
                     }//endfor
                     return*this;
              }
       }//end else
}
 
template<typename Type>
void arrStack<Type>::initializeStack()
{
       destroyStack();
}
 
template<typename Type>
void arrStack<Type>::destroyStack()
{
       top = 0;
}
 
template<typename Type>
bool arrStack<Type>::isStackEmpty()
{
       return (top == 0);
}
 
template<typename Type>
bool arrStack<Type>::isStackFull()
{
       return (top ==maxSize);
}
 
template<typename Type>
void arrStack<Type>::push(const Type& item)
{
       if(!isStackFull())
       {
              list[top] =item;
              top++;
       }
       else
       {
              cout <<"The Stack was already Full!" << endl;
       }
}
 
template<typename Type>
void arrStack<Type>::pop(Type& poppedItem)
{
       if(!isStackEmpty())
       {
              top--;
              poppedItem =list[top];
       }
       else
       {
              cout <<"The Stack was already Empty!" << endl;
       }
}

3.2用链表构造栈

链表构造栈注意：

1） 判断栈空的标记是top==NULL；由于栈的空间可以动态分配，因此可以认为链栈不会满。

2） 栈的入栈Push操作要先判定栈是否已经满，非满才可以入栈。先入栈，再调整top指针；

3） 栈的出栈Pop操作要先判定栈是否已空，非空才可以出栈。先调整top指针，再出栈，并删除原结点。

4） 可以加count判定当前结点的个数。

template<typename Type>
struct nodeType
{
       Type info;
       nodeType* link;
};
 
template<typename Type>
class linkedStack
{
public:
       linkedStack();
       ~linkedStack();
       linkedStack(constlinkedStack<Type>&);
       linkedStack&operator=(const linkedStack<Type>&);
 
       voidinitializeStack();
       void destroyStack();
       bool isStackEmpty()const;
       bool isStackFull()const;
       void push(constType& item);
       void pop(Type&poppedItem);
       void nodeCount();
      
       voidreversePrint();          //逆向打印的非递归实现...
 
private:
       nodeType<Type>*top;
       int count;         //统计节点个数
};
 
template<typename Type>
linkedStack<Type>::linkedStack()
{
       count = 0;
       top = NULL;
}
 
template<typename Type>
linkedStack<Type>::~linkedStack()
{
       while( top != NULL )
       {
              nodeType<Type>*tempNode = new nodeType<Type>;
              tempNode = top;
              top =top->link;
 
              deletetempNode;
       }//end if
}
 
 
template<typename Type>
linkedStack<Type>::linkedStack(constlinkedStack<Type>& copyStack)
{
       if(copyStack.top !=NULL)
       {
              nodeType<Type>*current;
              nodeType<Type>*first;
              nodeType<Type>*newNode;
             
              top = newnodeType<Type>;
              top->info =copyStack.top->info;                //此处的top不能直接用，内存报错！
              top->link =copyStack.top->link;
 
              first =top;                        //first跟进当前链表...
              current =copyStack.top->link;      //current跟进copy链表...
              while( current!= NULL)
              {
                     newNode= new nodeType<Type>;
                     newNode->link= current->link;
                     newNode->info= current->info;
 
                     first->link= newNode;
                     first =newNode;
                     current= current->link;
              }//end while
              count =copyStack.count;
       }//end if
       else
       {
              top = NULL;
              count = 0;
       }
}
 
template<typename Type>
linkedStack<Type>&linkedStack<Type>::operator=(const linkedStack<Type>&otherStack)
{
       //1避免自身赋值
       if(this ==&otherStack)
       {
              cout <<"Can't copy oneself!" << endl;
              return *this;
       }
       //2其他
       else
       {
              if(top != NULL)
              {
                     destroyStack();
              }
              if(otherStack.top!= NULL)
              {
                     nodeType<Type>*current;
                     nodeType<Type>*first;
                     nodeType<Type>*newNode;
 
                     top =new nodeType<Type>;
                     top->info= otherStack.top->info;
                     top->link= otherStack.top->link;
                     first =top;                        //first跟进当前链表...
                     current= otherStack.top->link;      //current跟进copy链表...
                     while(current != NULL)
                     {
                            newNode= new nodeType<Type>;
                            newNode->link= current->link;
                            newNode->info= current->info;
 
                            first->link= newNode;
                            first= newNode;
                            current= current->link;
                     }//endwhile
                     count =otherStack.count;
              }//end if
              else
              {
                     top =NULL;
                     count =0;
              }
              return *this;
       }
}
 
template<typename Type>
void linkedStack<Type>::initializeStack()
{
       destroyStack();
}
 
template<typename Type>
void linkedStack<Type>::destroyStack()
{
       count = 0;
       top = NULL;
}
 
template<typename Type>
bool linkedStack<Type>::isStackEmpty() const
{
       return (count == 0);
}
 
template<typename Type>
bool linkedStack<Type>::isStackFull() const //空间非固定，动态申请!
{
       return false;
}
 
template<typename Type>
void linkedStack<Type>::push(const Type& item)
{
       if(!isStackFull())
       {
              nodeType<Type>*newNode = new nodeType<Type>;
              newNode->info= item;
              newNode->link= NULL;
 
              if(top == NULL)
              {
                     top = newNode;
              }
              else
              {
                     newNode->link= top;
                     top =newNode;
              }
              count++;
              cout <<item << " was pushed!" << endl;
       }
}
 
template<typename Type>
void linkedStack<Type>::pop(Type& poppedItem)
{
       if(!isStackEmpty())
       {
              nodeType<Type>*temp = new nodeType<Type>;
              temp = top;
              poppedItem =top->info;
              top =top->link;
             
              count--;
              cout <<poppedItem << " was popped!" << endl;
              delete temp;
       }
}
 
template<typename Type>
void linkedStack<Type>::nodeCount()
{
       cout <<"nodeCount = " << count << endl;
}
 
//上一节的递归实现逆向链表打印，这是非递归的实现。
template<typename Type>
void linkedStack<Type>::reversePrint()          //逆向打印的非递归实现...
{
//  注释部分可作为链表调用栈的非递归实现。
//    nodeType<Type>*current = new nodeType<Type>;
//    current = top;
//    while(current != NULL)
//    {
//           pop(current->info);
//           current =current->link;
//    }
       int poppedItem = 0;
       while(!isStackEmpty())
       {
              pop(poppedItem);
       }

作者：铭毅天下
原文：https://blog.csdn.net/laoyang360/article/details/7871198