数据结构(C#语言版)——堆栈和队列
终极管理员 知识笔记 31阅读
堆栈和队列是计算机中两种常用的数据结构，它们是线性表，操作有限。栈的插入和删除是在栈顶进行的，栈顶是一个先入后出的线性表，队列的删除、搜索等操作是在队列头进行的，而插入操作是在队列尾进行的。它是一个先进先出的线性表。和线性表一样，栈和队列有两种方式：顺序存储和链式存储。
栈
13360公共接口I stackt {2://summary ://获取堆栈的长度。e:无；行高： 12pt；font-family: '快递新'快递，等宽；背景色： rgba(244，244，244，1)；text-align : left ' 4:////summary 5: int Count { get；} 6: 7://summary 8://清空堆栈。 : rgba(255, 255, 255, 1); text-align: left'> 9: /// </summary>10: void Clear();
11:
12: /// <summary>
13: /// 将一个数据压入栈
14: /// </summary>
15: /// <param name="value"></param>
16: void Push(T value);
17:
18: /// <summary>
19: /// 将一个数据弹出栈
20: /// </summary>
21: /// <returns></returns>
22: T Pop();
23:
24: /// <summary>
25: /// 获取栈顶部的数据，但不弹出
26: /// </summary>
27: /// <returns></returns>
28: T Peek();
29: }
顺序栈
1: public class SequenceStack<T> : IStack<T> {
2: private const int Step = 16;
3: private int _capacity;
4: private int _top = -1;
5: private T[] _datas;
6:
7: public SequenceStack() : this(Step) {}
8:
9: public SequenceStack(int capacity) {
10: this._capacity = capacity;
11: this._datas = new T[this._capacity];
12: }
13:
14: public int Count {
15: get { return this._top + 1; }
16: }
17:
18: public void Clear() {
19: this._top = -1;
20: }
21:
22: public void Push(T value) {
23: if(this._top+1>=this._datas.Length) {
24: this._capacity += Step;
25: T[] temps = new T[this._capacity];
26: for(int i = 0; i < this._datas.Length; i++) {
27: temps[i] = this._datas[i];
28: }
29: this._datas = temps;
30: }
31: this._datas[++this._top] = value;
32: }
33:
34: public T Pop() {
35: return this._datas[this._top--];
36: }
37:
38: public T Peek() {
39: return this._datas[this._top];
40: }
41: }
链栈
1: public class StackNode<T> {
2: private StackNode<T> _next;
3: private T _value;
4:
5: public StackNode() : this(default(T), null) {
6: }
7:
8: public StackNode(T value) : this(value, null) {
9: }
10:
11: public StackNode(T value, StackNode<T> next) {
12: this._value = value;
13: this._next = next;
14: }
15:
16: public StackNode<T> Next {
17: get { return this._next; }
18: set { this._next = value; }
19: }
20:
21: public T Value {
22: get { return this._value; }
23: set { this._value = value; }
24: }
25: }
1: public class LinkStack<T> : IStack<T> {
2: private int _count = 0;
3: StackNode<T> _top;
4:
5: public int Count {
6: get { return this._count; }
7: }
8:
9: public void Clear() {
10: this._top = null;
11: this._count = 0;
12: }
13:
14: public void Push(T value) {
15: this._top=new StackNode<T>(value, this._top);
16: this._count++;
17: }
18:
19: public T Pop() {
20: T result = this._top.Value;
21: this._top = this._top.Next;
22: this._count--;
23: return result;
24: }
25:
26: public T Peek() {
27: return this._top.Value;
28: }
29: }
队列
1: public interface IQueue<T> {
2: /// <summary>
3: /// 获取队列的长度
4: /// </summary>
5: int Count { get; }
6:
7: /// <summary>
8: /// 清空队列
9: /// </summary>
10: void Clear();
11:
12: /// <summary>
13: /// 一个数据进入队列
14: /// </summary>
15: /// <param name="value"></param>
16: void Add(T value);
17:
18: /// <summary>
19: /// 一个数据弹出队列
20: /// </summary>
21: /// <returns></returns>
22: T Dequeue();
23:
24: /// <summary>
25: /// 获取最前面的数据，但不出队列
26: /// </summary>
27: /// <returns></returns>
28: T Peek();
29: }
顺序队列
1: public class SequenceQueue<T> : IQueue<T> {
2: private const int Step = 16;
3: private int _capacity;
4: private int _front = -1;
5: private int _rear = -1;
6: private T[] _datas;
7:
8: public SequenceQueue() : this(Step) { }
9:
10: public SequenceQueue(int capacity) {
11: this._capacity = capacity;
12: this._datas = new T[this._capacity];
13: }
14:
15: public int Count {
16: get {
17: if(this._front==-1 && this._rear==-1) {
18: return 0;
19: }
20: if(this._front <= this._rear) {
21: return this._rear - this._front + 1;
22: }
23: return this._datas.Length - this._front + this._rear + 1;
24: }
25: }
26:
27: public void Clear() {
28: this._front = -1;
29: this._rear = -1;
30: }
31:
32: public void Add(T value) {
33: if(this.Count==this._datas.Length) {
34: this._capacity += Step;
35: T[] temps = new T[this._capacity];
36: for(int i = 0; i < this._datas.Length; i++) {
37: temps[i] = this.Dequeue();
38: }
39: this._datas = temps;
40: this._front = 0;
41: this._rear = this._datas.Length - 1;
42: }
43: if(this._rear+1==this._datas.Length) {
44: this._rear = 0;
45: }
46: else {
47: this._rear++;
48: }
49: this._datas[this._rear] = value;
50: }
51:
52: public T Dequeue() {
53: if(this.Count==0) {
54: throw new Exception("Queue is Empty");
55: }
56: T result = this._datas[this._front];
57: if(this.Count==1) {
58: this._front = -1;
59: this._rear = -1;
60: }
61: else {
62: if(this._front+1==this._datas.Length) {
63: this._front = 0;
64: }
65: else {
66: this._front++;
67: }
68: }
69: return result;
70: }
71:
72: public T Peek() {
73: if(this.Count == 0) {
74: throw new Exception("Queue is Empty");
75: }
76: return this._datas[this._front];
77: }
78: }
链队列
1: public class QueueNode<T> {
2: private QueueNode<T> _next;
3: private T _value;
4:
5: public QueueNode() : this(default(T), null) {
6: }
7:
8: public QueueNode(T value) : this(value, null) {
9: }
10:
11: public QueueNode(T value, QueueNode<T> next) {
12: this._value = value;
13: this._next = next;
14: }
15:
16: public QueueNode<T> Next {
17: get { return this._next; }
18: set { this._next = value; }
19: }
20:
21: public T Value {
22: get { return this._value; }
23: set { this._value = value; }
24: }
25: }
1: public class LinkQueue<T> : IQueue<T> {
2: private int _count = 0;
3: private QueueNode<T> _front;
4: private QueueNode<T> _rear;
5:
6: public int Count {
7: get { return _count; }
8: }
9:
10: public void Clear() {
11: this._count = 0;
12: }
13:
14: public void Add(T value) {
15: QueueNode<T> node = new QueueNode<T>(value);
16: if(this._count==0) {
17: this._front = this._rear = node;
18: }
19: else {
20: this._rear.Next = node;
21: this._rear = node;
22: }
23: this._count++;
24: }
25:
26: public T Dequeue() {
27: if(this.Count == 0) {
28: throw new Exception("Queue is Empty");
29: }
30: T result = this._front.Value;
31: this._front = this._front.Next;
32: this._count--;
33: return result;
34: }
35:
36: public T Peek() {
37: if(this.Count == 0) {
38: throw new Exception("Queue is Empty");
39: }
40: return this._front.Value;
41: }
42: }
标签：