详解栈及其实现

转自: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 条评论
登录 后参与评论

相关文章

来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

902
来自专栏HTML5学堂

2015.12.03 HTML5真题练习

HTML5学堂:每天一道题,强壮程序员!今日主要涉及昨日题目的解答,以及一道涉及计时器、时间对象的题目。 HTML5真题【2015.12.02】答案解析 昨日真...

3175
来自专栏文武兼修ing——机器学习与IC设计

调度队列的优先堆实现应用场景模拟应用分析代码实现

应用场景模拟 考虑优先堆的一种应用场景——按优先级的任务调度队列:每个任务有一个优先级和唯一标号,该调度队列需要具有以下功能: 添加任务:将任务添加进调度队列并...

32510
来自专栏Linyb极客之路

2016 腾讯软件开发面试题(部分)

2016 腾讯软件开发面试题(不定项选择题【1-12】) 1、已知一棵二叉树,如果先序遍历的节点顺序是: ADCEFGHB ,中序遍历是: CDFEGHAB ,...

3578
来自专栏非著名程序员

2016腾讯软件开发面试题之不定项选择题

一、前言 2017年1月27日19:05:28,今天是年三十,首先祝大家新年快乐,之前对自己要求过,每星期一篇面试题的博客,虽然今天心里有一万个不愿意写,也还是...

22510
来自专栏木子昭的博客

寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1) 异或运算 两个相同...

2535
来自专栏拭心的安卓进阶之路

Java 集合深入理解(17):HashMap 在 JDK 1.8 后新增的红黑树结构

上篇文章我们介绍了 HashMap 的主要特点和关键方法源码解读,这篇文章我们介绍 HashMap 在 JDK1.8 新增树形化相关的内容。 传统 HashMa...

2886
来自专栏Fundebug

代码面试需要知道的8种数据结构(附面试题及答案链接)

为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

886
来自专栏java学习

请问你知道什么是栈吗?

1.1栈的概念及记本操作 栈(stack)又称堆栈,是限制在表的一端进行插入和删除的线性表。其限制是仅允许在表的一端进行插入和删除操作,不允许在其他任何位置进行...

2948
来自专栏微信公众号:Java团长

初学者应该了解的数据结构:Array、HashMap 与 List

当开发程序时,我们(通常)需要在内存中存储数据。根据操作数据方式的不同,可能会选择不同的数据结构。有很多常用的数据结构,如:Array、Map、Set、List...

602

扫码关注云+社区