XIAOSUO 记录个人学习的足迹

一、概述

　　LIFO: Last In, First Out（后进先出）
　　受限的线性表，它插入和删除只能在表的一端进行
　　所有插入和删除操作都只能在表的一端进行，这一端叫栈顶。
　　最后进入栈中的数据最先被拿走。

二、栈的操作

1.初始化栈：

　　产生一个新的空栈。

2.入栈操作Push(T item)：

　　将指定类型元素data进到栈中。

3.出栈操作Pop()：

　　将栈中的栈顶元素取出来，并在栈中删除栈顶元素。

4.取栈顶元素GetTop()：

　　将栈中的顶元素取出来，栈中元素不变。

5.判断栈空IsEmpty()：

　　若栈为空，返回true，否则返回false。

6.清空操作Clear()：

　　从栈中清除所有的数据元素。

三、栈的顺序表示和实现

　　用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈。类似与顺序表，用一维数组来存放顺序栈中的数据元素。栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1。

　　基本运算在顺序栈上的实现如下：

public class SeqStack<T>
{
	private int maxsize;    //顺序栈的容量
	private T[] data;       //数组，用于存储顺序栈中的数据元素
	private int top;        //指示顺序栈的栈顶

	//索引器
	public T 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 SeqStack(int size)
	{
		data = new T[size];
		maxsize = size;
		top = -1;
	}

	public void Push(T elem)
	{
		if (IsFull())
		{
			throw new Exception("容量已满，不能再添加了");
		}
		data[++top] = elem;
	}

	public T Pop()
	{
		T tmp = default(T);
		if (IsEmpty())
		{
			return tmp;
		}
		tmp = data[top];
		--top;
		return tmp;
	}

	public T GetTop()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		return data[top];
	}

	public int GetLength()
	{
		return top + 1;
	}

	public void Clear()
	{
		top = -1;
	}

	public bool IsEmpty()
	{
		if (top == -1)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

	private bool IsFull()
	{
		if (top == maxsize - 1)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

四、栈的链式表示和实现

用链式存储结构存储的栈称为链栈。链栈通常用单链表来表示，它的实现是单链表的简化。所以，链栈结点的结构与单链表结点的结构一样。由于链栈的操作只是在一端进去，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。

　　基本运算在链栈上的实现如下：

public class LinkStack<T>
{
	private Node<T> top;    //栈顶指示器
	private int size;       //栈中结点的个数

	public Node<T> Top
	{
		get
		{
			return top;
		}
		set
		{
			top = value;
		}
	}

	public int Size
	{
		get
		{
			return size;
		}
		set
		{
			size = value;
		}
	}

	public LinkStack()
	{
		top = null;
		size = 0;
	}
   
	public void Push(T item)
	{
		Node<T> q = new Node<T>(item);
		if (top == null)
		{
			top = q;
		}
		else
		{
			q.Next = top;
			top = q;
		}
		++size;
	}
   
	public T Pop()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		Node<T> p = top;
		top = top.Next;
		--size;
		return p.Data;
	}

	public T GetTop()
	{
		if (IsEmpty())
		{
			return default(T);
		}
		return top.Data;
	}
 
	public int GetLength()
	{
		return size;
	}
  
	public void Clear()
	{
		top = null;
		size = 0;
	}
 
	public bool IsEmpty()
	{
		if ((top == null) && (size == 0))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}