详解栈及其实现

转自:melonstreet

http://www.cnblogs.com/QG-whz/p/5170418.html

栈的特点

栈(Stack)是一种线性存储结构,它具有如下特点:

1、栈中的数据元素遵守”先进后出"(First In Last Out)的原则,简称FILO结构。

2、限定只能在栈顶进行插入和删除操作。

栈的相关概念

1、栈顶与栈底:允许元素插入与删除的一端称为栈顶,另一端称为栈底。

2、压栈:栈的插入操作,叫做进栈,也称压栈、入栈。

3、弹栈:栈的删除操作,也叫做出栈。

例如我们有一个存储整型元素的栈,我们依次压栈:

在压栈的过程中,栈顶的位置一直在”向上“移动,而栈底是固定不变的。

如果我们要把栈中的元素弹出来:

出栈的顺序为3、2、1 ,顺序与入栈时相反,这就是所谓的”先入后出“。

在弹栈的过程中,栈顶位置一直在”向下“移动,而栈底一直保持不变。

如果你玩过一种称为汉诺塔的益智玩具,你就会知道游戏中小圆盘的存取就是一种先

进后出的顺序,一个圆柱就是一个栈:

栈的操作

栈的常用操作为:

1、弹栈,通常命名为pop

2、压栈,通常命名为push

3、求栈的大小

4、判断栈是否为空

5、获取栈顶元素的值

栈的存储结构

栈既然是一种线性结构,就能够以数组或链表(单向链表、双向链表或循环链表)作为底层数据结构。

本文我们以数组、单向链表为底层数据结构构建栈。

基于数组的栈实现

当以数组为底层数据结构时,通常以数组头为栈底,数组头到数组尾为栈顶的生长方向:

栈的抽象数据类型

栈提供了如上所述操作的相应接口。

template

classArrayStack

{

public:

ArrayStack(ints=10);//默认的栈容量为10

~ArrayStack();

public:

Ttop();//获取栈顶元素

voidpush(Tt);//压栈操作

Tpop();//弹栈操作

boolisEmpty();//判空操作

intsize();//求栈的大小

private:

intcount;//栈的元素数量

intcapacity;//栈的容量

T*array;//底层为数组

};

1、count 为栈的元素数量,capacity为栈的容量,count

2、本实现中不支持栈的动态扩容,栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定,默认的栈容量为10。

栈的具体实现

栈的实现还是相对简单的,很容易理解。

/*栈的判空操作*/

template

boolArrayStack::isEmpty()

{

returncount==;//栈元素为0时为栈空

};

/*返回栈的大小*/

template

intArrayStack::size()

{

returncount;

};

/*插入元素*/

template

voidArrayStack::push(Tt)

{

if(count!=capacity)//先判断是否栈满

{

array[count++]=t;

}

};

/*弹栈*/

template

TArrayStack::pop()

{

if(count!=)//先判断是否是空栈

{

returnarray[--count];

}

};

/*获取栈顶元素*/

template

TArrayStack::top()

{

if(count!=)

{

returnarray[count-1];

}

};

栈的代码测试

int_tmain(intargc,_TCHAR*argv[])

{

ArrayStackp(5);

for(inti=;i

{

p.push(i);

}

cout

cout

cout

cout

while(!p.isEmpty())

{

cout

}

getchar();

return;

}

测试结果:

栈的大小:5

栈是否为空:

栈顶元素:4

依次出栈:

4

3

2

1

基于单链表的栈

以链表为底层的数据结构时,以链表头为作为栈顶较为合适,这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部;

链表节点

/*链表节点结构*/

template

structNode

{

Node(Tt):value(t),next(nullptr){};

Node():next(nullptr){};

public:

Tvalue;

Node*next;

};

1、value:栈中元素的值

2、next:链表节点指针,指向直接后继

栈的抽象数据类型

基于链表的栈提供的接口与基于数组的栈一致。

/*栈的抽象数据结构*/

template

classLinkStack

{

public:

LinkStack();

~LinkStack();

public:

boolisEmpty();

intsize();

voidpush(Tt);

Tpop();

Ttop();

private:

Node*phead;

intcount;

};

栈的具体实现

/*返回栈的大小*/

template

intLinkStack::size()

{

returncount;

};

/*栈的判空操作*/

template

boolLinkStack::isEmpty()

{

returncount==;

};

/*插入元素*/

template

voidLinkStack::push(Tt)

{

Node *pnode=newNode(t);

pnode->next=phead->next;

phead->next=pnode;

count++;

};

/*弹栈*/

template

TLinkStack::pop()

{

if(phead->next!=nullptr)//栈空判断

{

Node*pdel=phead->next;

phead->next=phead->next->next;

Tvalue=pdel->value;

deletepdel;

count--;

returnvalue;

}

};

/*获取栈顶元素*/

template

TLinkStack::top()

{

if(phead->next!=nullptr)

returnphead->next->value;

};

栈的代码测试

int_tmain(intargc,_TCHAR*argv[])

{

LinkStacklstack;

lstack.push("hello");

lstack.push("to");

lstack.push("you!");

cout

cout

while(!lstack.isEmpty())

{

lstack.pop();

}

cout

getchar();

return;

}

测试结果:

栈的大小:3

栈顶元素:you!

栈的大小:

觉得本文有帮助?请分享给更多人

关注「算法爱好者」,修炼编程内功

本文来自企鹅号 - 算法爱好者媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Guangdong Qi

小Q项目框架搭建及会动的Tabbar未完待续,持续更新中

1564
来自专栏我杨某人的青春满是悔恨

在 iPhone 上使用 Popover Segue

iOS 系统提供了4种基本的转场方式:Show、Show Detail、Present Modally、Present as Popover。我们平常用的最多的...

955
来自专栏编程微刊

hcharts实现堆叠柱形图

1343
来自专栏移动开发之家

Android音频播放(本地/网络)绘制数据波形,根据特征有节奏的改变颜色

MediaPlayer、MediaRecord、AudioRecord,这三个都是大家耳目能详的Android多媒体类(= =没听过的也要假装听过),包含了音视...

2262
来自专栏Hongten

java开发_windows下面的关机,重启,注销小程序_源码下载

========================================================

1611
来自专栏向治洪

Android仿京东、天猫商品详情页

前言 前面在介绍控件TabLayout控件和CoordinatorLayout使用的时候说了下实现京东、天猫详情页面的效果,今天要说的是优化版,是我们线上实现的...

1805
来自专栏叁金大数据

WPF Canvas 画区域

有时候需要实现类似于QQ截图那样的选择区域功能,这里的区域可以是一条线,圆,矩形等等

1373
来自专栏张善友的专栏

AMF: ASP.NET Mobile Framework

ASP.NET移动框架(AMF)是一种最常用的平板电脑和智能手机上Web应用程序的框架,基于jQuery Mobile(http://jquerymobile....

18710
来自专栏wOw的Android小站

[Android][Framework] 无障碍快捷方式相关代码

问题:无障碍快捷方式(Accessibility Shortcut)打开不生效。

1181
来自专栏菩提树下的杨过

silverlight:手写板/涂鸦/墨迹/InkPresenter示例程序

这种应用现在已经比较常见了,比如论坛回贴中的手写功能 ,IM聊天中的个性化手写文字,个性签名等,在Silverlight中要实现该功能其实非常简单,只要一个I...

27910

扫码关注云+社区