目录

一、顺序栈

1.顺序栈的类型定义

2.构造一个空顺序栈

3.判断栈是否为空

4.入栈：插入元素x为栈顶元素

5.出栈并返回栈顶元素

6.取栈顶元素

二、双向栈

1.双向栈的类型定义

2.构造一个空双向栈

3.入栈

4.出栈

5.取栈顶元素

---

一、顺序栈

1.顺序栈的类型定义

#define MAXSIZE 100
typedef int Elemtype;
typedef struct
{
    Elemtype data[MAXSIZE];
    int top;
}SeqStack;
SeqStack S;

我们采用的方式比将top和base定义成指针更为方便！

2.构造一个空顺序栈

 int Stackinit(SeqStack &S)
{
    S.top=-1; //这里我们也可以将S.top置为0，和-1的区别就在于-1是将top更新到元素所在位置，而0是将top更新到元素的上一个位置
    return 1;
}

3.判断栈是否为空

int StackEmpty(SeqStack S)
{
    if(S.top==-1)
    {
        cout<<"栈空";
        return 1;
    }
    else
      return 0;
}

4.入栈：插入元素x为栈顶元素

int StackPush(SeqStack &S,Elemtype x) //这里注意我们要改S的data和top，所以加&
{
    if(S.top==MAXSIZE-1)
    {
        cout<<"栈满";
        return 0;
    }
    else
    {
        S.data[++S.top]=x;
        return 1;
    }
}

5.出栈并返回栈顶元素

int StackPop(SeqStack &S,Elemtype &x)
{
    if(S.top==-1)
    {
        cout<<"栈空";
        return 0;
    }
    else
    {
       x=S.data[S.top--];
    }
    return 1;
}

6.取栈顶元素

Elemtype StackGetTop(SeqStack S)  //最好将返回类型写成Elemtype，因为返回的是元素的类型
{
    return S.data[S.top];
}

二、双向栈

1.双向栈的类型定义

typedef struct
{
    Elemtype data[MAXSIZE]
    int top1,top2;
}DStack;
DStack S;

2.构造一个空双向栈

int DStackinit()
{
    S.top1=-1;
    S.top2=MAXSIZE;
    return 1;
}

3.入栈

int push(Dstack &S,Elemtype x,int i)
{
    if(S.top2-S.top1==1)
    {
        cout<<"栈满";
        return 0;
    }
    switch(i)
    {
        case 1:
            S.data[++(S.top1)]=x;
            break;
        case 2:
            S.data[--(S.top2)]=x;
            break;
        default:
            cout<<"编号输入错误";
        return 0;
    }
    return 1;
}

这里两栈共享向量空间,i是1或2表示两个栈，x是进栈元素。

4.出栈

int pop(Dstack &S,int i,Elemtype &x)
{
    switch(i):
     {
          case 1:
              if(S.top1==-1)
                  return 0;
              else
                  x=S.data[S.top1--];
              break;
          case 2:
              if(S.top2==MAXSIZE)
                  return 0;
              else
                 x=S.data[S.top2++];
              break;
          default:
              cout<<"编号输入错误";
              return 0;
      }
    return 1;
}

这里两栈共享向量空间,i是1或2表示两个栈。

5.取栈顶元素

Elemtype DStackGetTop(DStack S,int i)
{
    Elemtype x;
    switch(i):
    {
        case 1:
            x=S.data[S.top1];
            break;
        case 2:
            x=S.data[S.top2];
            break;
        default:
            cout<<"编号输入错误";
            return 0;
    }
    return x;
}

这里两栈共享向量空间,i是1或2表示两个栈。

代码的很多注释是在学习过程中遇到的一些细节问题，给自己记录一下，也希望帮助大家更好地理解代码内容。

欢迎大家在评论区讨论！