栈(Stack)是限定在表尾端进行插入或删除操作的线性表。因此,表尾具有特殊的含义,称之为栈顶(Top),另一端是固定的,称为栈底(Bottom)。不含任何数据元素的栈为空栈(Empty Stack)。
栈通常记为:S= (a1,a2,…,an),S是英文单词stack的第1个字母。栈中元素按a1,a2,a3,...,an的次序进栈,出栈的次序为栈顶元素。即出栈的次序与进栈相反,an第一个出栈,a1最后一个出栈。所以,栈的操作是按照后进先出(Last In First Out,简称LIFO)或先进后出(First In Last Out,简称FILO)的原则进行的,因此,栈又称为LIFO表或FILO表。
对于栈来说,主要的操作有:
1、构造空栈
2、清空栈:ClearStack()
3、求栈长(获得栈中元素的个数):StackLength()
4、返回栈顶元素:GetTop()
5、压栈操作:Push(object e)
6、弹栈操作(出栈操作):Pop()
7、判断栈是否为空:IsEmpty()
8、判断栈是否已满:IsFull()
using System;
class Stack
{
int maxsize; //顺序栈的容量
object[] data; //数组,用于存储栈中的数据
int top; //指示栈顶
public object this[int index]
{
get{return data[index];}
set{ data[index] = value;}
}
//栈容量属性
public int Maxsize
{
get{return maxsize;}
set{maxsize = value;}
}
//获得栈顶的属性
public int Top
{
get{return top;}
}
//使用构造器初始化栈
public Stack(int size)
{
data = new object[size];
maxsize = size;
top = -1;
}
//求栈的长度(栈中的元素个数)
public int StackLength()
{
return top+1;
}
//清空顺序栈
public void ClearStack()
{
top = -1;
}
//判断顺序栈是否为空
public bool IsEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
//判断顺序栈是否为满
public bool IsFull()
{
if (top == maxsize-1)
{
return true;
}
else
{
return false;
}
}
//入栈操作
public void Push(object e)
{
if(IsFull())
{
Console.WriteLine("栈已满!");
return;
}
data[++top] = e;
}
//出栈操作,并返回出栈的元素
public object Pop()
{
object temp = null;
if (IsEmpty())
{
Console.WriteLine("栈为空!");
return temp;
}
temp = data[top];
top --;
return temp;
}
//获取栈顶数据元素
public object GetTop()
{
if (IsEmpty())
{
Console.WriteLine("栈为空!");
return null;
}
return data[top];
}
}
//定义测试类
class Test
{
static void Main()
{
Stack s = new Stack(10);
Random r = new Random(); //随机生成数据
int mid;
for(int i = 0;i<10;i++)
{
mid = (int)r.Next(10,100); //获取10~100之间的整型数据
s.Push(mid); //将数据压栈
Console.WriteLine("将数据{0}压栈,现在栈中元素数为:{1}",
mid,s.StackLength());
}
Console.WriteLine("/n准备将数据元素888压栈:");
s.Push(888);
Console.WriteLine("栈中元素个数为:{0}",s.StackLength());
Console.WriteLine();
for(int j = 0;j<10;j++) //循环出栈
{
Console.WriteLine("将数据{0}弹栈,现在栈中元素数为:{1}",
s.Pop(),s.StackLength());
}
}
}
运行结果如下:
新闻热点
疑难解答