详解栈及其实现

转自：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！

栈的大小:

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

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