6-7 在一个数组中实现两个堆栈 (20分)

太过爱你忘了你带给我的痛 2022-10-26 04:56 71阅读 0赞

#### 本题要求在一个数组中实现两个堆栈。 ####

### 函数接口定义： ###

Stack CreateStack( int MaxSize );
    bool Push( Stack S, ElementType X, int Tag );
    ElementType Pop( Stack S, int Tag );

其中`Tag`是堆栈编号，取1或2；`MaxSize`堆栈数组的规模；`Stack`结构定义如下：

typedef int Position;
    struct SNode {
        
        ElementType *Data;
        Position Top1, Top2;
        int MaxSize;
    };
    typedef struct SNode *Stack;

注意：如果堆栈已满，`Push`函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则`Pop`函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

### 裁判测试程序样例： ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 1e8
    typedef int ElementType;
    typedef enum {
         push, pop, end } Operation;
    typedef enum {
         false, true } bool;
    typedef int Position;
    struct SNode {
        
        ElementType *Data;
        Position Top1, Top2;
        int MaxSize;
    };
    typedef struct SNode *Stack;
    
    Stack CreateStack( int MaxSize );
    bool Push( Stack S, ElementType X, int Tag );
    ElementType Pop( Stack S, int Tag );
    
    Operation GetOp();  /* details omitted */
    void PrintStack( Stack S, int Tag ); /* details omitted */
    
    int main()
    {
        
        int N, Tag, X;
        Stack S;
        int done = 0;
    
        scanf("%d", &N);
        S = CreateStack(N);
        while ( !done ) {
        
            switch( GetOp() ) {
        
            case push: 
                scanf("%d %d", &Tag, &X);
                if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag);
                break;
            case pop:
                scanf("%d", &Tag);
                X = Pop(S, Tag);
                if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);
                break;
            case end:
                PrintStack(S, 1);
                PrintStack(S, 2);
                done = 1;
                break;
            }
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

### 输入样例： ###

5
    Push 1 1
    Pop 2
    Push 2 11
    Push 1 2
    Push 2 12
    Pop 1
    Push 2 13
    Push 2 14
    Push 1 3
    Pop 2
    End

### 输出样例： ###

Stack 2 Empty
    Stack 2 is Empty!
    Stack Full
    Stack 1 is Full!
    Pop from Stack 1: 1
    Pop from Stack 2: 13 12 11

思路上比较简单即前后双指针，向中间靠拢。

细节处理：

一、是top1、top2的初始值。

二、栈满和栈空的条件

我第一遍写时，顺利通过,使用下面这种写法，但是当我想尝试一下Top1=0，Top2=MaxSize-1和Top1使用奇数位，Top2使用偶数位时，怎么都通不过，显示超时，我吐了，估计是题目中没有给出的`PrintStack`方法的问题。博客最后补上PrintStack和GetOp方法，便于自己调试验证。

> Top1初始值为-1，Top2初始值为MaxSize。

AC的代码：

Stack CreateStack( int MaxSize ){
        
    	Stack S =(Stack)malloc(sizeof(struct SNode));;
    	S->Data = (ElementType*)malloc(MaxSize*sizeof(ElementType));
    	S->MaxSize = MaxSize;
    	S->Top1= -1;
    	S->Top2= MaxSize;
    	return S;
    }
    bool Push( Stack S, ElementType X, int Tag ){
        
    	if(S==NULL) return false;
    	if(S->Top2 - S->Top1 == 1){
        
    		printf("Stack Full\n");
    		return false;
    	}
    	if(Tag == 1){
        
    		S->Data[++S->Top1]=X;
    	}else{
        
    		S->Data[--S->Top2]=X;
    	}
    	return true;
    }
    ElementType Pop( Stack S, int Tag ){
        
    	if(S==NULL) return ERROR;
    	if(Tag == 1){
        
    		if(S->Top1 == -1){
        
    			printf("Stack %d Empty\n",Tag); 
    			return ERROR;
    		}
    		return S->Data[S->Top1--];	
    	}else{
        
    		if(S->Top2 == S->MaxSize){
        
    			printf("Stack %d Empty\n",Tag); 
    			return ERROR;
    		}
    		return S->Data[S->Top2++];	
    	}
    }

补充的代码（取巧的代码（手动滑稽））：

Operation GetOp(){
        
        char str[4];
        scanf("%s", str);
        if (str[1] == 'u') return push;
        if (str[1] == 'o') return pop;
        if (str[1] == 'n') return end;
    }
    void PrintStack(Stack S, int Tag){
        
        printf("Pop from Stack %d:", Tag);
        if (Tag == 1){
        
            while (S->Top1 != -1){
        
                printf(" %d", S->Data[S->Top1--]);
            }
        } else {
        
            while (S->Top2 != S->MaxSize){
        
                printf(" %d", S->Data[S->Top2++]);
            }
        }
        printf("\n");
    }