C/C++数据结构---在一个数组中实现两个堆栈（PTA）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C/C++数据结构---在一个数组中实现两个堆栈（PTA）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人主页

仍有未知等待探索_数据结构,C语言疑难,小项目-CSDN博客

专题分栏---数据结构

数据结构_仍有未知等待探索的博客-CSDN博客

一、前言

二、题目

要求

函数接口定义

裁判测试程序样例

输入样例

输出样例

三、分析

1.栈的特点

2.题目分析

3.栈的创建

4.入栈

5.出栈

四、总代码

一、前言

今天写老师留的PTA的作业时，遇到一个非常不一样的栈，我觉得应该把它写出来，让大家眼前一亮，扩展一下视野，并且也能让我有更深层次的理解！

二、题目

要求

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

函数接口定义：
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

三、分析

在写之前，我们要明白，什么是在一个数组里面实现两个堆栈。堆栈好理解，就是线性表的一种特殊的形式。

栈，不像正常的顺序表那样能完成增删改查的操作，栈只能进行入栈和出栈的操作。虽然操作的形式变少了，但是栈也有自己的优点，他的入栈和出栈的时间复杂度为O(1)，相比正常的顺序表快了不少。

1.栈的特点

1、后进先出 2、入栈和出栈的时间复杂度为O(1)

一般栈的数据类型为：

#define MaxSize 1000
typedef int elemtype; 
struct LNode
{
    elemtype data[MaxSize];
    int top;栈顶指针，存储的是栈顶上的下标
}

2.题目分析

根据题目所说的一个数组开辟两个堆栈，如图所示：

栈顶指针Top1，Top2的初始位置分别为-1，和MaxSize。题目中的Tag变量存的是堆栈的编号，当Tag==1时，指的是栈顶指针为Top1的栈；Tag==2时，指的是栈顶指针为Top2的栈。

其中Top1为栈顶指针的栈是个正常的栈，而Top2为栈顶指针的栈是一个反向的栈，入栈的时候，要注意栈顶指针往左移，出栈的时候，栈顶指针往右移。

要注意栈满的时候的条件：Top1+1==Top2，如图所示：

3.栈的创建
typedef int Position;
struct SNode {
    ElementType *Data;
    Position Top1, Top2;
    int MaxSize;
};
typedef struct SNode *Stack;
根据题目给的栈的类型可知：首先，需要给栈类型开辟空间、指针Data开辟空间。

然后需要给两个不同的栈顶变量赋初值。不要忘了，栈类型里面还有MaxSize变量也要赋初值。
Stack CreateStack(int MaxSize)
{
    Stack s = (Stack)malloc(sizeof(struct SNode));
    s->Data = (int*)malloc(sizeof(ElementType) * MaxSize);
    s->Top1 = - 1;
    s->Top2 = MaxSize;
    s->MaxSize = MaxSize;
    return s;
}

4.入栈

在入栈前要先判断一下栈是否已经满了，满了的条件根据上述讲解，可知S->Top1+1 == S->Top2。如果没满的话，根据Tag的来分辨是栈顶指针是Top1还是栈顶指针是Top2的。最后先栈顶指针Top1++或Top2--；再赋初值。
bool Push(Stack S, ElementType X, int Tag)
{
    if (S->Top1+1 == S->Top2)
    {
        printf("Stack Full\n");
        return false;
    }
    if (Tag == 1)
    {
         S->Top1++;
         S->Data[S->Top1] = X;
    }
    if(Tag==2)
    {
        S->Top2--;
        S->Data[S->Top2] = X;
    }
    return true;
}

5.出栈

出栈也是一样的，先判断栈是否为空，如果不为空，那就栈顶指针Top1--或Top2++

ElementType Pop(Stack S, int Tag)
{
    if (Tag == 1)
    {
        if (S->Top1 == -1)       
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        return S->Data[S->Top1--];   
    }

    if (Tag == 2)
    {
        if (S->Top2 == S->MaxSize) 
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        return S->Data[S->Top2++];
    }
}

四、总代码

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

    if (Tag == 2)
    {
        if (S->Top2 == S->MaxSize) 
        {
            printf("Stack %d Empty\n", Tag);
            return ERROR;
        }
        return S->Data[S->Top2++];
    }
}

C/C++数据结构---在一个数组中实现两个堆栈（PTA）,PTA,数据结构,c语言