本篇，我们将会复习一下基于线性表衍生出的两种数据结构 —— 栈和队列。
栈(Stack)
在软件应用中，栈这种后进先出的数据结构的应用是非常普遍的。比如浏览器的前进后退、Word 和 PhotoShop 等编辑软件中的撤销操作，以及在 iOS 开发中的 push、pop controller 操作都是栈的应用。
栈本质是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。
栈又称为后进先出的线性表，简称为 LIFO 结构。
理解栈我们要注意:
- 他是一个线性表
- 仅允许在表尾进行插入和删除操作，这里的表尾是指栈顶
栈的插入操作，叫做进栈(push)，也称为压栈、入栈。
栈的删除操作，叫做出栈(pop)，也称为弹栈。
栈的顺序存储结构
栈的顺序存储结构简称为顺序栈。
public class SqStack<T>
{
public const int Maxsize = 20;
public T[] Data = new T[Maxsize];
public int Top = -1;
public Status Push(T t)
{
if (Top >= Maxsize)
{
return Status.Error;
}
Top++;
Data[Top] = t;
return Status.Ok;
}
public Status Pop(out T t)
{
if (Top == -1)
{
t = default(T);
return Status.Error;
}
t = Data[Top];
Top--;
return Status.Ok;
}
}
|
栈的链式存储结构
栈的链式存储结构简称为链栈。
对于链栈来说，是不需要头节点的。
class LinkStack<T>
{
public StackNode<T> Top;
public int Count;
public Status Push(T t)
{
var stackNode = new StackNode<T>(t) {NextNode = Top};
Top = stackNode;
Count++;
return Status.Ok;
}
public Status Pop(out T t)
{
if (Top == null)
{
t = default(T);
return Status.Error;
}
t = Top.Element;
Top = Top.NextNode;
Count--;
return Status.Ok;
}
}
|
栈的应用
递归
我们把一个直接调用自己或者通过一系列调用语句间接地调用自己的函数，称为递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不在引用自身而是返回值退出。
递归回退的顺序是他前进顺序的逆序。显然符合栈这种数据结构。因此编译器使用栈来实现递归。
四则运算表达式求值
一种不需要括号的后缀表示法，也称为逆波兰表示(RPN)。是一种非常巧妙的将四则运算由常见的中缀表达式变为后缀表达式来简化运算复杂性。基本原理也是栈。这里就不详细说明了。
队列(Queue)
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表，简称为 FIFO 结构。
允许插入操作的一端称为队尾，允许删除操作的一端称为队头。
队列在程序设计中使用非常频繁，如消息队列(MQ)所使用的数据结构等。
队列的顺序存储结构
如果我们只把队列当成普通的线性表操作也完全没有问题，入队操作时间复杂度为 O(1)，但是出队操作时间复杂度为 O(n)，为解决这个问题，我们可以使用循环队列。
我们把队列的这种头尾相接的顺序存储结构称为循环队列。
为了实现循环队列，我们需要引入两个变量，一个指向队头元素所在位置，一个指向队尾元素的下一个位置。
class SqQueue<T>
{
public const int Maxsize = 20;
public T[] Data = new T[Maxsize];
private int _front;
private int _rear;
public Status EnQueue(T t)
{
if ((_rear + 1) % Maxsize == _front)
{
return Status.Error;
}
Data[_rear] = t;
_rear = (_rear + 1) % Maxsize;
return Status.Ok;
}
public Status DeQueue(out T t)
{
if (_rear == _front)
{
t = default(T);
return Status.Error;
}
t = Data[_front];
_front = (_front + 1) % Maxsize;
return Status.Ok;
}
}
|
队列的链式存储结构
class QueueNode<T>
{
public T Element;
public QueueNode<T> NextNode;
public QueueNode(T t)
{
Element = t;
}
}
class LinkQueue<T>
{
public QueueNode<T> Front, Rear;
public Status EnQueue(T t)
{
var node = new QueueNode<T>(t);
Front.NextNode = node;
Rear = node;
return Status.Ok;
}
public Status DeQueue(out T t)
{
if (Front == Rear)
{
t = default(T);
return Status.Error;
}
t = Front.Element;
Front = Front.NextNode;
return Status.Ok;
}
}
|