栈
简介
栈（Stack），又称堆栈，是只允许在一端进行插入和删除的线性表，即栈是受限线性表。允许插入和删除的一端称为栈顶（Top），不允许插入和删除的一端称为栈底（Bottom），栈底是固定的。栈的操作特点是后进先出LIFO（Last In First Out），故又称后进先出的线性表。空栈是不含任何元素的栈。
往栈中添加元素称为进栈（Push），删除元素称为出栈（Pop）。栈根据存储结构分为顺序栈（顺序存储）和链栈（链式存储）。上图为顺序栈，进栈和出栈的时间复杂度都是O(1)。如上图，五个元素进栈的顺序为a1a2a3a4a5，但依次出栈的顺序相反为a5a4a3a2a1。因为栈的操作特性为LIFO，所以在a5没出栈之前，a4是不能越过a5提前出栈的，其他元素同理。
应用场景
1、游戏UI界面可以采用栈来存取，弹出UI页面称为出栈，关闭UI界面称为进栈。
2、C#中的值类型存储在栈中，访问速度快，由C#系统本身负责值类型内存空间的分配和释放。
3、栈可以用于括号匹配，将括号依次压入栈中，直到最近入栈的括号配对后，再依次配对其他括号。
4、程序语言编译器中的表达式求值问题是栈的典型应用。
5、递归中也大量使用了栈。
存储结构
由于栈是受限的线性表，因此栈可以采用顺序存储和链式存储两种方式。采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链栈。不同的存储结构就会有不同的操作特点。
基本操作
C#内置了栈类型Stack，位于System.Collections命名空间下，该栈元素为Object类型，以下是基本操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
using System;
using System.Collections;
namespace StackExample
{
class Client
{
public static void Main(string[] args)
{
// 新建一个栈
Stack s = new Stack();
// 1进栈
s.Push(1);
// “ok”进栈
s.Push("ok");
// Pop()弹出并返回栈顶元素
Console.WriteLine(s.Pop());
// 栈中的Peek()只返回，不弹出栈顶元素
Console.WriteLine(s.Peek());
// 获取栈的大小
Console.WriteLine(s.Count);
// 清空栈
s.Clear();
}
}
}
|
栈的实现
栈可以借助数组或链表实现，数组实现的栈称为顺序栈，而链表实现的栈称为链栈。下面是顺序栈的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
using System;
namespace Stack
{
class Stack<T>
{
// 初始栈容量
private int size = 10;
private T[] contents;
// 栈顶指针
private int top;
// 栈的构造函数
public Stack()
{
contents = new T[size];
top = -1;
}
// 判空
public bool isEmpty()
{
if (top == -1)
{
return true;
}
return false;
}
// 入栈时，栈顶指针top先加1，再添加元素
public void Push(T o)
{
// 栈满时不能入栈
if (top == size - 1)
{
throw new Exception("stack is full.");
}
contents[++top] = o;
}
// 出栈时，先删除元素，栈顶指针top再减一
public T Pop()
{
// 栈空时不能出栈
if (top == -1)
{
throw new Exception("stack is empty.");
}
return contents[top--];
}
// 获取栈元素个数
public int GetSize()
{
return top + 1;
}
}
class Client
{
public static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
stack.Push(1);
Console.WriteLine(stack.Pop());
}
}
}
// 输出结果：1
|
队列
简介
队列（Queue），简称队，只允许在一端插入元素，而在另一端删除元素，也是受限线性表。允许删除元素的一端称为队头（Front），又称队首。而允许插入元素的一端称为队尾（Rear）。队列的操作特点是先进先出FIFO（First In First Out），故又称先进先出的线性表。这和我们日常生活中排队的情况一样，先到先得，先排先走。空队列是不含任何元素的队列。
在队列中，插入元素称为入队（Enqueue），删除元素称为出队（Dequeue）。入队和出队的时间复杂度都是O(1)。如上图，五个元素的入队顺序为a1a2a3a4a5，由于队列的操作特点是先进先出，所以出队的顺序也是a1a2a3a4a5。
应用场景
1、层次遍历需要用到队列，比如二叉树的层序遍历，依次从上往下和从左到右将树中节点入队，出队顺序不变。
2、在计算机主机和外设的数据传输中，主机数据的输出速度远高于外设处理数据的速度，直接把数据传输给外设是不行的，这样外设处理不够来导致数据堆积。因此要在主机和外设之间设置一个缓冲区，主机将输出的数据写入缓冲区，写满就停止输出，直到外设依次将缓冲区的数据处理完，主机再输出数据到缓冲区。由此可见，缓冲区存储的数据就是一个队列。
3、CPU资源请求中也用到了队列，当有多个程序请求资源时，可以按顺序依次为每个程序分配资源，先到先得。
存储结构
由于队列也是受限的线性表，因此队列也可以采用顺序存储和链式存储两种方式。采用顺序存储结构的队列称为顺序队列，采用链式存储结构的队列称为链队。不同的存储结构就会有不同的操作特点。
基本操作
C#内置了队列类型Queue，位于System.Collections命名空间下，该队列元素为Object类型，以下是基本操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
using System;
using System.Collections;
namespace QueueExample
{
class Client
{
public static void Main(string[] args)
{
// 新建一个队列
Queue q = new Queue();
// 1进队
q.Enqueue(1);
// "ok"进队
q.Enqueue("ok");
// Dequeue()移除并返回队首元素
Console.WriteLine(q.Dequeue());
// 队列中Peek()只返回，不移除队首元素
Console.WriteLine(q.Peek());
// 获取队列的大小
Console.WriteLine(q.Count);
// 清空队列
q.Clear();
}
}
}
|
循环队列的实现
当顺序队列尾部没有多余的空间时，且队列还没有满时，如果还需要添加元素，则需要移动之前的元素为之后新添加的元素预留空间，而元素移动又需要额外的代价。因此，顺序队列不适合实际开发中使用。虽然链队可以动态申请内存单元，因而没有内存空间的限制，但是链队过长会导致过多的元素（请求）排队，从而使元素（请求）处理的时间过长。因此，在一些响应时间比较敏感的系统，比如基于链队实现的线程池是不合适的。因为，链队没有内存空间限制，过多的请求排队会造成程序响应时间过长，降低系统运行效率。因此，循环队列应运而生！
将顺序队列看成一个环，即一个环状顺序队列，就是循环队列。循环队列出队入队时，队头指针和队尾指针都按顺时针方向加1。循环队列最关键的是队空队满的条件是什么？通常，牺牲一个单元来区分队空和队满，即入队时少用一个队列单元，约定“当队尾指针rear的下一位置是队头指针front时就表示队满”。因此，循环队列的队满条件为：(Q.rear+1)%MaxSize == Q.front，而队空的条件为：Q.front == Q.rear，队列中的元素个数为：(Q.rear-Q.front+MaxSize)%MaxSize。下面是代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
using System;
namespace CircleQueue
{
class CircleQueue<T>
{
// 循环队列初始容量
private int size = 10;
private T[] contents;
// 队头指针
private int front;
// 队尾指针
private int rear;
// 构造函数
public CircleQueue()
{
contents = new T[size];
// 初始化时队头队尾指针都指向0
front = rear = 0;
}
// 判空
public bool IsEmpty()
{
if (rear == front)
{
return true;
}
return false;
}
// 入队，从队尾入，先赋值再让rear加1
public void EnQueue(T o)
{
if ((rear + 1) % size == front)
{
throw new Exception("CircleQueue is full.");
}
contents[rear] = o;
rear = (rear + 1) % size;
}
// 出队，从队头出，先取值再让front加1
public T DeQueue()
{
if (rear == front)
{
throw new Exception("CircleQueue is empty.");
}
T temp = contents[front];
front = (front + 1) % size;
return temp;
}
}
class Client
{
public static void Main(string[] args)
{
CircleQueue<int> cq = new CircleQueue<int>();
cq.EnQueue(1);
cq.EnQueue(2);
Console.WriteLine(cq.DeQueue());
Console.WriteLine(cq.DeQueue());
}
}
}
// 输出结果：1，2
|
Author
Neo
LastMod
2019-07-20
License
Crative Commons 4.0