算法２：程序11-20

程序１１：数组实现大小固定的队列和栈

#include<iostream>  //数组实现大小固定的队列和栈
using namespace std;
#include<algorithm>  
#include<limits.h>

class ArraySatck     //数组栈
{ 
public:
    ArraySatck(int initSize)  //初始化
    {
        if(initSize<0)
        {
            throw "size is wrong";
        }
        arr = new int[initSize];
        index=0;
    }

    int peek()   //栈顶
    {
        if(index ==0)
        {
            throw "empty";
        }
        return arr[index-1];
    }
    void push(int obj)  //push
    {
        if(index==sizeof(arr)/sizeof(int))
        {
            throw "full";
        }
        arr[index++]=obj;
    }

    int pop()  //pop
    {
        if(index==0)
        {
            throw " null";
        }
        return arr[--index];
    }

    int *arr;
    int index;
};
class ArrayQueue  //数组队列
{
public:
    ArrayQueue(int initSize)
    {
        if(initSize<0)
        {
            throw " size is wrong";
        }
        arr=new int[initSize];
        size=0;
        end=0;
        start=0;
    }

    int peek()
    {
        if(size==0)
        {
            throw " empty";
        }
        return arr[start];
    }

    void push(int obj)
    {
        if(size==sizeof(int)/sizeof(int))
        {
            throw"full";
        }
        size++;
        arr[end]=obj;
        end= end==sizeof(int)/sizeof(int)-1?0:end+1;
   }

   int pop()
   {
       if(size==0)
       {
           throw "empty";
       }
       size--;
       int tmp=start;
       start= start==sizeof(int)/sizeof(int)-1?0:start+1;
       return arr[tmp];
   }

    int start;
    int end;
    int size;
    int *arr;

};

int main()
{    

    ArraySatck s1(3);
    s1.push(2);
    cout<<s1.arr[0]<<endl;
    ArrayQueue s2(6);
    s2.push(5);
    cout<<s2.arr[0]<<endl;
    return 0;
}

程序１２：时间复杂度为Ｏ（１）的要求上返回栈的最小值

#include<iostream>  //返回栈中最小元素
using namespace std;
#include<stack>

 class myStack
 {
public:
    int getmin()
    {
        if(stackMin.empty())
        {
            throw "  empty";
        }
        return stackMin.top();
    }
    void push(int newNum)
    {
        if(stackMin.empty())
        {
            stackMin.push(newNum);
        }
        else if(newNum<getmin())
        {
            stackMin.push(newNum);
        }
        else
        {
            stackMin.push(stackMin.top());
        }
        stackData.push(newNum);

    }

    int pop()
    {
        if(stackMin.empty())
        {
            throw "   empty";
        }
        int tmp= stackMin.top();
        stackMin.pop();
        stackData.pop();
        return tmp;

    }

    stack<int> stackData;
    stack<int> stackMin;
 };

int main()
{    
    myStack s1;
    s1.push(4);
    s1.push(6);
    cout<<s1.stackMin.top()<<endl;
    return 0;
}

程序１３：两个队列实现栈

#include<iostream>  //两个队列实现栈
using namespace std;
#include<stack>
#include<queue>

 class TwoQueuesStack
 {
public:

    void swap()
    {
        queue<int> tmp = help;
        help = data;
        data = tmp;
    }

    void push(int pushInt)
    {
        data.push(pushInt);
    }

    int pop()
    {
        if(data.empty())
        {
            throw " empty";
        }
        while(data.size()>1)
        {
            help.push(data.front());
            data.pop();
        }
        int res = data.front();
        data.pop();
        swap();
        return res;
    }
    queue<int> data;
    queue<int> help;
 };

int main()
{    

    TwoQueuesStack t1;
    t1.push(5);
    t1.push(10);
    t1.push(56);
    cout<<t1.pop()<<endl;
    return 0;
}

程序１４：两个栈实现队列

#include<iostream>  //两个栈实现队列
using namespace std;
#include<stack>
#include<queue>

 class TwoStackQueues
 {
public:

    void push(int newData)
    {
        data.push(newData);
    }

    int pop()
    {
        if(data.empty()&&help.empty())
        {
            throw "empty";
        }
        else if(!help.empty())
        {
            int res = help.top();
            help.pop();
            return res;
        }
        while(!data.empty())
        {
            help.push(data.top());
            data.pop();
        }
        return help.top();
    }
    stack<int> data;
    stack<int> help;

 };

