栈结构

颠倒一个栈的元素顺序

问题：假设有一个栈{1,2,3,4,5,6}，6是栈顶，1是栈底，现在要把这个栈中的元素颠倒一下。

思路：最简单的办法当然是把栈中的元素依次pop到一个数组中，然后把这个数组再push回栈里面即可，但这样需要O(n)的辅助空间。

下面介绍一种仅使用O(1)辅助空间的算法，我们知道，可以使用递归来模拟栈的操作。我们借助函数递归pop元素，这样在递归的函数栈上依次有

{6,5,4,3,2,1}，1是栈顶，6是栈底，然后在递归返回的时候，如何把当前元素塞到原栈的底部呢？这里借助了另一个递归！

C++代码实现如下：

void Add2Bottom(stack
     
       &s, int val){    int top;    if (s.empty()) {        s.push(val);    } else {        top = s.top();        s.pop();         Add2Bottom(s, val);        s.push(top);    }   }void Reverse(stack
      
        &s) {    int top;    if (!s.empty()) {        top = s.top();        s.pop();        Reverse(s);        Add2Bottom(s, top);    }   }int main(){    int n;    int array[6] = {
   1,2,3,4,5,6};    stack
       
         s;    for (n=0; n<6; n++) s.push(array[n]);    Reverse(s);    while (!s.empty()) {        cout<
        
         <

栈的min函数

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

思路：利用辅助栈，每次对stack push/pop一个元素时，同时也要更新辅助栈（存储最小元素的位置），例如：

步骤数据栈辅助栈最小值

1.push 3 3 0 3

2.push 4 3,4 0,0 3

3.push 2 3,4,2 0,0,2 2

4.push 1 3,4,2,1 0,0,2,3 1

5.pop 3,4,2 0,0,2 2

6.pop 3,4 0,0 3

7.push 0 3,4,0 0,0,2 0

C++代码实现：

#include 
     
      #include 
      
       #include 
       
        using namespace std;template 
        
           class CStackWithMin{    public:        CStackWithMin(void) {}        virtual ~CStackWithMin(void) {}        T& top(void);        const T& top(void) const;        void push(const T& value);        void pop(void);        const T& min(void) const;    private:        deque
         
           m_data;               // the elements of stack        deque
          
            m_minIndex; // the indices of minimum elements};// get the last element of mutable stacktemplate 
           
             T& CStackWithMin
            
             ::top(){ return m_data.back();}// get the last element of non-mutable stacktemplate 
             
               const T& CStackWithMin
              
               ::top() const{ return m_data.back();}// insert an elment at the end of stacktemplate 
               
                 void CStackWithMin
                
                 ::push(const T& value){ // append the data into the end of m_data m_data.push_back(value); // set the index of minimum elment in m_data at the end of m_minIndex if(m_minIndex.size() == 0) { m_minIndex.push_back(0); } else { if(value < m_data[m_minIndex.back()]) m_minIndex.push_back(m_data.size() - 1); else m_minIndex.push_back(m_minIndex.back()); }}// erease the element at the end of stacktemplate 
                 
                  void CStackWithMin
                  
                   ::pop(){ // pop m_data m_data.pop_back(); // pop m_minIndex m_minIndex.pop_back();}// get the minimum element of stacktemplate 
                   
                    const T& CStackWithMin
                    
                     ::min() const{ assert(m_data.size() > 0); assert(m_minIndex.size() > 0); return m_data[m_minIndex.back()];}

int main()

{

class CStackWithMin<int> stk;

stk.push(3);