数据结构:栈的顺序存储结构

栈(stack)是限定在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)

,栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。

示例程序:(改编自《大话数据结构》)

#include <iostream>
using namespace std;

#define  MAXSIZE 20

typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int top; //栈顶指针
} SqStack;

/* 构造一个空栈*/
bool InitStack(SqStack *Sq)
{
    Sq->top = -1; //表示空栈
    return true;
}
/* 置为空栈 */
bool ClearStack(SqStack *Sq)
{
    cout << "Clear Stack ..." << endl;
    Sq->top = -1;
    return true;
}

bool StackEmpty(SqStack Sq)
{
    if (Sq.top == -1)
        return true;
    else
        return false;
}

int StackLength(SqStack Sq)
{
    cout << "Stack Length : ";
    return Sq.top + 1;
}
/* 返回栈顶元素 */
bool GetTop(SqStack Sq, ElemType *ptr)
{
    if (Sq.top != -1)
    {
        *ptr = Sq.data[Sq.top];
        cout << "Get Top Item " << *ptr << endl;
        return true;
    }
    return false;
}
/* 压栈 */
bool Push(SqStack *Sq, ElemType Elem)
{
    cout << "Push Item  " << Elem << endl;
    if (Sq->top + 1 > MAXSIZE - 1)
        return false;
    Sq->data[++Sq->top] = Elem;
    return true;
}
/* 出栈 */
bool Pop(SqStack *Sq, ElemType *ptr)
{
    if (Sq->top == -1)
        return false;

    *ptr = Sq->data[Sq->top--];
    cout << "Pop Item  " << *ptr << endl;
    return true;
}

bool StackTraverse(SqStack Sq)
{
    cout << "Traverse Stack ..." << endl;
    if (Sq.top == -1)
        return false;
    for (int i = 0; i <= Sq.top; i++)
        cout << Sq.data[i] << ' ';
    cout << endl;
    return true;
}

int main(void)
{
    SqStack Sq;
    InitStack(&Sq);
    for (int i = 0; i < 5; i++)
        Push(&Sq, i);
    StackTraverse(Sq);
    int result;
    Pop(&Sq, &result);
    StackTraverse(Sq);
    GetTop(Sq, &result);
    if (!StackEmpty(Sq))
        cout << StackLength(Sq) << endl;

    ClearStack(&Sq);

    return 0;
}

输出为:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏娱乐心理测试

多线程与NSTimer

1305
来自专栏ACM算法日常

求素数(暴力枚举)-HDU 3823

Besides the ordinary Boy Friend and Girl Friend, here we define a more academic ...

1114
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

2853
来自专栏Golang语言社区

map按key和按value排序

看一个题: 查找和排序 题目:输入任意(用户,成绩)序列,可以获得成绩从高到低或从低到高的排列,相同成绩 都按先录入排列在前的规则处理。 例示: jack 70...

4098
来自专栏转载gongluck的CSDN博客

FFmpeg菜鸡互啄#第6篇#音频帧格式转换(重采样)

关键步骤 struct SwrContext* swr_covert_ctx = swr_alloc_set_opts(NULL, av_get_def...

4585
来自专栏猿人谷

du熊学斐波那契I

du熊学斐波那契I Time Limit : 2000/1000ms (C/Other)   Memory Limit : 65535/32768K (C/Ot...

18410
来自专栏移动开发

FruitLoadView 一个自定义view可用来做加载view

Github地址:https://github.com/X-FAN/FruitLoadView 欢迎star

722
来自专栏逍遥剑客的游戏开发

用OpenGL绘制地球

4189
来自专栏everhad

Android自定义评分控件:RatingStarView

RatingStarView Android自定义的评分控件,类似RatingBar那样的,使用星星图标(full、half、empty)作为rating值的“...

3039
来自专栏Vamei实验室

纸上谈兵: 伸展树 (splay tree)

我们讨论过,树的搜索效率与树的深度有关。二叉搜索树的深度可能为n,这种情况下,每次搜索的复杂度为n的量级。AVL树通过动态平衡树的深度,单次搜索的复杂度为log...

18210

扫码关注云+社区