int main()
{    

    TwoStackQueues t1;
    t1.push(4);
    t1.push(8);
    t1.push(56);
    cout<<t1.pop()<<endl;

    return 0;
}

程序１５：猫狗队列 未完整

#include<iostream>  //猫狗队列
using namespace std;
#include<string>
#include<queue>

class Pet
{
public:
    Pet();   //不可缺
    Pet(string type)
    {
        this->type = type;
    }
    string getType()
    {
        return this->type;
    }
    string type;
};

class Dog:public Pet
{ 
public:
    Dog():Pet("dog"){}

};

class Cat:public Pet
{
    Cat():Pet("cat"){}
};

class PetEnter
{
public:
    PetEnter(Pet pet, int count) //需要用到Pet的无参构造函数，所以Pet类既要有有参构造，也要有无参构造
    {
        this->pet = pet;
        this->count = count;
    }
    Pet getPet()
    {
        return pet;
    }
    int getCount()
    {
        return count;
    }
    string getEnterPetType()
    {
        return pet.getType();
    }
    Pet pet;
    int count;
};

class DogCatQueue
{
public:
    DogCatQueue()
    {
        count = 0;
    }

    void add(Pet pet)
    {
        if(pet.getType()=="dog")
        {
            dogQ.push(PetEnter(pet, count++)); //相当于　p=PetEnter(pet,count++);dogQ.push(p);
        }
        else if(pet.getType()=="cat")
        {
            catQ.push(PetEnter(pet, count++));
        }
        else
        {
            throw " not cat or dog";
        }
    };

    Pet pollAll()
    {
        if(!dogQ.empty()&&!catQ.empty())
        {
            if(dogQ.front().getCount()<catQ.front().getCount())
            {
                Pet tmp=dogQ.front().getPet();
                dogQ.pop();
                return tmp;
            }
            else
            {
                catQ.pop();
            }
        }
        else if(!dogQ.empty())
        {
            Pet tmp=dogQ.front().getPet();
            dogQ.pop();
            return tmp;
        }
        else if(!catQ.empty())
        {
            Pet tmp=catQ.front().getPet();
            catQ.pop();
            return tmp;
        }
        else
        {
            throw "empty";
        }       
    }
    void pollDog()
    {
        if(!dogQ.empty())
        {
            // Dog tmp=dogQ.front().getPet();  //只有子类转换成父类，父类不可能转换成子类。
            dogQ.pop();
        }
        else
        {         
            throw "dog is empty";
        }      
    }

    void pollCat()
    {
        if(!catQ.empty())
        {
            catQ.pop();
        }
        else
        {         
            throw "cat is empty";
        }
    }

    bool isEmpty()
    {
        return dogQ.empty()&&catQ.empty();
    }
    queue<PetEnter> dogQ;
    queue<PetEnter> catQ;
    int count;
};

int main()
{
    DogCatQueue q;
    Pet p("dog");
    q.add(p);
    cout<<q.pollAll().getType()<<endl;

    return 0;
}

程序１６：转圈打印数组

#include<iostream>  //转圈打印数组
using namespace std;


void printEdge(int arr[3][4], int tR,int tC,int dR,int dC)
{
    if(tR==dR)
    {
        for(int i=tC;i<=dC;i++)
        {
            cout<<arr[tR][i]<<"  ";
        }
    }
    else if(tC==dC)
    {
        for(int i=tR;i<=dR;i++)
        {
            cout<<arr[i][tC]<<"  ";
        }
    }
    else
    {
        int curC=tC;
        int curR=tR;
        while(curC!=dC)
        {
            cout<<arr[tR][curC++]<<"  ";
        }
        while (curR!=dR)
        {
            cout<<arr[curR++][dC]<<" ";
        }
        while (curC!=tC)
        {
            cout<<arr[dR][curC--]<<"  ";
        }
        while (curR!=tR)
        {
            cout<<arr[curR--][tC]<<"  ";
        }
    }

}
void spiralOrderPrint(int arr[3][4])
{
    int tR=0;
    int tC=0;
    int dR=2;
    int dC=3;

    while(tR<=dR&&tC<=dC)
    {
        printEdge(arr,tR++,tC++,dR--,dC--);
    }

}


