1.假定有四個元素A、B、C、D，按所列次序進棧，試寫出所有可能的出棧列，注意，每一

個元素進棧后都允許出棧，如ACDB就是一種出棧序列。

解：

ABCD ABDC ACBD ADCB BACD BADC BCAD

BCDA BDCA CBAD CDBA DCBA

2.在一個數(shù)組空間stack[StackMaxSize]中可以同時存放兩個順序棧，棧底分別在數(shù)組的兩端

，當?shù)谝粋€棧的棧頂指針top1等于-1時則棧1為空，當?shù)诙€棧的棧頂指針top2等于StackMax

Size時棧2為空。兩個棧均向中間增長，當向棧1插入元素時，使top1增1得到新的棧頂位置，

當向棧2插入元素時，則使top2減1才能夠得到新的棧頂位置。當top1等于top2-1或者top2等

于top1+1時，存儲空間用完，無法再向任一棧插入元素。用于雙棧操作的順序存儲類型可定

義為：

struct Bothstack{

ElemType stack[stackMaxSize];

int top1,top2;

};

雙棧操作的抽象數(shù)據(jù)類型可定義為：

DAT BSTACK is

Data:采用順序結構存儲的雙棧，其存儲類型為Bothstack

operations:

void InitStack(Bothstack& BS,int k);

//初始化棧。當k=1或2時對應置棧1或棧2為空，k=3時置兩個格均為空

void Clearstack(BothStack& BS,int k)

//清除棧。當k=1或2時對應棧1或棧2被清除，k=3時兩個棧均被清除

int StackEmpty(BothStack& BS,int k)

//判斷棧是否為空。當k=1或2時判斷對應的棧1或棧是否為空，k=3時

//判斷兩個棧是否同時為空。若判斷結果為空則返回1，否則返回0

ElemType Peek(BothStack& BS,int k)

//取棧頂元素。當k=1或2時對應返回棧1或棧2的棧頂元素

void Push(BothStack& Bs,int k,const ElemType& item)

//進棧。當k=1或2時對應向棧1或棧2的頂端壓入元素item

End BSTACK

1.試寫出上述抽象數(shù)據(jù)類型中每一種操作的算法。

解：

void InitStack(BothStack& BS,int k)

{

if(k==1)

BS.top1=-1;

else if(k==2)

BS.top2=StackMaxSize;

else if(k==3){

BS.top1=-1;

BS.top2=StackMaxSize;

}

}

void ClearStack(BothStack& BS,int k)

{ //函數(shù)體同上

}

int StackEmpty(BothStack& BS,int k){

if(k==1)

return BS.top1==-1;

else if(k==2)

return BS.top2==StackMaxSize;

else if(k==3)

return(BS.top1==-1)&&(BS,top2==StackMaxSize);

else{

cerr<<"k的值不正確!"';

exit(1);

}

}

ElemType peek(BothStack& BS,int k)

{

if(k==1){

if(BS.top1==-1){

cerr<<"Stack 1 is empty!"<<end1;

exit(1);

}

return BS,stack(bs,top1);

}

else if(k==2){

if(BS.top2==StackMaxSize){

cerr<<"Stack 2 is empty!"<<end1;

exit(1);

}

return BS,stack[BS,top2];

}

else{

cerr<<"k的值不正確!";

exit(1);

}

}

void push(BothStack& BS,int k,const ElemType& item)

{

if(BS.top1==BS.top2-1){

cerr<<"Stack overflow!"<<end1;

exit(1);

}

if(k==1){

BS.top1++;

Bs.stack[BS.top1]=item;

}

else if(k==2){

BS.top1--;

BS.stack[BS.top2]=item;

}

}

ElemType pop(BothStack& BS,int k]

{

if(k==1){

if(BS.top==-1){

cerr<<"Stack 1 is empty!"<<end1;

exit(1);

}

BS.top--;

return BS,stack[BS.top1+1];

}

else if(k==2){

if(BS.top==StackMaxSize){

cerr<<"Stack 2 is empty!"<<end1;

exit(1);

}

BS.top2++;

return BS.stack[BS,top2-1];

}

else{

cerr<<"k的值不正確!";

exit(1);

}

}

2.假定上述所有操作的算法已存于頭文件"bstack.h"中，試編寫一個程序，讓計算機隨機

產(chǎn)生出100以內(nèi)的20個正整數(shù)并輸出，同時把它們中的偶數(shù)依次存入到第一個棧中，奇數(shù)

