《實驗二十棧與隊列的操作》由會員分享，可在線閱讀，更多相關《實驗二十棧與隊列的操作（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、實驗二十 棧與隊列的操作
一、實驗目的
棧與隊列是重要的數(shù)據(jù)結構，通過本實驗要求掌握以下內(nèi)容：
1. 棧結構的特點及操作方法，能用面向?qū)ο蟮姆椒ǘx棧結構。
2. 隊列結構的特點及操作方法，能用面向?qū)ο蟮姆椒ǘx并檢驗隊列。
二、實驗內(nèi)容
1. 定義存儲字符的棧類，要求如下：
1) 使用教材例7.8中定義的順序棧模板，用字符作參數(shù)定義字符棧，完成壓棧和出棧操作，順序輸入26個字母，輸出為逆序。
2) 修改順序棧類，當棧滿時，執(zhí)行StackFull()操作：動態(tài)創(chuàng)建一個是原來的?？臻g的兩倍的空間，把原來棧中的內(nèi)容放入新棧，再刪除原?？臻g。（這是C++標準模板庫中的做法。）
2、
#include
#include
using namespace std;
templateclass Stack{
int top; //棧頂指針（下標）
T *elements; //動態(tài)建立數(shù)值的指針
int maxSize; //棧最大允納的元素個數(shù)
public:
Stack(int=20);
3、 //棧如不指定大小，設為20元素
~Stack(){delete[] elements;}
void Push(const T &data); //壓棧
T Pop(); //出棧，top減1
T GetElem(int i); //取數(shù)據(jù)，top不變
void StackFull(); //堆棧加倍
void MakeEmpty(){top= -1;}
4、 //清空棧
bool IsEmpty() const{return top== -1;} //判棧是否空
bool IsFull() const{return top==maxSize-1;} //判棧是否滿
void PrintStack(); //輸出棧內(nèi)所有數(shù)據(jù)
};
template Stack::Stack(int maxs){
maxSize=maxs;
top=-1;
elements=new T [maxS
5、ize]; //建立?？臻g
assert(elements!=0); //分配不成功，結束程序
}
template void Stack::PrintStack(){
for(int i=0;i<=top;i++) cout< void Stack::Push(const T &data){
if(IsFull())
{
co
6、ut<<"棧滿"< T Stack::Pop(){
assert(!IsEmpty()); //棧已空則不能退棧，退出程序
return elements[top--]; //返回棧頂元素，同時棧頂指
7、針減1
}
template T Stack::GetElem(int I){
assert(i<=top&&i>=0); //超出棧有效數(shù)據(jù)范圍，退出程序
return elements[i]; //返回棧頂元素，top不變
}
template void Stack::StackFull(){ //堆棧加倍
T * el=elements;
int i=maxSize,j;
maxSize*=2;
8、
elements=new T [maxSize]; //建立棧空間
assert(elements!=0); //分配不成功結束程序
for(j=0;j
9、,'n','o',
'p','q','r','s','t','u','v','w','x','y'},b[25];
Stack istack(5);
for(i=0;i<25;i++) istack.Push(a[i]);
istack.PrintStack();
i=0;
while(!istack.IsEmpty()){
b[i]=istack.Pop();
i++;
}
if(istack.IsEmpty()) cout<<"?？?<
10、<'\t';//注意先進后出
cout<
#include
11、assert>
using namespace std;
templateclass DeQueue;
templateclass Node{
T info;
Node *link;
public:
Node(T data=0,Node *l=NULL);
friend class DeQueue;
};
template Node::Node(T data,Node *l){
info=data;
link=l;
}
templatecla
12、ss DeQueue{
Node *front,*rear;
public:
DeQueue(){rear=front=NULL;} //構造一個空鏈隊
~DeQueue(){MakeEmpty();}
bool IsEmpty(){ return front==NULL;} //隊空否？
void EnQueFront(const T &data); //進隊
void EnQueRear(const T &data); //進隊
T DeQue(); //出隊
T GetFront();
13、 //查看隊頭數(shù)據(jù)
void MakeEmpty(); //置空隊列，與析構邏輯上不同，物理上一樣
};
templatevoid DeQueue::MakeEmpty(){
Node *temp;
while(front!=NULL){
temp=front;front=front->link;delete temp;
}
}
templatevoid DeQueue::EnQueFront(const T &data){
if(front==NULL) fr
14、ont=rear=new Node(data,NULL);
else front=new Node(data,front);
}
templatevoid DeQueue::EnQueRear(const T &data){
if(front==NULL) front=rear=new Node(data,NULL);
else rear=rear->link=new Node(data,NULL);
}
templateT DeQueue::DeQue(){
assert(!IsEmp
15、ty());
Node *temp=front;
T data=temp->info;
front=front->link;
delete temp;
return data;
}
templateT DeQueue::GetFront(){
assert(!IsEmpty());
return front->info;
}
int main(){
int i;
DeQueue que;
char str1[]="abcdefghijklmn
16、opqrstuvwxyz";
cout<<"從隊尾入隊"<
17、e()<<'\t'; //先進先出
cout<
18、1，2，3，4表示。使用棧來存儲每個行政區(qū)著色結果，棧的下標與行政區(qū)號相同。
[要求]讀懂下面的程序，并為主程序添加注釋。再設計一個行政區(qū)圖，檢驗程序是否有錯。
0
1
2
3
4
5
6
7
0
0
0
1
0
1
0
0
0
1
0
0
1
1
0
0
0
0
2
1
1
0
1
1
0
0
0
3
0
1
1
0
1
1
0
0
4
1
0
1
1
0
1
1
0
5
0
0
0
1
1
0
1
0
6
0
0
0
0
1
1
0
0
19、7
0
0
0
0
0
0
0
0
圖1.12 關系矩陣圖
1
2
3
4
5
6
7
0
圖1.11 華東行政區(qū)圖
#include
#include
using namespace std;
templateclass Stack{
int top; //棧頂指針（下標）
T *elements;
20、 //動態(tài)建立的數(shù)值
int maxSize; //棧最大允納的元素個數(shù)
public:
Stack(int=20); //棧的默認大小為20個元素
~Stack(){delete[] elements;}
void Push(const T &data); //壓棧
T Pop(); //彈出，top減1
21、 T GetElem(int i); //取數(shù)據(jù)，top不變
void StackFull(); //堆棧加倍
void MakeEmpty(){top= -1;} //清空棧
bool IsEmpty() const{return top== -1;} //判?？?
bool IsFull() const{return top==maxSize-1;} //判棧滿
void PrintStack();
22、 //輸出棧內(nèi)所有數(shù)據(jù)
};
template Stack::Stack(int maxs){
maxSize=maxs;
top=-1;
elements=new T [maxSize]; //建立?？臻g
assert(elements!=0); //分配不成功結束程序
}
template void Stack::PrintStack(){
for(int i=0;i<=top;i++) co
23、ut< void Stack::Push(const T &data){
if(IsFull()){
cout<<"棧滿"< T Stack::Pop(){
as
24、sert(!IsEmpty()); //棧已空則不能退棧，退出程序
return elements[top--]; //返回棧頂元素，同時棧頂指針減1
}
template T Stack::GetElem(int i){
assert(i<=top&&i>=0); //超出棧有效數(shù)據(jù)則錯，退出程序
return elements[i]; //返回棧頂元
25、素，top不變
}
template void Stack::StackFull(){ //堆棧加倍
T * el=elements;
int i=maxSize,j;
maxSize*=2;
elements=new T [maxSize]; //建立?？臻g
assert(elements!=0); //分配不成功，結束程序
for(j=0;j
26、ut<<"堆棧空間已加倍，空間為："< sk;
int i=1,j=1,k; //i為行政區(qū)號，從0開始；j為著色號，取1~4
sk.P
27、ush(j);
while(i4){
i--;
j=sk.Pop()+1;
}
}
for(i=0;i
實驗二十棧與隊列的操作