int main()
{
    int arr[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};
    spiralOrderPrint(arr);
    return 0;
}

程序１７：正方形数组顺时针旋转９０°

#include<iostream>  //正方形数组顺时针旋转９０°
using namespace std;


void rotateEdge(int arr[][4], int a,int b,int c,int d)
{
    int times=d-b;
    for(int i=0;i!=times;i++)
    {
        int tmp=arr[a][b+i];
        arr[a][b+i]=arr[c-i][b];
        arr[c-i][b]=arr[c][d-i];
        arr[c][d-i]=arr[a+i][d];
        arr[a+i][d]=tmp;
    }

}
void rotate(int arr[][4])
{
    int tR=0;
    int tC=0;
    int dR=sizeof(arr[0])/sizeof(int)-1;
    int dC=sizeof(arr[0])/sizeof(int)-1;

    while(tR<dR)
    {
        rotateEdge(arr,tR++,tC++,dR--,dC--);
    }

}


int main()
{
    int arr[][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    rotate(arr);
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            cout<<arr[i][j]<<"  ";
        }
        cout<<endl;
    }
    return 0;
}

程序１８：＂之＂字形打印二维数组

#include<iostream>  //之字形打印
using namespace std;


void printLevel(int arr[][4],int aR,int aC,int bR,int bC,bool flag)
{
     if(flag)
     {
         while (aR!=bR+1)
         {
            cout<<arr[aR++][aC--]<<"  ";
         }

     }
     else
     {
        while (bR!=aR-1)
        {
            cout<<arr[bR--][bC++]<<"  ";
        }

     }

}
void printMatrixZigZag(int arr[][4],int R,int C)
{
    int aR=0;
    int aC=0;
    int bR=0;
    int bC=0;
    int endR=R-1;
    int endC=C-1;
    bool flag=false;
    while (aR!=endR+1)
    {
        printLevel(arr,aR,aC,bR,bC,flag);
        aR=aC==endC?aR+1:aR;
        aC=aC==endC?aC:aC+1;
        bC=bR==endR?bC+1:bC;   //这行与下面一行的顺序不能颠倒，因为bR在这个过程中值发生了改变
        bR=bR==endR?bR:bR+1; 
        flag=!flag;
    }
}


