数据结构:两栈共享存储空间

数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为0处,另一个栈为栈的末端,即下标为数组长度

n-1处。这样,如果两个栈增加元素,就是两端点向中间延伸。当top1 + 1 == top2 的时候为栈满。

示例代码:(改编自《大话数据结构》)

#include <iostream>
using namespace std;

#define  MAXSIZE 20

typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int top1; //栈1栈顶指针
    int top2; //栈2栈顶指针
} SqStack;

/* 构造一个空栈*/
bool InitStack(SqStack *Sq)
{
    cout << "Init Stack ..." << endl;
    Sq->top1 = -1; //表示空栈
    Sq->top2 = MAXSIZE;

    return true;
}
/* 置为空栈 */
bool ClearStack(SqStack *Sq)
{
    cout << "Clear Stack ..." << endl;
    Sq->top1 = -1;
    Sq->top2 = MAXSIZE;
    return true;
}

bool StackEmpty(SqStack Sq)
{
    if (Sq.top1 == -1 && Sq.top2 == MAXSIZE)
        return true;
    else
        return false;
}

int StackLength(SqStack Sq)
{
    cout << "Stack Length : ";
    return Sq.top1 + 1 + MAXSIZE - Sq.top2;
}
/* 返回栈顶元素 */
bool GetTop(SqStack Sq, ElemType *ptr, int StackNum)
{
    if (StackNum == 1)
    {
        if (Sq.top1 != -1)
        {
            *ptr = Sq.data[Sq.top1];
            cout << "Get Top1 Item " << *ptr << endl;
            return true;
        }
        return false;
    }

    else if (StackNum == 2)
    {
        if (Sq.top2 != MAXSIZE)
        {
            *ptr = Sq.data[Sq.top2];
            cout << "Get Top2 Item " << *ptr << endl;
            return true;
        }
        return false;
    }
    else
    {
        cout << "Stack Num must be 1 or 2!" << endl;
        return false;
    }
}

/* 压栈 */
bool Push(SqStack *Sq, ElemType Elem, int StackNum)
{
    if (StackNum == 1)
    {
        cout << "Push Item to Stack1 : " << Elem << endl;
        if (Sq->top1 + 1 == Sq->top2)   //栈满
            return false;
        Sq->data[++Sq->top1] = Elem;
        return true;
    }
    else if (StackNum == 2)
    {
        cout << "Push Item to Stack2 : " << Elem << endl;
        if (Sq->top1 + 1 == Sq->top2)
            return false;
        Sq->data[--Sq->top2] = Elem;
        return true;
    }
    else
    {
        cout << "Stack Num must be 1 or 2!" << endl;
        return false;
    }
}
/* 出栈 */
bool Pop(SqStack *Sq, ElemType *ptr, int StackNum)
{
    if (StackNum == 1)
    {
        if (Sq->top1 == -1)
            return false;

        *ptr = Sq->data[Sq->top1--];
        cout << "Pop Item from Stack1 :  " << *ptr << endl;
        return true;
    }
    else if (StackNum == 2)
    {
        if (Sq->top2 == MAXSIZE)
            return false;
        *ptr = Sq->data[Sq->top2++];
        cout << "Pop Item from Stack2 :  " << *ptr << endl;
        return true;
    }
    else
    {
        cout << "Stack Num must be 1 or 2!" << endl;
        return false;
    }

}

bool StackTraverse(SqStack Sq)
{
    cout << "Traverse Stack ..." << endl;
    if (StackEmpty(Sq))
        return false;
    cout << "Stack1 : ";
    for (int i = 0; i <= Sq.top1; i++)
        cout << Sq.data[i] << ' ';
    cout << endl;
    cout << "Stack2 : ";
    for (int i = MAXSIZE - 1; i >= Sq.top2; i--)
        cout << Sq.data[i] << ' ';
    cout << endl;

    return true;
}

int main(void)
{
    SqStack Sq;
    InitStack(&Sq);
    for (int i = 0; i < 5; i++)
        Push(&Sq, i, 1);
    for (int i = 5; i < 10; i++)
        Push(&Sq, i, 2);
    StackTraverse(Sq);
    int result;
    Pop(&Sq, &result, 1);
    Pop(&Sq, &result, 2);
    StackTraverse(Sq);
    GetTop(Sq, &result, 1);
    GetTop(Sq, &result, 2);
    if (!StackEmpty(Sq))
        cout << StackLength(Sq) << endl;

    ClearStack(&Sq);

    return 0;
}

输出为:

事实上 ,使用这样的数据结构,通常都是当两个栈的空间需求有想法关系时,也就是当一个栈增长时另一个栈在缩短的情况。

还需要注意的一点是必须是同种数据类型的栈,否则不但不能更好地解决问题,反而会使问题更加复杂。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注研发

最小生成数(并查集)Kruskal算法

12720
来自专栏菩提树下的杨过

无限级分类(非递归算法/存储过程版/GUID主键)完整数据库示例_(2)插入记录

-- ======================================== -- Author:  <杨俊明,jimmy.yang@cntvs.c...

20690
来自专栏deed博客

数学速算法

16620
来自专栏软件开发 -- 分享 互助 成长

CRC校验码

循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度为N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明...

30660
来自专栏西二旗一哥

Conclusion of objective-C structure

12530
来自专栏码匠的流水账

聊聊hystrix的BucketedCounterStream

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/metric/consumer/BucketedCou...

9110
来自专栏伪君子的梦呓

题解 ~ 输出所有的水仙花数

打印所有的"水仙花数",所谓"水仙花数"是指一个三位数,其各位数字立方和等于该本身。 例如:153 是一个水仙花数,因为

18930
来自专栏java系列博客

HibernateCallback 的用法

11920
来自专栏高性能服务器开发

(二)结构体分析

继上次的redis源码分析(一)之后,本人开始订制着一份非常伟大的计划-啃完redis源代码,也对他进行了切块划分,鉴于本人目前对他的整个运行流畅还不特别清楚的...

34260
来自专栏李家的小酒馆

图论基本知识

图 图的基本概念 图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。 ? 图分为有向图和无向图,无向图为两个节点之间互相可以到达...

21800

扫码关注云+社区

领取腾讯云代金券