[C++知识库]C++版顺序栈

栈是一种先进后出、后进先出的线性序列。

实现了顺序栈的创建和初始化，并实现了栈的入栈、出栈、取栈顶、遍历操作。

1、定义顺序栈的结构体

? ? 栈的结构体有两个成员变量，一个是栈顶指针，指向栈顶元素的上一个位置；一个是栈底指针，指向栈的底部。

struct Stack
{
    int* base;   //栈底指针
    int* top;    //栈顶指针
};

2、顺序栈初始化

? ? 给顺序栈分配一段内存空间，内存空间的容量即为栈的容量，动态分配返回的空间基地址作为栈底指针；? ? ? ? ? ? ? ? ?

? ? 初始时，栈顶指针等于栈底指针。

const int max_size = 1000;
//初始化
bool InitStack(Stack& s)
{
    s.base = new int[max_size];  //在内存上给栈分配一段空间
    if (!s.base)
    {
        return false;
    }
    s.top = s.base;   //初始时栈顶指针和栈底指针相同
    return true;
}

3、入栈操作

? ? 分两步进行：首先，将入栈元素放到栈顶指针指向的位置；然后，将栈顶指针上移一位。

? ? 注意：在入栈之前要判断栈是否已满。

//入栈
void Push(Stack& s)  
{
    int elem;
    cout << "请输入入栈元素" << endl;
    cin >> elem;
    if (s.top - s.base == max_size)   //栈已满
    {
        cout << "栈已满" << endl;
    }
    *s.top = elem;     //压入元素
    s.top++;           //栈顶指针上移，此时栈顶指针空指
}

4、出栈操作?

? ? 分两步进行：首先，将栈顶指针下移一位，使其指向真正的栈顶元素；然后，将栈顶元素取走。

//出栈
void Pop(Stack& s)
{
    int elem;
    if (s.top == s.base)
    {
        cout << "栈已空" << endl;
    }
    s.top--;          //栈顶指针下移，此时栈顶指针指向真正栈顶元素
    elem = *s.top;    //取出元素
    cout << "出栈元素为：" << elem << endl;
}

5、取栈顶元素

? ? 不需要移动栈顶指针，只取走栈顶指针前一个位置的元素即可

//取栈顶
void GetTop(const Stack& s)
{
    if (s.top == s.base)
    {
        cout << "栈已空" << endl;
    }
    int elem = *(s.top - 1);    //真正的栈顶元素是top-1位置上的元素
    cout << "栈顶元素为：" << elem << endl;
}

6、遍历打印顺序栈

? ? 定义一个指针变量，从栈底指针开始，遍历到栈顶指针的前一个位置，打印变量指向的元素。

//遍历打印
void Print(const Stack& s)
{
    for (auto i = s.base; i < s.top; i++)
    {
        cout << *i << " ";
    }
    cout << endl;
}

整体代码：

#include <iostream>
using namespace std;
#define max_size 100

struct Stack
{
    int* base;   //栈底指针
    int* top;    //栈顶指针
};

//初始化
bool InitStack(Stack& s)
{
    s.base = new int[max_size];  //在内存上给栈分配一段空间
    if (!s.base)
    {
        return false;
    }
    s.top = s.base;   //初始时栈顶指针和栈底指针相同
    return true;
}

//栈中的元素包括s.base到s.top-1位置上的所有元素
//入栈
void Push(Stack& s)  
{
    int elem;
    cout << "请输入入栈元素" << endl;
    cin >> elem;
    if (s.top - s.base == max_size)   //栈已满
    {
        cout << "栈已满" << endl;
    }
    *s.top = elem;     //压入元素
    s.top++;           //栈顶指针上移，此时栈顶指针空指
}

//出栈
void Pop(Stack& s)
{
    int elem;
    if (s.top == s.base)
    {
        cout << "栈已空" << endl;
    }
    s.top--;          //栈顶指针下移，此时栈顶指针指向真正栈顶元素
    elem = *s.top;    //取出元素
    cout << "出栈元素为：" << elem << endl;
}

//取栈顶
void GetTop(const Stack& s)
{
    if (s.top == s.base)
    {
        cout << "栈已空" << endl;
    }
    int elem = *(s.top - 1);    //真正的栈顶元素是top-1位置上的元素
    cout << "栈顶元素为：" << elem << endl;
}

//遍历打印
void Print(const Stack& s)
{
    for (auto i = s.base; i < s.top; i++)
    {
        cout << *i << " ";
    }
    cout << endl;
}

int main()
{
    int choose = 0;
    Stack s;
    if (!InitStack(s))
    {
        cout << "初始化失败" << endl;
    }
    cout << "1、入栈" << endl;
    cout << "2、出栈" << endl;
    cout << "3、取栈顶" << endl;
    cout << "4、遍历" << endl;
    cout << "9、退出" << endl;
    while (choose != 9)
    {
        cout << "请输入要做的操作" << endl;
        cin >> choose;
        switch (choose)
        {
        case 1:
            Push(s);
            break;
        case 2:
            Pop(s);
            break;
        case 3:
            GetTop(s);
            break;
        case 4:
            Print(s);
            break;
        delegate:
            break;
        }
    }


    return 0;
}