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

数组有两个端点,两个栈有两个栈底,让一个栈的栈底为数组的始端,即下标为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 条评论
登录 后参与评论

相关文章

来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1442
来自专栏IT杂记

Storm客户端提交任务失败原因分析

2710
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

3081
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2608
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

2152
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

931
来自专栏everhad

消息处理管道

TODO: 待写 消息处理管道 一个App看作是系统,外部输入消息需要经过一系列处理,涉及不同接收者。消息处理的跟踪(Trace)和结果的保存。 比如设计一个...

1966
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

832
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

8175
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2762

扫码关注云+社区