@TOC

栈

只能在一边进出，先进的后出。

进出的一端叫做栈顶，另一端叫做栈底。

栈可以使用顺序存储结构，也能使用链式存储结构。

注意：栈只能在一端进行操作，这是栈的关键特征，也就是说栈不允许在中间进行查找、插入、删除等操作，(但是在实际应用中我们可以打破它)。

这里掌握初始化、入栈、出栈、取栈顶元素操作即可。

顺序存储结构实现栈

#include<iostream>
using namespace std;

#define MAX_SIZE 128
typedef int DataType;

//栈的结构有多重方式定义，不用局限于这一种
/*
    例如:
        定义两个int型，并且直接开辟好数组空间
        定义一个指针，一个int top
*/
typedef struct _Stack
{
    DataType* top;    //栈顶指针
    DataType* base;//栈底指针
    //其实没有必要定义一个来标记元素的个数。
    //两个指针指向同一个数组，他们两个相减得到是中间元素的个数。
    //否则两个地址相减没有意义
}Stack;

//栈的初始化
bool initStack(Stack& S)
{
    //先用栈底指针来拿到这个刚开辟好空间的数组
    S.base = new int[MAX_SIZE];//指针来定位这个数组
    if (!S.base)
    {
        return false;
    }
    S.top = S.base;
    return true;
}

//入栈
bool pushStack(Stack& S, DataType data)
{
    if (!S.base)
    {
        return false;
    }
    if (S.top - S.base == MAX_SIZE)
    {
        //栈满
        return false;
    }

    //栈中还有空位置
    *(S.top) = data;
    S.top++;
    return true;
}

//出栈-栈顶元素出栈
DataType popStack(Stack& S)
{
    //不为空
    if (S.top != S.base)
    {
        return *(--S .top);
    }
    else
    {
        return -1;
    }
}
//返回栈顶元素         
DataType getTop(Stack& S)
{
    if (S.top - S.base == 0)
    {
        return -1;
    }
    return *(S.top-1);
}
int main(void)
{
    Stack S;
    initStack(S);    
    int n = 0;
    int m = 0;
    cin >> n;
    m = n;
    while (n)
    {    
        pushStack(S, n);
        n--;
    }
    cout << "____" << endl;
    cout << getTop(S) << endl;
    cout << "____" << endl;
    while (m)
    {
        cout << popStack(S) << endl;
        m--;
    }
    return    0;
}

入栈操作图示:

链接存储结构实现栈

#include<iostream>
using namespace std;

//数据类型
typedef int DataType;
//最大存储数量
#define  MAX_SZIE 128
//结点结构
typedef struct _Snode
{
    DataType data;
    struct _Snode* next;
}Snode;

//栈(头)结构
typedef struct _Stack
{
    int count;
    Snode* base;
    Snode* top;
}Stack;

//初始化
bool initStack(Stack* S)
{
    if (!S)
    {
        return false;
    }
    S->base = S->top = NULL;
    S->count = 0;
    return true;
}

//入栈
bool pushStack(Stack* S, Snode* node)
{
    if (!S || !node)
    {
        return false;
    }

    //第一次插入元素
    if (S->count == 0)
    {
        S->base = S->top = node;
        S->top->next = NULL;
        S->count++;
    }
    else
    {
        S->top->next = node;
        S->top = node;
        S->count++;
    }
    return false;
}
//出栈
bool popStack(Stack* S)
{
    if (!S || S->count == 0)
    {
        return false;
    }
    Snode* tempnode = S->base;

    while (tempnode->next != S->top && S->count != 1)
    {
        tempnode = tempnode->next;
    }
    if (S->count == 1)//如果栈中只剩下一个结点可以删除
    {
        S->base = NULL;
    }
    //现在tempnode是top的前一个结点
    delete S->top;
    S->top = tempnode;//如果是最后一个结点的话base和top都被置空了
    S->top->next = NULL;
    
    S->count--;
    return true;
}
//拿到栈顶元素
bool getTop(Stack* S,DataType* m_data)
{
    if (!S || S->count == 0)
    {
        return S;
    }
    *m_data = S->top->data;
    return false;
}
//判断栈是否为空
bool isEmpty(Stack* S)
{
    if (S->count == 0)
    {
        return true;
    }
    return false;
}
int main(void)
{
    Stack* S = new Stack;
    initStack(S);

    int n = 5;
    int m = n;
    while (n)
    {
        Snode* tempnode = new Snode;
        tempnode->data = n;
        pushStack(S, tempnode);
        n--;
    }

    while (m >0)
    { 
        m--;
    }

    cout << S->top->data << " ";
    popStack(S);

    cout << S->top->data << " ";
    popStack(S);

    cout << S->top->data << " ";
    popStack(S);
    
    cout << S->top->data << " ";
    popStack(S);

    cout << S->top->data << " ";
    popStack(S);

    if (!isEmpty(S))
    {
        cout << S->top->data << " ";
    }


    int temp = 0;
    getTop(S, &temp);
    cout << temp << endl;

    delete S;
    return    0; 
}

补充:要修改指针指向地址，可以传递二级指针。

一级指针修改值。

实际应用

迷宫求解

链接——【栈】实现迷宫求解(C++)(详解)

表达式求值

链接——【数据结构】栈(C++)