栈的介绍
栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。
栈是一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 栈也称为后进先出表(LIFO表)。栈可以用来在函数调用的时候存储断点,做递归时要用到栈!
栈的特性:只在表的一端访问元素的表,其元素只能从栈顶端增加或删除。设计存放那些只能从一端访问的元素。
增加(压入push):栈顶增加元素
删除(弹出pop):栈顶删除元素
后进先出原则(LIFO)
栈满:栈已达到处理元素个数的最大值。 栈空:无法从栈中删除元素。
代码示例:
1、SeqStack.h文件
#define MAXSIZE 0xFFFF
template<class type>
class SeqStack
{
int top; //栈顶指示
type *stacka; //数组名
int maxsize; //栈最大可容纳元素个数
public:
SeqStack();
SeqStack(int size);
SeqStack(type data[], int size);
virtual ~SeqStack()
{
delete[]stacka;
}
void Push(const type &item); //元素item压栈
type Pop(); //数据元素出栈,返回之
type GetTop(); //读栈顶数据元素并返回
int Empty()const
{
return top == -1; //判断栈是否为空
}
int Full()const
{
return top == maxsize - 1; //判断栈是否为满
}
void Clear()
{
top = -1; //清空栈
}
};
template<class type>
SeqStack<type>::SeqStack():top(-1), maxsize(MAXSIZE)
{
stacka = new type[maxsize];
if (stacka == NULL){
cerr << "动态存储分配失败!" << endl;
exit(1);
}
}
template<class type>
SeqStack<type>::SeqStack(int size) :
top(-1), maxsize(size)
{
stacka = new type[maxsize]; //创建存储栈的数组
if (stacka == NULL){ //分配不成功
cerr << "动态存储分配失败!" << endl;
exit(1);
}
}
template<class type>
SeqStack<type>::SeqStack(type data[], int size) :
top(-1), maxsize(size)
{
stacka = new type[maxsize]; //创建存储栈的数组
if (stacka == NULL){ //分配不成功
cerr << "动态存储分配失败!" << endl;
exit(1);
}
for (int i = 0; i<maxsize; i++){
stacka[i] = data[i];
}
top += maxsize;
}
template<class type>
void SeqStack<type>::Push(const type& item)
{
//若栈已满,出错处理;否则把元素item压栈
if (Full()){
cerr << "栈已满,不能压栈!" << endl;
exit(1);
}
//这里我们采用指针先移动,然后再对元素进行操作的方式
top++;
stacka[top] = item;
}
template<class type>
type SeqStack<type>::Pop()
{
if (Empty()){
cerr << "栈已空!" << endl;
exit(1);
}
//栈不空,取栈顶元素
type data = stacka[top];
top--;
//返回栈顶元素
return data;
}
template<class type>
type SeqStack<type>::GetTop()
{
//若栈不空,返回栈顶元素的值
if (Empty()){
cerr << "栈空!" << endl;
exit(1);
}
//返回栈顶元素的值
return stacka[top];
}
2、main.c文件
#include <iostream>
#include "SeqStack.h"
using namespace std;
int main()
{
int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
SeqStack<int> stack(data, 10);
while (!stack.Empty()){
cout << stack.Pop() << " ";
}
cout << endl;
system("pause");
return 0;
}
3、代码运行结果
分析:程序如实实现了栈的创建,插入,删除等操作,代码中通过使用类模板,实现了面向对象编程的思想。
Next:数据结构(Data Structure)——2、队列(Queue)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)