依次存入到第二個棧中，接著按照存入每個棧中元素的次序分別輸出每個棧中的所有元素

(此操作不改變棧的狀態(tài))，然后按照后進先出的原則輸出每個棧中的所有元素。

解：

#include<iostream.h>

#include<stdlib.h>

const int StackMaxSize=50;

typedef int ElemType;

struct BothStack{

ElemType stack[StackMaxSize];

int top1,top2;

};

#include"bstack.h"

void main()

{

BothStack a;

InitStack(a,3);//初始化兩個棧

int i,j,k;

//計算機產(chǎn)生20個隨機數(shù)并輸出，同時按奇偶數(shù)不同分別放入不同的棧中

for(i=0;i<20;i++){

j=rand()%100;

cout<<j<<"";

if(j%2==0)

push(a,1,j);

else

push(a,2,j);

}

cout<<end1;

//按照存入棧1中元素的次序輸出棧1中的所有元素

cout<<"棧1：";

for(i=0;i<=a.top1;i++)

cout<<a.stack[i]<<"";

cout<<end1;

//按照存入棧2中元素的次序輸出棧2中的所有元素

cout<<"棧2：";

for(i=StackMaxSize-1;i>=a.top2;i--)

cout<<a.stack[i]<<"";

cout<<end1;

//按照后進先出的原則輸出每個棧中的所有元素

for(k=1;k<=2;k++){

if(k==1)

cout<<"棧1：";

else

cout<<"棧2：";

while(!StackEmpty(a,k))

cout<<Pop(a,k)<<"";

cout<<end1;

}

}

該程序輸入并運行后將得到如下結果(由于機器系統(tǒng)和C++版本不同，你得到的結果可能

與此不同)：

41 67 34 0 69 24 78 58 62 5 45 81 27 61 91 95 42 27 36

棧1：34 0 24 78 58 62 64 42 36

棧2：41 67 69 5 45 81 27 61 91 95 27

棧1：36 42 64 62 58 78 24 0 34

棧2：27 95 91 61 27 81 45 5 69 67 41

3.設用第二章定義的類型為AlinkList的一維數(shù)組MS[MaxSize]建立三個鏈接堆棧，其中前三個元

素的next域用來存儲三個棧頂指針，從下標為3的元素起作為空閑元素提供給三個棧共同使用，

試編寫一個算法把從鍵盤上輸入的n個整數(shù)按照下列條件分別進入不同的棧：

⑴若輸入的整數(shù)x小于60，則進第一個棧；

⑵若輸入的整數(shù)x大于等于60同時小于100，則進第二個棧；

⑶若輸入的整數(shù)大于100，則進第三個棧。

解：

void MoreStack(ALinkList MS,int n)

//把從鍵盤上輸入的n個整數(shù)按不同條件分別進入到三個不同的鏈接棧中

{

if(n>MaxSize-3){

cerr<<"存儲空間不足!";

exit(1);

}

int i,x,av;

for(i=0;i<3;i++)

MS[i].next=0//置空棧，即給三個棧頂指針賦0

av=3;//av指向可利用元素的下標，賦初值為3

cout<<"輸入"<<n<<"個整數(shù)："<<end1;

for(i=0;i<n;i++){

//從鍵盤讀入一個整數(shù)并把它賦給av元素的值域

cin>>x;

MS[av].data=x;

//按條件把av元素壓入不同的棧，即鏈接到相應棧的棧頂

if(x<60){

Ms[av].next=MS[0].next;

MS[0].next=av;

}

else if(x>=60&&x<=100){

MS[av].next=MS[1].next;

MS[1].next=av;

}

else{

MS[av].next=MS[2].next;

MS[2].next=av;

}

//使av指向下一個可利用元素

av++;

}

}

4.編寫一個程序，首先調(diào)用上題算法，然后分別打印出每個棧中的內(nèi)容。

解：

#include<iostream.h>

#include<stdlib.h>

const int MaxSize=50;//要至少定義為比輸入的整數(shù)個數(shù)大3

typedef int ElemType;

struct ALNode{

ElemType data;

int next;

};

typedef ALNode ALinkList[MaxSize];

void MoreStack(ALinkList MS,int n)

{//函數(shù)體在此省略

}

void main()

