栈

栈：限定仅在表尾进行插入或删除操作的线性表

栈是 先进后出 的线性表 ( 简称 LIFO )

栈有两种存储表示方式：

• 线性栈
• 顺序栈

push 表示 入栈操作
pop 表示出栈操作

表尾表示栈顶
表头表示栈底

若栈顶为n， 栈底为 0, 则该站存放了 n+1 个元素，若要找到第 i 个元素，需要出栈 n-i+1 个元素

顺序栈

先分配一定的基础容量，在使用过程中，当栈的空间不够时，再逐渐扩大

下例：实现 十进制 转化 八进制

#include "pch.h"
#include <iostream>
#include <stdlib.h>

#define STACK_INIT_SIZE 100     // 初始长度
#define STACKINCREMENT 10       // 栈满，每次添加的长度

typedef struct
{
    int * base;         // 栈底指针
    int * top;          // 栈顶指针
    int stacksize;      // 当前已分配的内存空间
}SqStack;
using namespace std;

class Stack
{
public:
    bool InitStack(SqStack &s);         // 构建空栈
    bool DestryStack(SqStack &s);       // 销毁栈
    bool ClearStack(SqStack &s);        // 清空栈
    bool StcakEmpty(SqStack s);         // 判断是否为空栈
    int  StackLength(SqStack s);        // 栈的长度
    bool GetTop(SqStack s, int &e);     // 返回栈顶
    bool Push(SqStack &s, int e);       // 入栈
    bool Pop(SqStack &s, int &e);       // 出栈
};

void conversion(int num, int n);
int main()
{
    Stack link;
    SqStack  s;
    if (link.InitStack(s))      // 初始化成功
    {
        int res,num;
        cout << "数字：";
        cin >> num;
        while (num)
        {
            link.Push(s, num % 8);
            num = num / 8;
        }
        while (!link.StcakEmpty(s))
        {
            if (link.Pop(s, res))
            {
                cout << res;
            }
        }
        cout << endl;
    }
    system("pause");
    return 0;
}


// 构建空栈
bool Stack::InitStack(SqStack &s)
{
    s.base = (int *)malloc(STACK_INIT_SIZE * sizeof(int) );
    if (!s.base) return false;
    s.top = s.base;
    s.stacksize = STACK_INIT_SIZE;
    return true;
}

// 销毁栈
bool Stack::DestryStack(SqStack &s)
{
    this->ClearStack(s);
    free(s.base);
    return true;
}

// 清空栈
bool Stack::ClearStack(SqStack &s)
{
    int e;
    while (this->StcakEmpty(s))
    {
        this->Pop(s,e);
    }
    return true;
}

// 判断是否为空栈
bool  Stack::StcakEmpty(SqStack s)
{
    return s.base == s.top;
}

// 栈的长度
int   Stack::StackLength(SqStack s)
{
    return s.stacksize;
}

// 返回栈顶
bool  Stack::GetTop(SqStack s, int &e)
{
    if (this->StcakEmpty(s)) return false;
    e = *(s.top-1);
    return true;
}

// 入栈
bool  Stack::Push(SqStack &s, int e)
{
    if (s.top - s.base >= s.stacksize) // 栈满
    {
        s.base = (int *)realloc(s.base, STACKINCREMENT * sizeof(int));
        if (!s.base) return false;
        s.top = s.base + s.stacksize;
        s.stacksize += STACKINCREMENT;
    }
    *s.top++ = e;
    return true;
}

// 出栈
bool  Stack::Pop(SqStack &s, int &e)
{
    if (this->StcakEmpty(s)) return false;
    e = *--s.top;
    return true;
}