详解栈及其实现

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

相关文章

来自专栏Java 源码分析

LinkedList 源码分析

LinkedList 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,...

28340
来自专栏架构之路

判断栈的出栈顺序合法性

栈的出栈顺序合法性是指给定一系列元素,如1 - N,按照从小到大的方式入栈,每个元素的出栈时机不定。题目给定一个出栈顺序,我们来判断这个出栈顺序有没有可能发生。...

34430
来自专栏来自地球男人的部落格

[LeetCode] 79. Word Search

【原题】 Given a 2D board and a word, find if the word exists in the grid. The wo...

202100
来自专栏java闲聊

JDK1.8 LinkedList 源码解析

23240
来自专栏Java爬坑系列

【Java入门提高篇】Day32 Java容器类详解(十四)ArrayDeque详解

  今天来介绍一个不太常见也不太常用的类——ArrayDeque,这是一个很不错的容器类,如果对它还不了解的话,那么就好好看看这篇文章吧。

10620
来自专栏cmazxiaoma的架构师之路

浅谈CGLIB动态代理和JDK动态代理 学习笔记

57840
来自专栏云霄雨霁

数据结构----栈

16200
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列13

一、说出一些常用的类,包,接口,请各举5个 常用的类:BufferedReader BufferedWriter FileReader FileWirter ...

28930
来自专栏猿人谷

出栈顺序

之前参加过华北计算机研究所和优酷土豆的笔试,都考到出栈顺序,之前数据结构学的不到位,遇到这类题时,还着实把我愣了一会,现在总结下,省得以后再遇到这类问题,也希...

36260
来自专栏行者常至

009.多线程-AtomicInteger

版权声明:本文为博主原创文章,允许转载,请标明出处。

9020

扫码关注云+社区

领取腾讯云代金券