{

ALinkList a;

int n;

cout<<"從鍵盤輸入的整數(shù)個數(shù)(1～47):";

cin>>n;

MoreStack(a,n);

for(int i=0;i<3;i++)

{ //依次將每個棧中的元素全部出棧并打印出來

int j=a[i].next;

while(j!=0){

cout<<a[j].data<<"";

j=a[j].next;

}

cout<<end1;

}

}

一次輸入和運行結果如下：

從鍵盤上輸入的整數(shù)個數(shù)為(1～47)：12

輸入12個整數(shù)：

38 64 97 120 78 33 45 214 88 25 143 60

25 45 33 38

60 88 78 97 64

143 214 120

5.已知一個中綴算術表達式為：

3+4/(25-(6+15))*8@

⑴寫出對應的后綴算術表達式。

解：3 4 25 6 15 + - /8 * + @

⑵畫出在轉換成后綴表達式的過程中運算符棧的變化。

解：略

6.已知一個后綴算術表達式為：

24 8 + 3 * 4 10 7 - * / @

⑴寫出對應的中綴算術表達式。

解： (24+8)*3/(4*(10-7))

⑵畫出在進行后綴算術表達式求值的過程中數(shù)值棧的變化。

解：略

7.為了計算表達式的值：

把棧Stack類型定義為帶模板的類型，該類型中包含順序存儲的棧和對棧的每一種基

本操作的實現(xiàn)。

解：把進行后綴表達式求值的Compute算法改寫為使用Stack類的算法。

解：把進行中綴表達式轉換為后綴表達式的Change算法改寫為使用Stack類的算法。

解：寫出計算C(n,k)的遞歸算法。

解：利用二維數(shù)組寫出計算C(n,k)的非遞歸算法。

解：分析遞歸算法和非遞歸算法的時間復雜度和空間復雜度。

解：

template<class ElemType>

class Stack{

ElemType stack[StackMaxSize];

int top;

public:

void InitStack()

//初始化棧對象，即把它置為空

{

top=-1;

}

void ClassStack()

//清除棧對象中的所有元素，使之成為一個空棧

{

top=-1;

}

int StackEmpty()

//判斷棧對象是否為空，若是則返回1，否則返回0

{

return top==-1;

}

ElemType peek()

//返回棧對象的棧頂元素，但不移動棧頂指針

{

if(top==-1){

cerr<<"Stack is empty!"<<end1;

exit(1);

}

return stack[top];

}

void push(const ElemType& item)

//元素item進棧，即插入到棧頂

if(top==StackMaxSize-1){

cerr<<"Stack overflow!"<<end1;

exit(1);

}

top++;

stack[top]=item;

}

ElemType Pop()

//刪除棧頂元素并返回之

{

if(top==-1){

cerr<<"Stack is empty!"<<end1;

exit(1);

}

ElemType temp=stack[top];

top--;

return temp;

}

}

float Compute(char* str)

{

Stack<float> s;//定義元素類型為float的棧

S.InitStack();

istrstream ins(str);

char ch;

float x;

ins>>ch;

while(ch!='@')

{ //掃描每一個字符并進行相應處理

switch(ch)

{

cass'+':

X=S.Pop()+S.Pop();

break;

cass'-':

X=S.Pop();

X=S.Pop()-X;

break;

cass'*':

X=S.Pop()*S.Pop();

break;

cass'/':

X=S.Pop();

if(X!=0.0)

X=S.Pop()/X;

else{

cerr<<"Divide by 0!"<<end1;

exit(1);

}

break;

default://讀入的必為一個浮點數(shù)的最高位數(shù)字

ins.putback(ch);

ins<<X;

}

S.Push(X);

ins>>ch;

}

if(!S.StackEmpty())

{

x=s.Pop();

if(!S.StackEmpty())

return X;

else{

cerr<<"expression error!"<<end1;

exit(1);

}

}

else{

cerr<<"Stack is empty!"<<end1;

exit(1);

}

}

void Change(char* s1,char* s2)

{

Stack<char>R;//定義元素類型為char的棧

R.InitStack();

R.push('@');

int i,j;

i=0;

j=0;

char ch=s1[i];

while(ch='@')

{

if(ch=='')

ch=s1[++i];

else if(ch=='('){

R.Push(ch);

ch=s1[++i];

}

else if(ch==')'){

while(R.peek()!='(')

s2[j++]=R.Pop();

R.Pop();

ch=s1[++i];

}

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){

char w=R.peek();

while(precedence(w)>=Precedence(ch){

s2[j++]=w;

R.Pop();w=R.Peek();

}

R.Push(ch);

ch=s1[++i];

}

else{

while(isdigit(ch)||ch=='.'){

s2[j++]=ch;

ch=s1[++i];

}

s2[j++]='';

}

}

ch=R.Pop();

while(ch!='@'){

s2[j++]=ch;

ch=R.Pop();

}

s2[j++]='@';

s2[j++]='\0';

}

