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

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

相关文章

来自专栏Pulsar-V

MSP430F5529LP IIC与OLED的HELLOWRLD

简单理解下什么是IIC I2C(Inter-Integrated Circuit BUS) 集成电路总线,该总线由NXP(原PHILIPS)公司设计,多用于主...

3677
来自专栏Android学习之路

Android中关于UUID的操作

2866
来自专栏图形学与OpenGL

9.3.3编程实例-图形拾取

int select_point = 0; //1 是第一个点,2是第二个,以此类推

1044
来自专栏Alan's Lab

[From Nand to Tetris] 第8章 虚拟机项目 python 实现

为防闲逛至此的看官不知所云: From Nand to Tetris 是一个在线课程,目标是指导学生从 Nand 逻辑门开始从头到尾完成一整套计算机系统。

462
来自专栏吴伟祥

星期、月份英文缩写 原

751
来自专栏calmound

poj 3083 Children of the Candy Corn(搜索)

http://poj.org/problem?id=3083 题意:迷宫沿着左墙走,和沿着右强的距离以及最短路径的距离分别是多少,当向左走的时候1的位置就是面向...

2755
来自专栏HansBug's Lab

1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果

1589: [Usaco2008 Dec]Trick or Treat on the Farm 采集糖果 Time Limit: 5 Sec  Memory L...

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

(三)dict哈希结构2

dict.c; /* Hash Tables Implementation. * * This file implements in memory ha...

2669
来自专栏章鱼的慢慢技术路

CodeCombat地牢关卡Python代码

1918
来自专栏HansBug's Lab

3299: [USACO2011 Open]Corn Maze玉米迷宫

3299: [USACO2011 Open]Corn Maze玉米迷宫 Time Limit: 10 Sec  Memory Limit: 128 MB Sub...

2624

扫码关注云+社区