int main()
{
    int arr[][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
    int arrR = sizeof(arr)/sizeof(arr[0]);
    int arrC = sizeof(arr[0])/sizeof(int);
    printMatrixZigZag(arr,arrR,arrC);
    return 0;
}

程序１９：链表是否为回文结构

#include<iostream>  //是否为回文结构
using namespace std;
#include<stack>

struct Node
{
    int value;
    Node *next;
};

bool isPalindrmoe1(Node *head)   //need N extra space
{
    stack<Node> s;
    Node *cur=head;
    while (cur!=NULL)
    {
        s.push(*cur);
        cur=cur->next;
    }
    while (head!=NULL)
    {
        if(head->value!=s.top().value)
        {
            return false;
        }
        s.pop();
        head=head->next;
    }
    return true;
}

 bool isPalindrmoe2(Node *head)  //need N/2 extra space
 {
     if(head==NULL&&head->next==NULL)
     {
         return true;
     }
     Node *right=head->next;
     Node *cur=head;
    while (cur->next!=NULL&&cur->next->next!=NULL)
    {
        right=right->next;   //right处的也要进栈
        cur=cur->next->next;
    }
    stack<Node>s;
    while (right!=NULL)
    {
        s.push(*right);
        right=right->next;
    }
    while (!s.empty())
    {
        if(head->value!=s.top().value)
        {
            return false;
        }
        head=head->next;
        s.pop();
    }
    return true;
 }

 bool isPalindrmoe3(Node *head)  //need O(1) extra space
 {
    if(head==NULL&&head->next==NULL)
    {
        return true;
    }
    Node *n1=head;
    Node *n2=head;
    while (n2->next!=NULL&&n2->next->next!=NULL)
    {
        n1=n1->next;
        n2=n2->next->next;
    }
    n2=n1->next;
    n1->next=NULL;
    Node *n3=NULL;
    while (n2!=NULL)
    {
        n3=n2->next;
        n2->next=n1;
        n1=n2;
        n2=n3;
    }
    n3=n1;  //记录最后一个节点
    n2=head; 
    bool res=true;
    while (n1!=NULL&&n2!=NULL)
    {
        if(n1->value!=n2->value)
        {
            res=false;
            break;
        }
        n1=n1->next;
        n2=n2->next;
    }
    n1=n3->next;
    n3->next=NULL;
    while (n1!=NULL)   //将原链表恢复原样
    {
        n2=n1->next;
        n1->next=n3;
        n3=n1;
        n1=n2;
    }
    return res;
 }
int main()
{
    Node *head1 = NULL;
    Node *head2 = NULL;
    Node *ptr = NULL;

    for(int i =1;i<6;i++)//构造链表
    {
        if(NULL == head1)
        {    
        head1 = new Node;
        head1->value = i;
        head1->next = NULL;
        ptr = head1;
        continue;
        }
        ptr->next = new Node;
        ptr = ptr->next;
        ptr->value = i;
        ptr->next = NULL;
    }

    Node *right = NULL;
    Node *tmp = NULL;
    for(int i =1;i<5;i++)//构造回文结构的链表
    {
        if(head2==NULL&&right==NULL )
        {    
            head2 = new Node;
            head2->value = i;
            head2->next = NULL;
            ptr = head2;

            right = new Node;
            right->value = 5-i;
            right->next = NULL;
            tmp = right;
            continue;
        }
        ptr->next = new Node;
        ptr = ptr->next;
        ptr->value = i;
        ptr->next = NULL;

        tmp->next = new Node;
        tmp = tmp->next;
        tmp->value =5-i;
        tmp->next = NULL;
    }
    ptr->next = right;

    cout<<isPalindrmoe3(head2);
    return 0;
}

程序２０：单链表安某值划分为三部分

#include<iostream>  //单链表安某值划分为三部分
using namespace std;
#include<stack>

struct Node
{
    int value;
    Node *next;
};

Node* listPartition(Node *head,int num)
{
    Node *sH=NULL;
    Node *sT=NULL;
    Node *eH=NULL;
    Node *eT=NULL;
    Node *bH=NULL;
    Node *bT=NULL;
    Node *next=NULL;
    while (head!=NULL)
    {
        next=head->next;
        head->next=NULL;
        if(head->value<num)
        {
            if(sH==NULL)
            {
                sH=head;
                sT=head;
            }
            else
            {
                sT->next=head;
                sT=head;
            }

        }
        else if(head->value==num)
        {
            if(eH==NULL)
            {
                eH=head;
                eT=head;
            }
            else
            {
                eT->next=head;
                eT=head;
            }
        }
        else if(head->value>num)
        {
            if(bH==NULL)
            {
                bH=head;
                bT=head;
            }
            else
            {
                bT->next=head;
                bT=head;
            }
        }
        head=next;
    } 
    if(sT!=NULL)
    {
        sT->next=eH;
        eT=eT==NULL?sT:eT;
    }
    if(eT!=NULL)
    {
        eT->next=bH;
    }
    return sH!=NULL?sH:eH!=NULL?eH:bH;

}

int main()
{
    Node *head1 = NULL;
    Node *head2 = NULL;
    Node *ptr = NULL;

    for(int i =1;i<5;i++)//构造链表
    {
        if(head1==NULL)
        {    
        head1 = new Node;
        head1->value = i;
        head1->next = NULL;
        ptr = head1;
        continue;
        }
        ptr->next = new Node;
        ptr = ptr->next;
        ptr->value = i;
        ptr->next = NULL;
    }
    ptr->next = new Node;
    ptr = ptr->next;
    ptr->value = 2;
    ptr->next = NULL;
    ptr->next = new Node;
    ptr = ptr->next;
    ptr->value = 4;
    ptr->next = NULL;
    Node * p=listPartition(head1,3);
    while (p!=NULL)
    {
        cout<<p->value<<" ";
        p=p->next;
    }


    return 0;
}