8.編寫把十進制正整數(shù)轉換為十六進制數(shù)輸出的算法。

解：

void Transform(long num)

//把一個正整數(shù)num轉為一個十六進制數(shù)輸出

{

Stack a;

InitStack(a);

while(num!=0){

int k=num % 16;

Push(a,k);

num/=16;

}

while(!StackEmpty(a))

{

int X=Pop(a);

if(x<10)

cout<<x;

else{

switch(x)

{

cass 10:

cout<<'A';

break;

cass 11:

cout<<'B';

break;

cass 12:

cout<<'C';

break;

cass 13:

cout<<'D';

break;

cass 14:

cout<<'E';

break;

cass 15:

cout<<'F';

}

}

}

cout<<end1;

}

9.編寫把十進制正整數(shù)轉換為S進制(2≤S≤9)數(shù)輸出的遞歸算法，然后若把425轉換為六進制

數(shù)，畫出每次遞歸調(diào)用前和返回后系統(tǒng)棧的狀態(tài)。

解：

只給出遞歸算法，畫圖從略。

void Transform(long num,int s)

//把十進制正整數(shù)轉換為S進制數(shù)的遞歸算法

{

int k;

if(num!=0){

k=num%S;

Transfrom(num/S,S);

cout<<k;

}

}

10.裴波那契(Fibonacci)數(shù)列的定義為：它的第一項和第二項均為1，以后各項為其前兩項之和。

若裴波那契數(shù)列中的第n項用Fid(n)表示，則計算公式為：

1 (n=1或n=2)

Fib(n)= Fib(n-1)+Fib(n-2) (n>=2)

試編寫計算Fib(n)的遞歸算法和非遞歸算法，并分析它們的時間復雜度和空間復雜度。

解：

遞歸算法為：

long Fib(int n)

{

if(n==1||n==2) //終止遞歸條件

return 1;

else

return Fib(n-1)+Fib(n-2);

}

非遞歸算法為

long Fib1(int n)

{

int a,b,c;//C代表當前項，a和b分別代表當前項前面的第2項和第1項

a=b=1; //給a和b賦初值1

if(n==1||n==2)

return 1;

else

for(int i=3;i<=n;i++){

c=a+b; //求出當前項

a=b;//把前面第1項賦給前面第2項

b=c;//把當前項賦給前面第1項

}

return c;//返回所求的第n項

}

11.根據(jù)代數(shù)中的二項式定理，二項式(x+y)n的展開式的系數(shù)序列可以表示成

圖4-1那樣的三角形，其中除每一行最左和最右兩個系數(shù)等于1以外，其余各數(shù)均等于上一

行左右兩系數(shù)之和。這個系數(shù)三角形稱作楊輝三角形。

(x+y)0 1

(x+y)1 1 1

(x+y)2 1 2 1

(x+y)3 1 3 3 1

(x+y)4 1 4 6 4 1

(x+y)5 1 5 10 10 5 1

(x+y)6 1 6 15 20 15 6 1

(x+y)7 1 7 21 35 35 21 7 1

(x+y)8 1 8 28 56 70 56 28 8 1

圖4-1 楊輝三角形

設C(n,k)表示楊輝三角形中第n行(n≥0)的第k個系數(shù)(0≤k≤n)，按照二項式定理，C(n,k)

可遞歸定義為：

1 (k=0或k=n)

C(n,k)=

C(n-1,k-1)+C(n-1,k) (n>=2)

int C(int n,int k)

//求出指數(shù)為n的二項展開式中第k項(0<=k<=n)系數(shù)的遞歸算法

{

if(k==0||k==n)

return 1;

else

return C(n-1,k-1)+C(n-1,k);

}

int C1(int n,int k)

//求出指數(shù)為n的二項展開式中第k項(0<=k<=n)系數(shù)的非遞歸算法

