# 顺序栈

**Repository Path**: shaobufan/sequential-stack

## Basic Information

- **Project Name**: 顺序栈
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-12-07
- **Last Updated**: 2022-05-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构

## 栈

### 栈的定义和基本操作

栈(Stack)是只允许在表的同一端进行插入和删除操作的特殊的线性表，允许插入和删除操作的一端称为栈顶(top)，而另一端称为栈底(bottom)。当栈中没有任何元素是称为空栈。向栈中插入元素称为入栈、进栈或压入(push)，从栈中删除元素称为出栈、退栈或弹出(pop)。

由于栈只允许在栈顶插入元素，所以先入栈的元素被压在栈的底部，后入栈的元素在栈的顶部。同时，由于删除元素总是在栈顶进行，所以一定是后进入的元素先出来。因此，栈又被称为后进先出(Last In First Out)的线性表，简称LIFO表。

栈是一种很常用也是很重要的数据结构，它的用途非常广泛，例如，编译程序中的表达式计算，函数调用时的参数传递和返回等都是基于栈来实现的。

栈的抽象数据类型定义如下：

```c++
ADT Stack
{
    Init(&s)
        操作结果：构造一个空的栈s
    Destroy(&s)
        初始条件：栈s已存在
        操作结果：销毁栈s
    Clear(&s)
        初始条件：栈s已存在
        操作结果：将栈s清空
    Empty(s)
        初始条件：栈s已存在
        操作结果：若s为空栈，则返回true，否则返回false
    Length(s)
        初始条件：栈s已存在
        操作结果：返回栈s的长度
    Top(s)
        初始条件：栈s已存在,且s非空
        操作结果：返回栈顶元素
    Push(&s,e)
        初始条件：栈s已存在,且s未满
        操作结果：插入新元素e到栈顶
    Pop(&s)
        初始条件：栈s已存在,且s非空
        操作结果：删除栈顶元素
}
```

### 栈的储存结构及操作实现

从上面的描述可知，栈是一种操作受限的特殊的线性表，因此，线性表的储存结构同样适用于栈，故栈也可以采用顺序储存和链式储存结构。

#### 栈的顺序储存表示——顺序栈

用顺序储存结构表示的栈称为顺序栈。在顺序储存方式下，采用一维数组(即向量)来模拟连续的储存空间，由于插入和删除都只是在表的同一端进行，因此可以插入/删除的这一端(栈顶)是活动的;而一端(栈底)是固定的。通常，将0下标端设为栈底，栈的第1个元素(即栈底元素)存放在0下标位置。由于，栈顶位置经常变动，所以需要一个栈顶指针(或称指示器)top来只是栈顶位置。初始时，栈为空，置top=0;入栈时，top加1;出栈时，top减1;当栈满时，top等于数组空间大小。因此，top总是指在栈顶元素的后一个下标位置。

流程如图所示：

![输入图片说明](https://images.gitee.com/uploads/images/2021/1207/170416_c3856e7c_9660275.png "栈示意图.png")

顺序栈定义如下：

```c++
template <class ElemType>		//声明一个类模板
class SqStack					//顺序栈类
{
public:
    SqStack(int m);				//构造函数
    ~SqStack();					//析构函数
    void Clear();				//清空栈
    bool Empty() const;			//判栈空
    int Length() const;			//求长度
    ElemType & Top() const;		//取栈顶元素
    void Push(const ElemType &e);//入栈
    void Pop();					//出栈
    void Traverse(void(*visit)(const ElemType& e))const; //遍历栈
private:
    ElemType *m_base;			//基地址指针
    int m_top;					//栈顶指针
    int m_size;					//向量空间大小
};
```

下面给出顺序栈的基本操作的实现。

（1）栈初始化

```c++
//构造函数，分配m个结点的顺序空间，构造一个空的顺序栈
template <class ElemType>
SqStack <ElemType>::SqStack(int m)
{
    m_top=0;
    m_base=new ElemType[m];
    m_size=m;
}
```

（2）销毁栈

```c++
//析构函数，将栈结构销毁
template <class ElemType>
SqStack <ElemType>::~SqStack()
{
    if(m_base!=NULL)
        delete[] m_base;
}
```

（3）清空栈

```c++
//清空栈
template <class ElemType>
void SqStack <ElemType>::Clear()
{
    m_top=0;
}
```

（4）判栈空

```c++
//若栈为空，则返回true，否则返回false
template <class ElemType>
bool SqStack <ElemType>::Empty() const
{
    return m_top==0;
}
```

（5）求长度

```c++
//求栈中元素的个数
template <class ElemType>
int SqStack <ElemType>::Length() const
{
    return m_top;
}
```

（6）取栈顶元素值

```c++
//取栈顶元素值，先决条件时栈不空
template <class ElemType>
ElemType & SqStack <ElemType>::Top() const
{
    return m_base[m_top-1];
}
```

（7）入栈

```c++
//入栈，若栈满，则先扩展空间，插入e到栈顶
template <class ElemType>
void SqStack <ElemType>::Push(const ElemType &e)
{
    if(m_top>=m_size){
        ElemType *newbase;
        newbase = new ElemType[m_size+10];
        for(int j=0;j<m_top;j++)
            newbase[j]=m_base[j];
        delete[] m_base;
        m_base = newbase;
        m_size+=10;
    }
    m_base[m_top++]=e;
}
```

（8）出栈

```c++
//出栈，弹出栈顶元素，先决条件是栈不空
template <class ElemType>
void SqStack <ElemType>::Pop()
{
    m_top--;
}
```

（9）遍历栈

```c++
//顺序栈的遍历
template<class ElemType>
void SqStack<ElemType>::Traverse(void (*visit)(const ElemType& e))const
{
    ElemType* p = m_base;
    for (int i = 0; i < m_size; i++)
        visit(*p++);
}
```