1. 栈的简介
1.1栈的特性
栈(Stack)是一种线性存储结构，它具有如下特点：
栈中的数据元素遵守”
先进后出"(First In Last Out)的原则，简称FILO结构。限定只能在栈顶进行插入和删除操作（单向操作）。
1.2栈的相关概念
栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。压栈：栈的插入操作，叫做进栈，也称压栈、入栈。弹栈：栈的删除操作，也叫做出栈。
例：我们有一个存储整型元素的栈，我们依次压栈：{1,2,3}
在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。 如果我们要把栈中的元素弹出来：
出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”先入后出“。 在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。
1.3 栈的操作
栈的常用操作为：
弹栈，通常命名为pop压栈，通常命名为push求栈的大小判断栈是否为空获取栈顶元素的值
1.4 栈的存储结构
栈 是一种线性结构，就能够以数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。 本文我们以数组、单向链表为底层数据结构构建栈。
2. 基于数组的栈实现
当以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向：
2.1 栈的抽象数据类型
栈提供了如上所述操作的相应接口。
template<typename T>
class ArrayStack
{
public:
ArrayStack(int s =
10);
//默认的栈容量为10
~
ArrayStack();
public:
T top(); //获取栈顶元素
void push(T t);
//压栈操作
T pop();
//弹栈操作
bool isEmpty();
//判空操作
int size();
//求栈的大小
private:
int count;
//栈的元素数量
int capacity;
//栈的容量
T * array;
//底层为数组
};
栈的定义
count 为栈的元素数量，capacity为栈的容量，count<=capacity，当栈满的时候，count = capacity。本实现中不支持栈的动态扩容，栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定，默认的栈容量为10。
2.2 栈的具体实现
/*栈的判空操作*/
template <typename T>
bool ArrayStack<T>
::isEmpty()
{
return count ==
0;
//栈元素为0时为栈空
};
/*返回栈的大小*/
template <typename T>
int ArrayStack<T>
::size()
{
return count;
};
/*插入元素*/
template <typename T>
void ArrayStack<T>
::push(T t)
{
if (count != capacity)
//先判断是否栈满
{
array[count++] =
t;
}
};
/*弹栈*/
template <typename T>
T ArrayStack<T>
::pop()
{
if (count !=
0)
//先判断是否是空栈
{
return array[--
count];
}
};
/*获取栈顶元素*/
template <typename T>
T ArrayStack<T>
::top()
{
if (count !=
0)
{
return array[count -
1];
}
};
栈的操作
2.3 栈的代码测试
int main(
int argc,
char*
argv[])
{
ArrayStack <
int> p(
5);
for (
int i =
0; i <
5; i++
)
{
p.push(i);
}
cout <<
"栈的大小:"<<p.size() <<
endl;
cout <<
"栈是否为空:"<<p.isEmpty() <<
endl;
cout <<
"栈顶元素："<<p.top() <<
endl;
cout <<
"依次出栈:" <<
endl;
while (!
p.isEmpty())
{
cout << p.pop() <<
endl;
}
getchar();
return 0;
}
测试
测试结果
栈的大小:
5
栈是否为空:0 栈顶元素：4 依次出栈: 4 3 2 1 0
回到顶部
3. 基于单链表的栈
以链表为底层的数据结构时，以链表头为作为栈顶较为合适，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部；
3.1 链表节点
/*链表节点结构*/
template <typename T>
struct Node
{
Node(T t) :value(t), next(nullptr){};
Node() :next(nullptr){};
public:
T value;
Node<T>*
next;
};
栈的定义
value:栈中元素的值next:链表节点指针，指向直接后继
3.2 栈的抽象数据类型
基于链表的栈提供的接口与基于数组的栈一致。
/*栈的抽象数据结构*/
template <typename T>
class LinkStack
{
public:
LinkStack();
~
LinkStack();
public:
bool isEmpty();
int size();
void push(T t);
T pop();
T top();
private:
Node<T>*
phead;
int count;
};
栈的抽象
3.3 栈的具体实现
/*返回栈的大小*/
template <typename T>
int LinkStack<T>
::size()
{
return count;
};
/*栈的判空操作*/
template <typename T>
bool LinkStack<T>
::isEmpty()
{
return count ==
0;
};
/*插入元素*/
template<typename T>
void LinkStack<T>
::push(T t)
{
Node <T> *pnode =
new Node<T>
(t);
pnode->next = phead->
next;
phead->next =
pnode;
count++
;
};
/*弹栈*/
template <typename T>
T LinkStack<T>
::pop()
{
if (phead->next != nullptr)
//栈空判断
{
Node<T>* pdel = phead->
next;
phead->next = phead->next->
next;
T value = pdel->
value;
delete pdel;
count--
;
return value;
}
};
/*获取栈顶元素*/
template <typename T>
T LinkStack<T>
::top()
{
if (phead->next!=
nullptr)
return phead->next->
value;
};
栈的操作
3.4 栈的代码测试
int main(
int argc,
char*
argv[])
{
LinkStack <
string>
lstack;
lstack.push("hello");
lstack.push("to");
lstack.push("you！");
cout <<
"栈的大小:" << lstack.size() <<
endl;
cout <<
"栈顶元素:"<< lstack.top() <<
endl;
while (!
lstack.isEmpty())
{
lstack.pop();
}
cout <<
"栈的大小:" << lstack.size() <<
endl;
getchar();
return 0;
}
测试
测试结果：
栈的大小:
3
栈顶元素:you！
栈的大小:0
转载于:https://www.cnblogs.com/chenshikun/p/8193696.html
相关资源：数据结构—成绩单生成器
