顺序栈的实现与基本操作

栈是一种只允许在一端进行插入和删除操作的线性表，允许操作的一端叫栈顶，另一端叫栈底。
通常把元素插入栈的操作称为入栈， 从栈中删除元素的操作称为出栈。
栈具有后进先出的特点，每一次入栈的元素都会成为该栈新的栈顶元素，每一次出栈操作从栈里跳出的元素的都是当前情况下的栈顶元素。

栈的实现(C语言)

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50                 //设置栈最大容量处
typedef int ElemType;              //设置栈内元素类型处

/*顺序栈结构*/
typedef struct
{
    ElemType data[MaxSize];           //存放数据数组  
    int top;                          //栈顶指针，即存放栈顶元素在data数组中的下标
}SqStack;

/*****初始化栈*****/
void InitStack(SqStack* &s)
{
    s = (SqStack *)malloc(sizeof(SqStack));    //分配一个顺序栈空间
    s->top = -1;                               //栈顶指针初始化为-1
}

/*****销毁栈*****/
void DestroyStack(SqStack* &s)
{
    free(s);
}

/*****判断栈是否为空*****/
bool StackEmpty(SqStack* s)
{
    return (s->top == -1);
}

/*****进栈*****/
bool Push(SqStack* &s, ElemType e)
{
    if (s->top == MaxSize - 1)             //栈满返回false
        return false;
    s->top++;                              //栈顶指针增1
    s->data[s->top] = e;                   //元素e放在栈顶指针处
    return true;
}

/*****出栈*****/
bool Pop(SqStack* &s, ElemType &e)
{
    if (s->top == -1)                       //栈空返回false
        return false;
    e = s->data[s->top];                    //取栈顶元素
    s->top--;
    return true;
}

/*****取栈顶元素*****/
bool GetTop(SqStack* s, ElemType &e)
{
    if (s->top == -1)
        return false;
    e = s->data[s->top];
    return true;
}

/*****获取栈的长度*****/
int getLen(SqStack* s) {
    return s->top + 1;
}                                                                       //代码参考自《数据结构教程》

下面我们来测试一下是否能正常工作：

int main()
{
    SqStack *testStack;
    InitStack(testStack);
    for (int i = 0; i < 5; i++)
    {
        Push(testStack, i);
    }
    int len = getLen(testStack);
    printf("该栈的长度为：%d\n", len);
    int top;
    GetTop(testStack, top);
    printf("栈顶元素为：%d\n", top);
    int n = 0;
    int out;
    while (1)
    {
        if (!Pop(testStack, out))
            break;
        n++;
        printf("第%d次出栈的元素为：%d\n", n, out);
    }
    if (StackEmpty(testStack))
    {
        DestroyStack(testStack);
        printf("栈为空，已成功销毁!\n");
    }
    return 0;
}

我们先依次让0， 1， 2， 3， 4入栈，然后检验该栈的长度，栈顶元素是否正确，最后全部出栈，并输出。

运行结果