南京做网站公司 雷仁,专门做汽车内饰的网站,提供网页制作平台的公司,能自己制作图片的app堆栈(Stack)最明显的特征就是“先进后出”#xff0c;本质上讲堆栈也是一种线性结构#xff0c;符合线性结构的基本特点#xff1a;即每个节点有且只有一个前驱节点和一个后续节点。 相对前面学习过的顺序表、链表不同的地方在于#xff1a;Stack把所有操作限制在只能…堆栈(Stack)最明显的特征就是“先进后出”本质上讲堆栈也是一种线性结构符合线性结构的基本特点即每个节点有且只有一个前驱节点和一个后续节点。 相对前面学习过的顺序表、链表不同的地方在于Stack把所有操作限制在只能在线性结构的某一端进行而不能在中间插入或删除元素。下面是示意图 从示意图中可以看出堆栈有二种实现方式基于数组的顺序堆栈实现、类似链表的链式堆栈实现 先抽象堆栈的接口IStack: namespace 栈与队列
{public interface IStackT{/// summary/// 返回堆栈的实际元素个数/// /summary/// returns/returnsint Count();/// summary/// 判断堆栈是否为空/// /summary/// returns/returnsbool IsEmpty();/// summary/// 清空堆栈里的元素/// /summaryvoid Clear();/// summary/// 入栈将元素压入堆栈中/// /summary/// param nameitem/paramvoid Push(T item);/// summary/// 出栈从堆栈顶取一个元素并从堆栈中删除/// /summary/// returns/returnsT Pop();/// summary/// 取堆栈顶部的元素(但不删除)/// /summary/// returns/returnsT Peek();}
}顺序堆栈(SeqStack)的实现 using System;
using System.Text;namespace 栈与队列
{public class SeqStackT:IStackT{private int maxsize;private T[] data;private int top; public SeqStack(int size) {data new T[size];maxsize size;top -1;}#region //接口实现部分public int Count() {return top 1;}public void Clear() {top -1;}public bool IsEmpty() {return top -1;}public void Push(T item){if (IsFull()){Console.WriteLine(Stack is full);return;}data[top] item;}public T Pop(){T tmp default(T);if (IsEmpty()){Console.WriteLine(Stack is empty);return tmp;}tmp data[top];top--;return tmp;}public T Peek(){if (IsEmpty()){Console.WriteLine(Stack is empty!);return default(T);}return data[top];}#endregionpublic bool IsFull() {return top maxsize - 1;}public override string ToString(){StringBuilder sb new StringBuilder();for (int i top;i0;i--){sb.Append(data[i] ,);}return sb.ToString().Trim(,);} }
} 链式堆栈(LinkStack)的实现 先定义节点Node.cs namespace 栈与队列
{public class NodeT{private T data;private NodeT next;public Node(T data, NodeT next) {this.data data;this.next next;}public Node(NodeT next) {this.next next;this.data default(T);}public Node(T data) {this.data data;this.next null;}public Node() {this.data default(T);this.next null;}public T Data {get { return this.data; }set { this.data value; }}public NodeT Next {get { return next; }set { next value; }}}
}下面是LinkStack.cs using System;
using System.Text;namespace 栈与队列
{public class LinkStackT:IStackT{private NodeT top;private int num;//节点个数/// summary/// 顶部节点/// /summarypublic NodeT Top {get { return top; }set { top value; }}public LinkStack() {top null;num 0;}public int Count() {return num;}public void Clear() {top null;num 0;}public bool IsEmpty() {if (top null num 0){return true;}else {return false;}}public void Push(T item) {NodeT q new NodeT(item);if (top null){top q;}else {q.Next top;top q;}num;}public T Pop() {if (IsEmpty()) {Console.WriteLine(Stack is empty!);return default(T);}NodeT p top;top top.Next;num--;return p.Data;}public T Peek() {if (IsEmpty()) {Console.WriteLine(Stack is empty!);return default(T);}return top.Data;}public override string ToString(){StringBuilder sb new StringBuilder();if (top ! null) {sb.Append(top.Data.ToString() ,);NodeT p top;while (p.Next ! null){ sb.Append(p.Next.Data.ToString() ,);p p.Next;}}return sb.ToString();}}
}测试代码片段 Console.WriteLine(顺序堆栈测试开始...);SeqStackint seqStack new SeqStackint(10);seqStack.Push(1);seqStack.Push(2);seqStack.Push(3);Console.WriteLine(seqStack);Console.WriteLine(seqStack.Peek());Console.WriteLine(seqStack);Console.WriteLine(seqStack.Pop());Console.WriteLine(seqStack);Console.WriteLine(链堆栈测试开始...);LinkStackint linkStack new LinkStackint();linkStack.Push(1);linkStack.Push(2);linkStack.Push(3);Console.WriteLine(linkStack);Console.WriteLine(linkStack.Peek());Console.WriteLine(linkStack);Console.WriteLine(linkStack.Pop());Console.WriteLine(linkStack);Console.ReadLine();.Net中System.Collections.Generic.StackT已经提供了堆栈的基本实现明白原理后仍然推荐大家使用内置的实现。转载于:https://www.cnblogs.com/yjmyzz/archive/2010/10/30/1865212.html