{

typedef int b[15];

//定義一維整型數(shù)組類型[15]為b，其尺寸要大于參數(shù)n

b*a=new b[n+1];

//動態(tài)分配具有b類型的一維數(shù)組，其尺寸為n+1，這樣a就指向了一個具有

//[n+1][15]的二維數(shù)組。

for(int i=0;i<=n;i++)

for(int j=0;j<=i;j++)

//外循環(huán)每循環(huán)一次計算出指數(shù)為i的二項展開式的所有系數(shù)，內(nèi)循環(huán)每循環(huán)

//一次計算出此展開式中第j項的系數(shù)

if(j==0||j==1)

a[i][j]=1;

else

a[i][j]=a[i-1][j-1]+a[i-1][j];

return a[n][k]; //返回指數(shù)為n的二項展開式中第k項的系數(shù)

}

遞歸時間復雜度和空間復雜度分別為O(2n)和O(n)，非遞歸算法的時間復雜

度和空間復雜度均為O(n2)。

12.利用堆棧編寫出求解迷宮問題的非遞歸算法。

解：

設描述迷宮中當前位置的結構如下

struct item

{//定義描述迷宮中當前位置的結構

int x,y,d; //x和y分別表示當前位置的行坐標和列坐標，d表示移動到下一步的方向

};

此題的算法如下:

void Seekpath(int m,int n)

//查找m*n迷宮從入口(1,1)到出口(m,n)的一條通路

{

mark[1][1]=1;

Stack S;//棧的元素類型應定義為item

InitStack(s);

items temp;

temp.x=1;temp.y=1;temp.d=-1;

push(s,temp);//將入口點壓入棧

while(!stackEmpty(s))

{ //每循環(huán)一次從查找的路徑中退回一步

temp=Pop(S);//將保存的上一個位置出棧

int x=temp.x;int y=temp.y;int d=temp.d+1;

//沿著該位置的下一個方向前進

while(d<4)

{//按順時針方向試探著前進

if(x==m&&y==n)//到達出口，按逆序輸出路徑中每個位置的坐標，然后返回

{

cout<<m<<""<<n<<end1;

while(!StackEmpty(S)){

temp=Pop(S);

cout<<temp.x<<""<<temp.y<<end1;

}

return;

}

int g=x+move[d][0];int h=y+move[d][1];

//按方向d前進，求出下一個位置的坐標

if(mase[g][h]==0&&mark[g][h]==0)

{//對未訪問過的可通行的下一個位置，應將當前位置進棧，并將下一個位置

//變?yōu)楫斍拔恢茫駝t改變沿當前位置前進的方向

mark[g][h]=1;

temp.x=x;temp.y=y;temp.d=d;

Push(S,temp);

x=g;y=h;d=0;

//進入一個新位置后，重新從初開始方向東開始

}

else

d++;

}

}

cout<<"不存在從入口到出口的通路"<<end1;

}

調(diào)用此算法的完整程序如下。

#include<iostream.h>

#include<stdlib.h>

const int StackMaxSize=30;

struct item

{//定義描述迷宮中當前位置的結構

int x,y,d;//x和y分別表示當前位置的行坐標和列坐標，d表示移動到下一步的

//方向

};

typedef items ElemType; //定義棧中元素的類型為items類型

struct stack{

ElemType stack[StackMaxSize];

int top;

};

#include"stack.h"http://保存?；静僮魉惴ǖ念^文件

const M=10,N=10; //定義M和N常量，由它們決定迷宮的最大尺寸

int maze[M+2][N+2];//定義保存迷宮數(shù)據(jù)的數(shù)組

int mark[M+2][N+2];//定義保存訪問標記的數(shù)組

int move[4][2]={{0,1},{0,-1},{-1,0}};

//行下標0,1,2,3分別代表東,南,西,北方向

void SeekPath(int m,int n)

//查找m*n迷宮中從入口(1,1)到出口(m,n)的一條通路

{//函數(shù)體在此省略

}

void main(void)

{

int i,j;

int m,n;

//輸入迷宮尺寸

do{

cout<<"輸入迷宮的行數(shù)m和列數(shù)n："；

cin>>m>>n;

if(m>M||n>N)cout<<"重新輸入m和n的值."<<end1;

}while(m>M||n>N);

//輸入迷宮數(shù)據(jù)

for(i=0;i<m+2;i++)

for(j=0;j<n+2;j++)

cin>>maze[i][j];

//初始化mark數(shù)組

for(i=0;i<m+2;i++)

for(j=0;j<n+2;j++)

mark[i][j]=0;

//求解maze迷宮中從入口(1,1)到出口(m,n)的一條路徑

Seekpath(m,n);

}

