堆栈(Stack)是一种特殊的线性表，是一种操作只允许在尾端进行插入或删除等操作的线性表。表尾允许进行插入删除操作，称为栈顶(Top)，另一端是固定的，称为栈底(Bottom).栈的操作使按照先进后出或后进先出的原则进行的。
用一片连续的存储空间来存储栈中的数据元素，称为顺序栈(Sequence Stack)。类似于顺序表，用一维数组来存放栈中的数据元素。缺点：浪费存储空间。
用链式存储结构来存储的栈为链栈(Linked Stack).链栈通常用单链表来表示。
Stack using System;
using System.Collections.Generic;
using System.Linq;
using System.Text; namespace DataStructure
{ interface IStack<T>
{
void Push(T item); //入栈操作
T Pop(); //出栈操作
T GetTop(); //取栈顶元素
int GetLength(); //求栈的长度
bool IsEmpty(); //判断栈是否为空
void Clear(); //清空操作
}
/// <summary>
/// 顺序栈
/// </summary>
/// <typeparam name="T"></typeparam>
class SequenceStack<T> : IStack<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 SequenceStack(int size)
{
data = new T[size];
maxsize = size;
top = -;
} //求栈的长度
public int GetLength()
{
return top + ;
}
//清空顺序栈
public void Clear()
{
top = -;
}
//判断顺序栈是否为空
public bool IsEmpty()
{
if (top == -)
{
return true;
}
else
return false;
}
//判断栈是否为满
public bool IsFull()
{
if (top == maxsize - )
{
return true;
}
else
return false;
} //入栈
public void Push(T elem)
{
if (IsFull())
{
Console.WriteLine("Stack is Full ！");
return;
}
data[++top] = elem; } //出栈
public T Pop()
{
T tem = default(T);
if (IsEmpty())
{
Console.WriteLine("Stack is Empty !");
return default(T);
}
tem = data[top];
--top;
return tem;
} //获取栈顶元素
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is Empty !");
return default(T);
}
return data[top];
} } /// <summary>
/// 用顺序栈解决火车车厢重排问题
/// </summary>
class TrainArrangwBySeqStack
{
//车厢重排算法，K个缓冲铁轨，车厢初始排序存放在P中
public bool RailRoad(int[] p, int n, int k)
{
//创建与缓冲铁轨对应的堆栈
SequenceStack<int>[] H;
H = new SequenceStack<int>[k + ];
for (int i = ; i <= k; i++)
H[i] = new SequenceStack<int>(p.Length);
int NowOut = ; //下次要输出的车厢
int minH = n + ; //缓冲铁轨中编号最小的车厢
int minS = ; //minH号车厢对应的缓冲铁轨 //车厢重排
for (int i = ; i < n; i++)
{
if (p[i] == NowOut)
{
Console.WriteLine("Move car {0} from input to output", p[i]);
NowOut++;
//从缓冲铁轨中输出
while (minH == NowOut)
{
Output(ref minH, ref minS, ref H, k, n);
NowOut++;
}
}
else
{
if (!Hold(p[i], ref minH, ref minS, ref H, k, n))
{
return false;
}
}
}
return true;
} //在一个缓冲区中放入车厢C
public bool Hold(int c, ref int minH, ref int minS, ref SequenceStack<int>[] H, int k, int n)
{
//如果没有可用的缓冲铁轨，则返回false
//否则返回true
//为车厢c寻找最优的铁轨
//初始化 int BestTrack = ; //目前最优的铁轨
int BestTop = n + ; //最优铁轨上的头辆车厢
int x; //车厢索引 //扫描缓冲铁轨
for (int i = ; i <= k; i++)//！！！i=1
{
if (!H[i].IsEmpty())
{
//铁轨i不为空
x = H[i][H[i].Top];
if (c < x && x < BestTop)
{
//铁轨i顶部的车厢编号最小
BestTop = x;
BestTrack = i;
}
}
else//铁轨i为空
{
if (BestTrack == )
{
BestTrack = i;
}
break;
}
}
if (BestTrack == )
return false;//没有可用铁轨 //把车厢c送入缓冲铁轨
H[BestTrack].Push(c);
Console.WriteLine("Move car{0} from input to holding track {1}", c, BestTrack);
//必要时修改minH minS
if (c < minH)
{
minH = c;
minS = BestTrack;
}
return true;
} //把车厢从缓冲区铁轨送至出轨处，同时修改minH minS
public void Output(ref int minH, ref int minS, ref SequenceStack<int>[] H, int k, int n)
{
int c;//车厢索引
//从堆栈minS中删除编写、好最小的车厢minH
c = H[minS].Pop();
Console.WriteLine("Move car{0} from holding track {1} to output", minH, minS);
//通过检查所有的栈顶，搜索新的minH minS
minH = n + ;
for (int i = ; i <= k; i++)
{
if (!H[i].IsEmpty() && (c = H[i][H[i].Top]) < minH)
{
minH = c;
minS = i;
}
}
}
} /// <summary>
/// 链栈结点
/// </summary>
class StackNode<T>
{
private T data; //数据域
private StackNode<T> next; //引用域 public StackNode()
{
data = default(T);
next = null;
} public StackNode(T val)
{
data = val;
next = null;
} public StackNode(T val, StackNode<T> p)
{
data = val;
next = p;
} //数据域属性
public T Data
{
get { return data; }
set { data = value; }
} //引用域属性
public StackNode<T> Next
{
get { return next; }
set { next = value; }
} } /// <summary>
/// 链栈
/// </summary>
/// <typeparam name="T"></typeparam>
class LinkStack<T> : IStack<T>
{
private StackNode<T> top; //栈顶指示器
private int size; //栈中元素的个数 //栈顶指示器属性
public StackNode<T> Top
{
get { return top; }
set { top = value; }
} //元素个数属性
public int Size
{
get { return size; }
set { size = value; }
} public LinkStack()
{
top = null;
size = ;
} //判断链栈是否为空
public bool IsEmpty()
{
if ((top == null) && (size == ))
return true;
else
return false;
} public int GetLength()
{
return size;
} public void Clear()
{
top = null;
size = ;
} //入栈操作
//在单链表的起始处插入一个结点
public void Push(T item)
{
StackNode<T> q = new StackNode<T>(item);
if (top == null)
{
top = q;
}
else
{
//将新结点的next指向栈顶指示器top所指向的结点
q.Next = top;
//将栈顶指示器top指向新结点
top = q;
}
++size;
} //出栈操作
public T Pop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty !");
return default(T);
}
StackNode<T> p = top;
top = top.Next;
--size;
return p.Data;
} //获取栈顶结点的值
public T GetTop()
{
if (IsEmpty())
{
Console.WriteLine("Stack is empty !");
return default(T);
}
return top.Data;
}
} /// <summary>
/// 用链栈解决火车车厢重排问题
/// </summary>
class TrainArrangeByLinkStack
{
//k个缓冲铁轨，车厢初始排序存储在p中
public bool RailRoad(int[] p, int n, int k)
{
//创建与缓冲铁轨对应的堆栈
LinkStack<int>[] H;
H = new LinkStack<int>[k + ];
for (int i = ; i <= k; i++)
{
H[i] = new LinkStack<int>();
} int NowOut = ; //下一次要输出的车厢
int minH = n + ; //缓冲铁轨中编号最小的车厢
int minS = ; //minH号车厢对应的缓冲铁轨 //车厢重排
for (int i = ; i < n; i++)
{
if (p[i] == NowOut)
{
Console.WriteLine("Move car {0} from input to output", p[i]);
NowOut++; //从缓冲铁轨中输出
while (minH == NowOut)
{
Output(ref minH, ref minS, ref H, k, n);
NowOut++;
}
}
else
{
//将p[i]送入缓冲铁轨
if (!Hold(p[i], ref minH, ref minS, ref H, k, n))
return false;
}
}
return true;
} //在一个缓冲铁轨中放入车厢c
public bool Hold(int c, ref int minH, ref int minS, ref LinkStack<int>[] H, int k, int n)
{
//如果没有可用缓冲铁轨，则返回false
//否则返回true
//为车厢c寻找最优的缓冲铁轨
//初始化
int BestTrack = ; //目前最优的铁轨
int BestTop = n + ; //最优铁轨上的头辆车厢
int x; //车厢索引 //扫描缓冲铁轨
for (int i = ; i <= k; i++)
{
if (!H[i].IsEmpty())
{
//铁轨不为空
x = H[i].Top.Data;
if (c < x && x < BestTop)
{
BestTop = x;
BestTrack = i;
}
}
else
{
if (BestTrack == )
BestTrack = i;
break;
}
}
if (BestTrack == )
return false;//没有可用铁轨
//把车厢c送入缓冲铁轨
H[BestTrack].Push(c);
Console.WriteLine("Move car {0} from input to holding track {1}", c, BestTrack); if (c < minH)
{
minH = c;
minS = BestTrack;
}
return true;
} //把车厢从缓冲铁轨送至出轨处，同时修改minH minS
public void Output(ref int minH,ref int minS ,ref LinkStack <int>[] H,int k,int n)
{
int c; //车厢索引
c = H[minS].Pop();
Console.WriteLine("Move car {0} form holding track {1} to output", minH, minS);
//通过检查所有的栈顶，搜索新的minH和minS
minH = n + ;
for (int i = ; i <= k; i++)
{
if (!H[i].IsEmpty() && (c = H[i].Top.Data) < minH)
{
minH = c;
minS = i;
}
}
}
} class Stack
{ static void Main()
{
int[] p = new int[] { , , , , , , , , };
int k = ; //用顺序栈解决火车车厢重排问题
TrainArrangwBySeqStack tas = new TrainArrangwBySeqStack();
bool results;
results = tas.RailRoad(p, p.Length, k);
do
{
if (results == false)
{
Console.WriteLine("need more holding track, please enter additional number:");
k = k + Convert.ToInt32(Console.ReadLine());
results = tas.RailRoad(p, p.Length, k);
}
} while (results == false);
Console.ReadLine(); //用链栈解决火车车厢重排问题
TrainArrangeByLinkStack ta = new TrainArrangeByLinkStack();
bool result;
result = ta.RailRoad(p, p.Length, k);
do
{
if (result == false)
{
Console.WriteLine("need more holding track,please enter additional number:");
k = k + Convert.ToInt32(Console.ReadLine());
result = ta.RailRoad(p, p.Length, k);
}
} while (result == false);
Console.ReadLine();
}
}
}