《数据结构与算法 C语言版》—— 3.5典型例题

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第3章，第3.5节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.5典型例题

例1设有两个栈S1、S2采用顺序栈方式，并且共享一个数组A［Maxsize］，为了尽量利用空间，减少溢出的可能，采用栈顶相向、迎面增长的存储方式。设计S1、S2的有关初始化、入栈和出栈的操作算法。
解两栈共享数组空间，将两栈栈底设在数组的两端，初始时，top［0］=-1，top［1］=Maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，两栈顶指针都指向栈顶元素。

#define Maxsize 100//栈空间容量
typedef struct {
ElemType data［Maxsize］;
int Top［2］;//指向栈顶元素
}Dstack;

初始化、入栈和出栈的操作算法如下。
(1)初始化操作

void InitStack(Dstack &S){
S.Top［0］=-1;S.Top［1］=Maxsize;
}

(2)进栈操作

int Push(Dstack &S,ElemType x,int i){
if(S.Top［0］+1==S.Top［1］)return 0;//栈满
switch(i){
case 0:S.Top［0］++;S.data［S.Top［0］］=x;break;
case 1:S.Top［1］--;S.data［S.Top［1］］=x;break;
default:return 0;
}
return 1;
}

(3)出栈操作

int Pop(Dstack &S,ElemType &x,int i){
switch(i){
case 0:if(S.Top［0］==-1)return 0;   x=S.data［S.Top［0］］;S.Top［0］--;break;
case 1:if(S.Top［1］==Maxsize)return 0;x=S.data［S.Top［1］］;S.Top［1］++;break;
default:return 0;
}
return 1;
}

例2设从键盘输入一个整数序列:a1，a2，…，an。试编写一个算法实现:用栈结构存储输入的整数，当a≠－1时，进栈；当a=－1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。
解算法描述如下：

#define Maxsize 100//栈空间容量
void InOutStack(int S［Maxsize］){
int i,x,n,top=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
if(x!=-1)
if(top==Maxsize-1){printf("栈满\\\\n");exit(OVERFLOW);}
else S［++top］=x;
else
if(top==0){printf("栈空\\\\n");exit(OVERFLOW);}
else printf("出栈元素是%d\\\\n",S［top--］);
}
}

例3设结点结构为(data,next)，试用一个全局指针p和某种链接结构实现一个队列，并给出入队和出队操作的算法，要求它们的时间复杂度都是O(1)(不计new和delete时间)。
解本题可采用链表结构来实现。但题目中仅给一个全局指针p，且入队和出队的时间复杂度都是O(1)，因此我们用只设尾指针的循环链表来实现，算法描述如下。
(1)入队操作

void EnQueue(LinkQueue &P,ElemType x){
Qnode *s;
s=new Qnode;
s->data=x;
s->next=P->next;
P->next=s;P=s;
}

(2)出队操作

void DeQueue(LinkQueue &P,ElemType &x){
Qnode *s;
if(P->next==P){printf("空队列\\\\n");exit(OVERFLOW);}
else{
s=P->next->next;
P->next->next=s->next;
x=s->data;
if(P==s)P=P->next;//只有一个结点的情况
delete s ;
}
}

例4利用两个栈S1和S2来模拟一个队列。已知栈的三个操作如下：Push(S,x)，元素x入栈；Pop(S,x)，栈顶元素x出栈；StackEmpty(S)，判栈是否为空栈。利用栈的操作来实现该队列的三个操作：EnQueue()，插入元素入队列；DeQueue()，删除一个元素出队列；QueueEmpty()，判队列是否为空队列。
解栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈S1和S2来模拟一个队列时，S1作为输入栈，逐个元素入栈，以此模拟队列元素的入队。当需要出队时，将栈S1出栈并逐个压入栈S2中，S1中最先入栈的元素，在S2中处于栈顶。S2出栈，相当于队列的出队，实现了先进先出。显然，只有S2为空且S1也为空时，才算是空队列。算法如下。
(1)入队操作

int EnQueue(Stack &s1,ElemType x){//s1是容量为n的栈，栈元素类型为ElemType。入栈成功返回OK，

//否则返回ERROR
if(s1top==n&&!StackEmpty(s2)){//top是s1的栈顶指针，s1满s2非空，这时s1不能再入栈
printf("栈满\\\\n");
exit(OVERFLOW);
}
if(s1top==n&&StackEmpty(s2))//若s2空，先将s1出栈，元素压入栈s2
while(!StackEmpty(s2)){Pop(s1,x);Push(s2,x);}
Push(s1,x);return(OK);//x入栈，实现了队列元素的入队
}

(2)出队操作
void DeQueue(Stack s1,Stack &s2){//s2是输出栈，将s2栈顶元素出栈，实现队头元素的出队

ElemType x;
if(!StackEmpty(s2)){//栈s2不空，则直接出栈
Pop(s2,x);printf("出队元素为%d\\\\n",x);
}
else//处理s2空栈
if(StackEmpty(s1)){//若输入栈也为空，则判定空队列
printf("队列空\\\\n");
exit(OVERFLOW);
}
else{//先将s1倒入s2，再进行出队操作
while(!StackEmpty(s1)){Pop(s1,x);Push(s2,x);}
Pop(s2,x); //s2出栈相当于队列出队
printf("出队元素为%d\\\\n",x);
}
}

(3)判队列空

int QueueEmpty(){//队列空返回1，否则返回0
if(StackEmpty(s1)&&StackEmpty(s2))return 1;
else return 0;
}