13.編寫一個遞歸算法，輸出自然數(shù)1～n這n個元素的全排列。

分析：由排列組全的知識可知，n個元素的全排列共有n!種，如對于1,2,3這三個元素,其全排

列為123,132,213,231,321,312,共3!=6種。n!種可分解為n*(n-1)!種，而(n-1)!種又可分解

為(n-1)(n-2)!種，依次類推。對于n個元素 ,可把它們分別放入到n個位置上，讓第一個元素

依次取每一個元素，共有n種不同的取法，對其后n-1個位置上的n-1個元素，共有(n-1)!種不

同的排列，所以總共有n(n-1)!種不同的排列；同樣，

解：

對n個元素的全排列是一個遞算法，具體描述如下。

void Permute(int a[],int s,int n)

//對a[s]～a[n-1]中的n-s個元素進行全排列，s的初始值為0

{

int i,temp;

if(s==n-1)

{ //當遞歸排序到最后一個元素時結束遞歸，輸出a中保存的一種排列

for(i=0;i<n;i++)

cout<<a[i]<<"";

cout<<"";

}

else //繼續(xù)遞歸排列

for(i=s;i<n;i++)

{ //每循環(huán)一次使a[s]取一個新值，并對其后的所有元素進行遞歸排序

temp=a[s];a[s]=a[i];a[i]=temp;

//交換a[s]與a[i]的元素值

Permute(a,s+1,n);

//對a[s+1]～a[n-1]中的元素進行遞歸排序

temp=a[s];a[s]=a[i];a[i]=temp;

//恢復a[s]與a[i]的原有值

}

}

調(diào)用此算法的完整程序如下。

#include<iostream.h>

const int UpperLimit=6;//定義全排列的元素個數(shù)的最大值

void Permute(int a[],int s,int n)

//對a[s]～a[n-1]中的n-s個元素進行全排列，s的初值為0

{

}//函數(shù)體在此省略

void main(void)

{

int a[UpperLimt];//定義存儲n個整型元素的數(shù)組

int n;

cout<<"Enter a number'n'between 1and"

<<UpperLimit<<":";

cin>>n;//輸入待全排的元素的個數(shù)

for(int i=0;i<n;i++)

a[i]=i+1; //給數(shù)組a賦初值

cout<<end1;

Permute(a,0,n);//對數(shù)組a中的n個元素(即1-n)進行全排列

cout<<end1;

}

14.根據(jù)

解： 略

15.假定用于順序存儲一個隊列的數(shù)組的長度為N，隊首和隊尾指針分別為front和rear

，寫出求此隊列長度(即所含元素個數(shù))的公式。

解：

隊列長度的計算公式為：

(N+rear-front)%N

16.假定在一個鏈接隊列中只設置隊尾指針，不設置隊首指針，并且讓隊尾結點的指針域

指向隊首結點(稱此為循環(huán)鏈隊)，試分別寫出在循環(huán)鏈隊上進行插入和刪除的算法。

解：

插入操作的算法如下。

void QInsert(LNode*&Rear,const ElemType& item)

//使新元素item的值插入到循環(huán)鏈隊中

{

LNode*newptr=new Lnode;

//得到一個由newptr指針所指向的新結點

if(newptr==NULL){

cerr<<"Memory allocation failare"<<end1;

exit(1);

}

newptr->data=item;//把item的值賦給新結點的值域

if(Rear==NULL)

Rear=newptr->next=newptr;

//若鏈隊為空，則新結點即是隊首結點又是隊尾結點

else{

newptr->next=Rear->next;

//使新結點的指針域指向隊首結點

Rear->next=newptr;

//使隊尾結點的指針域指向新結點

Rear=newptr;

//使新結點成為新的隊尾結點

}

}

刪除操作的算法如下。

ElemType QDelete(LNode*&Rear)

//從循環(huán)鏈隊中刪除隊首元素

{

if(Rear==NULL){

cerr<<"Linked queue is empty!"<<end1;

exit(1);

}

LNode* p=Rear->next; //使p指向隊首結點

if(p==Rear)

Rear=NULL;

//若鏈隊中只有一個結點，則刪除后隊尾指針為空

else

Rear->next=p->next;

//使隊尾結點的指針域指向隊首結點的后繼結點

ElemType temp=p->data;//暫存隊首元素

delete p;//回收原隊首結點

return temp;//返回被刪除的隊首元素

}