【数据结构】栈的相关操作

一、栈的定义

• 栈是一种特殊的线性表;
• 栈只能在线性表的一端进行操作。即只允许在栈顶（Top）操作，而不允许在栈底（Bottom）操作。　

二、栈的特性

• 由于栈只允许在栈顶（Top）操作，故栈的特性为后进先出（Last In First Out）。如下图所示：
  　　
  　　

三、栈的操作

• 创建栈
• 销毁栈
• 进栈
• 出栈
• 获取栈顶元素
• 判空
• 获取栈的大小

四、栈的实现

• 栈是一种特殊的线性表
  栈只允许在线性表的一端进行操作
  栈通常有两种实现方式：顺序结构实现(动态)、链式结构实现

参考代码：

• 顺序结构实现(动态)：

Stack.h:

#ifndef __STACK_H__
#define __STACK_H__
/**************************************************************
*                         动态顺序栈                           *
***************************************************************/
#include <stdio.h>
#include <assert.h>
#include <malloc.h>

typedef int DataType;
typedef struct Stack
{
    DataType* data;
    int top;
    int capacity;
}Stack;

//初始化
void StackInit(Stack* pStack);
//销毁
void StackDestory(Stack* pStack);

//入栈
void StackPush(Stack* pStack, DataType x);
//出栈
void StackPop(Stack* pStack);
//取栈顶元素
DataType SatckTop(Stack* pStack);
//判空
int StackEmpty(Stack* pStack);
//栈的大小
int StackSize(Stack* pStack);
//测试
void testStack();
#endif //__STACK_H__

Stack.c:

#include "Stack.h"

//初始化
void StackInit(Stack* pStack)
{
    assert(pStack);

    pStack->top = 0;
    pStack->data = (DataType*)malloc(sizeof(DataType)*3);
    assert(pStack->data);

    pStack->capacity = 3;

}
//销毁
void StackDestory(Stack* pStack)
{
    assert(pStack&&pStack->data);
    if (pStack->data)
    {
        free(pStack->data);
        pStack->data = NULL;
        pStack->capacity = 0;
        pStack->top = 0;
    }

}

//入栈
void StackPush(Stack* pStack, DataType x)
{
    assert(pStack);
    if (pStack->top == pStack->capacity)
    {
        DataType* tmp = NULL;
        tmp = (DataType*)realloc(pStack->data, sizeof(DataType)*(pStack->capacity + 3）);
        assert(pStack->data);
        pStack->data = tmp;
        pStack->capacity += 3;

    }
    pStack->data[pStack->top++] = x;

}
//出栈
void StackPop(Stack* pStack)
{
    assert(pStack);
    assert(pStack->data);
    assert(pStack->top > 0);
    pStack->top--;
}
//取栈顶元素
DataType StackTop(Stack* pStack)
{
    assert(pStack);
    assert((pStack->data)&&(pStack->top > 0));
    return pStack->data[pStack->top - 1];
}
//判空
int StackEmpty(Stack* pStack)
{
    assert(pStack);
    return pStack->top == 0;
}
//栈的大小
int StackSize(Stack* pStack)
{
    assert(pStack);
    return pStack->top;
}
//测试
void testStack()
{
    Stack s;
    StackInit(&s);
    StackPush(&s, 1);
    StackPush(&s, 2);
    StackPush(&s, 3);
    StackPush(&s, 4);

    while (!StackEmpty(&s))
    {
        printf("%d ", StackTop(&s));
        StackPop(&s);
    }

    StackDestory(&s);
}

函数调用时的栈：

• 程序中的”函数调用栈”是栈数据结构的一种应用，实际在内存堆上开辟空间
• 函数调用栈一般是从高地址向低地址增长的、栈底为内存的高地址处、栈顶为内存的低地址处
• 函数调用栈中存储的数据为活动记录

程序中的栈：

• 程序中的栈空间可看做一个顺序栈的应用，实际在内存栈上开辟空间，函数调用完毕，栈销毁
• 栈保存了一个函数调用所需的维护信息，函数参数、函数返回地址、局部变量、
• 程序栈空间在本质上是一种顺序栈
• 程序栈空间的访问是通过函数调用进行的
• 程序栈空间仍然遵从后进先出的规则