博客

前言

栈（Stack）是一种只允许在一端进行插入或删除操作的

线性表

。

栈顶（Top）是允许进行插入删除的一端。

栈底（Bottom）是固定不允许插入删除的一端。

栈的操作特性概括为

后进先出

（Last In First Out，LIFO）。

共享栈是让两个顺序栈共享

一个一维数组空间

，将两个栈的

栈底

分别设置在共享空间的

两端

，两个

栈顶

向共享空间的

中间

延伸。



相关知识：


C++结构体



C++指针



C++引用



栈之顺序栈

类型描述

假定线性表的元素类型为ElemType。

共享栈的顺序存储类型可描述为：

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top0;                   //栈0的栈顶指针（左边）
    int top1;                   //栈1的栈顶指针（右边）
}SharedStack;

基本操作的实现

1.基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同；

2.此处将栈0的栈顶指针

top初始化为-1

，将栈1的栈顶指针

top初始化为MaxSize

；

3.使用一个

flag

标志来区别对哪个栈操作，0表示栈0,1表示栈1；

4.进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素；

5.出栈操作：栈非空时，先取出栈顶元素值，再将栈顶指针减1；

6.栈空条件：

S.top0 == -1 && S.top1 == MaxSize

；栈满条件：

S.top1 – S.top0 == 1

。

//
// Created by Evian on 2020/3/8.
// 共享栈
#include <iostream>
using namespace std;

#define MaxSize 50
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize];
    int top0;                   //栈0的栈顶指针（左边）
    int top1;                   //栈1的栈顶指针（右边）
}SharedStack;

void InitStack(SharedStack &S);
bool isEmpty(SharedStack S);
bool Push(SharedStack &S, ElemType e, int flag);
bool Pop(SharedStack &S, ElemType &x, int flag);
ElemType GetTop(SharedStack S);
void Display(SharedStack S);

int main(){
    SharedStack stack;
    ElemType x0, x1;
    InitStack(stack);
    Push(stack, 1, 0);
    Push(stack, 2, 1);
    Push(stack, 3, 0);
    Push(stack, 4, 1);
    Push(stack, 5, 0);
    Push(stack, 6, 1);
    Display(stack);
    GetTop(stack);
    Pop(stack, x0, 0);
    Pop(stack, x1, 1);
    Display(stack);
    return 0;
}

void InitStack(SharedStack &S){
    S.top0 = -1;
    S.top1 = MaxSize;
}

bool isEmpty(SharedStack S){
    if (S.top0 == -1 && S.top1 == MaxSize){
        return true;
    } else{
        return false;
    }
}

bool Push(SharedStack &S, ElemType e, int flag){
    if (S.top1 - S.top0 == 1){                  //栈满的判断条件是两个栈顶指针相邻
        cout<<"栈为满"<<endl;
        return false;
    } else if (flag == 0){
        S.data[++S.top0] = e;
        return true;
    } else if (flag == 1){
        S.data[--S.top1] = e;
    } else{
        cout<<"请输入有效的flag值（0或1）"<<endl;
        return false;
    }
}

bool Pop(SharedStack &S, ElemType &x, int flag){
    if (flag == 0){
        if (S.top0 == -1){
            cout<<"堆栈0为空"<<endl;
            return false;
        } else{
            cout<<"Stack0 Pop: "<<S.data[S.top0--]<<endl;
            return true;
        }
    } else if (flag == 1){
        if (S.top1 == MaxSize){
            cout<<"堆栈1为空"<<endl;
            return false;
        } else{
            cout<<"Stack1 Pop: "<<S.data[S.top1++]<<endl;
            return true;
        }
    } else{
        cout<<"请输入有效的flag值（0或1）"<<endl;
    }
}

ElemType GetTop(SharedStack S){
    if (S.top0 != -1){
        cout<<"Stack0 Top: "<<S.data[S.top0]<<endl;
    }
    if (S.top1 != MaxSize){
        cout<<"Stack1 Top: "<<S.data[S.top1]<<endl;
    } else{
        cout<<"栈为空"<<endl;
        return -1;
    }
}

//打印栈中元素，栈底在前，栈顶在后
void Display(SharedStack S){
    if (S.top0 != -1){
        cout<<"Stack0: ";
        for (int i = 0; i < S.top0; i++) {
            cout<<S.data[i]<<"--->";
        }
        cout<<S.data[S.top0]<<endl;
    }
    if (S.top1 != MaxSize){
        cout<<"Stack1: ";
        for (int i = MaxSize-1; i > S.top1; i--) {
            cout<<S.data[i]<<"--->";
        }
        cout<<S.data[S.top1]<<endl;
    } else{
        cout<<"栈为空"<<endl;
    }
}

以下为打印结果：

Stack0: 1--->3--->5
Stack1: 2--->4--->6
Stack0 Top: 5
Stack1 Top: 6
Stack0 Pop: 5
Stack1 Pop: 6
Stack0: 1--->3
Stack1: 2--->4

如有错误，还请指正！TkY 0.0