算法２：程序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;
}
