数据结构（C#版本）_栈和队列
【摘要】
推荐阅读：
我的CSDN 我的博客园 QQ群：704621321
栈：先进后出，只能在栈顶进行操作。
栈的操作主要包括在栈顶插入元素和删除元...
推荐阅读：
栈：先进后出，只能在栈顶进行操作。
栈的操作主要包括在栈顶插入元素和删除元素、取栈顶元素和判断栈是否为空等。
栈的接口定义：
public interface IStack<T>
{
int GetLength(); //求栈的长度
bool IsEmpty(); //判断栈是否为空
void Clear(); //清空操作
void Push(T item); //入栈操作 T
Pop(); //出栈操作
T GetTop(); //取栈顶元素
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
字段 top 表示栈顶，top 的范围是0 到 maxsize-1，如果顺序栈为空，top=-1
1.顺序栈类 SeqStack的实现：
public class SeqStack<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 SeqStack(int size)
{
data = new T[size];
maxsize = size;
top = -1;
}
//求栈的长度
public int GetLength()
{
return top + 1;
}
//清空顺序栈
public void Clear()
{
top = -1;
}
//判断顺序栈是否为空
public bool IsEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
//判断顺序栈是否为满
public bool IsFull()
{
if (top == maxsize - 1)
{
return true;
}
else
{
return false;
}
}
//入栈
public void Push(T item)
{
if (IsFull())
{
return;
}
data[++top] = item;
}
//出栈
public T Pop()
{
T tmp = default(T);
if (IsEmpty())
{
return tmp;
}
tmp = data[top];
--top;
return tmp;
}
//获取栈顶元素
public T GetTop()
{
if (IsEmpty())
{
return default(T);
}
return data[top];
}
}
SeqStack
- 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
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
链栈 通常用单链表来表示，栈顶设在链表的头部，并且不需要头结点
2.链栈结点类(Node)的实现：
public class Node<T>
{
private T data; //数据域
private Node<T> next; //引用域
//构造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
//构造器
public Node(Node<T> p)
{
next = p;
}
//构造器
public Node(T val)
{
data = val;
}
//数据域属性
public T Data
{
get { return data; }
set { data = value; }
}
//引用域
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
Node
- 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
3.链栈类 LinkStack的实现： LinkStack类增 设一个字段 num 表示链栈中结点的个数。
public class LinkStack<T> : IStack<T>
{
private Node<T> top; //栈顶指示器
private int num; //栈中结点的个数
//栈顶指示器属性
public Node<T> Top
{
get { return top; }
set { top = value; }
}
//元素个数属性
public int Num
{
get { return num; }
set { num = value; }
}
//构造器
public LinkStack()
{
Top = null;
num = 0;
}
//求链栈的长度
public int GetLength()
{
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()
{
Node<T> q = new Node<T>(item);
if (top == null)
{
top = q;
}
else
{
q.Next = top;
top = q;
}
++num;
}
//出栈
public T Pop()
{
if (IsEmpty())
{
return default(T);
}
Node<T> p = top;
top = top.Next;
--num;
return p.Data;
}
//取栈顶结点的值
public T GetTop()
{
if (IsEmpty())
{
return default(T);
}
return top.Data;
}
}
LinkStack
- 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
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
**4.进制转换：**将一个十进制数 N 转换为八进制数：利用辗转相 除法，转换得到的八进制数各个数位
算法思想如下：当 N＞0 时，重复步骤 1 和步骤 2。
步骤 1：若 N≠0，则将 N%8 压入栈中，执行步骤 2；若 N=0。则将栈的内 容依次出栈，算法结束。
步骤 2：用 N/8 代替 N，返回步骤 1。
算法实现如下：
public void Conversion(int n)
{
LinkStack<int> s = new LinkStack<int>();
while(n > 0)
{
s.Push(n%8);//余数入栈
n = n/8;
}
while(!s.IsEmpty())
{
n = s.Pop();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
5.括号匹配
算法思想：如果括号序列不为空，重复步骤 1。
步骤 1：从括号序列中取出 1 个括号，分为三种情况：
a) 如果栈为空，则将括号入栈；
b) 如果括号与栈顶的括号匹配，则将栈顶括号出栈。
c) 如果括号与栈顶的括号不匹配，则将括号入栈。
步骤 2：如果括号序列为空并且栈为空则括号匹配，否则不匹配。
用顺序栈实现算法：
public bool MatchBracket(char[] charlist)
{
SeqStack<char> s = new SeqStack<char>(50);
int len = charlist.Length;
for (int i = 0; i < len; ++i)
{
if (s.IsEmpty())
{
s.Push(charlist[i]);
}
else if(((s.GetTop()=="(")&&(charlist[i]==")")))||(s.GetTop()=="[" && charlist[i]=="]"))
{
s.Pop();
}
else
{
s.Push(charlist[i]);
}
}
if (s.IsEmpty())
{
return true;
}
else
{
return false;
}
}
MatchBracket(char[] charlist)
- 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
队列(Queue)是插入操作限定在表的尾部，其它操作限定在表的头部进行的线性表。
队列的操作主要包括：在队尾插入元素、在队头删除元素、取队头元素和判断队列是否为空等。
队列“队尾入 队头出”的操作造成“假溢出”，解决假溢出的方法：将顺序队列看成是首尾相接的循环结构，头尾指示器的关系不变，这种队列叫循环顺序队列。
front 表示队头，front 的范围是 0 到 maxsize-1。 rear 表示队尾，rear 的范围也是 0 到 maxsize-1。
如果循环顺序队列为空，front=rear=-1。 当执行入队列操作时需要判断循环顺序队列是否已满。
如果循环顺序队列已满， (rear + 1) % maxsize==front ，循环顺序队列已满不能插入元素。
求循环队列中数据元素的个数：(rear-front+maxsize)%maxsize
6.循环顺序队列类 CSeqQueue的实现：
public class CSeqQueue<T> : IQueue<T>
{
private int maxsize; //循环顺序队列的容量
private T[] data; //数组，用于存储循环顺序队列中的数据元素
private int front; //指示循环顺序队列的队头
private int rear; //指示循环顺序队列的队尾
//索引器
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
//容量属性
public int MaxSize
{
get { return maxsize; }
set { maxsize = value; }
}
//队头属性
public int Front
{
get { return front; }
set { front = value; }
}
//队尾属性
public int Rear
{
get { return rear; }
set { rear = value; }
}
//构造器
public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -1;
}
//求循环队列长度
public int GetLength()
{
return (rear - front + maxsize) % maxsize;
}
//清空循环队列
public void Clear()
{
front = rear = -1;
}
//判断循环队列是否为空
public bool IsEmpty()
{
if (front == rear)
{
return true;
}
else
{
return false;
}
}
//判断循环顺序队列是否为满
public bool IsFull()
{
if ((rear + 1) % maxsize == front)
{
return true;
}
else
{
return false;
}
}
//入队
public void In(T item)
{
if (IsFull())
{
return;
}
else
{
data[++rear] = item;
}
}
//出队
public T Out()
{
T tmp = default(T);
if (IsEmpty())
{
return tmp;
}
tmp = data[++front];
return tmp;
}
//获取队头数据元素
public T GetFront()
{
if (IsEmpty())
{
return default(T);
}
return data[++front];
}
}
CSeqQueue
- 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
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
链队列
7.队列结点类(Node)的实现：
public class Node<T>
{
private T data; //数据域
private Node<T> next; //引用域
//构造器
public Node(T val, Node<T> p)
{
data = val;
next = p;
}
//构造器
public Node(Node<T> p)
{
next = p;
}
//构造器
public Node(T val)
{
data = val;
next = null;
}
//构造器
public Node()
{
data = default(T);
next = null;
}
//数据域属性
public T Data
{
get { return data; }
set { data = value; }
}
//引用域属性
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
Node
- 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
8.链队列类 LinkQueue的实现：
public class LinkQueue<T> : IQueue<T>
{
private Node<T> front; //队列头指示器
private Node<T> rear; //队列尾指示器
private int num; //队列结点个数
//队头属性
public Node<T> Front
{
get{return front;}
set{front=value;}
}
//队尾属性
public int Rear
{
get { return rear; }
set { rear = value; }
}
//结点的个数
public int Num
{
get{return num;}
set{num=value;}
}
//构造器
public LinkQueue(int size)
{
front=rear=-1;
num=0;
}
//求循环队列长度
public int GetLength()
{
return num;
}
//清空循环队列
public void Clear()
{
front = rear = null;
num=0;
}
//判断循环队列是否为空
public bool IsEmpty()
{
if (front == rear)&&(num==0)
{
return true;
}
else
{
return false;
}
}
//入队
public void In(T item)
{
Node<T> q = new Node<T>(item);
if (rear == null)
{
rear=q;
}
else
{
rear.Next=q;
rear=q;
}
++num;
}
//出队
public T Out()
{
if (IsEmpty())
{
return default(T);
}
Node<T> p = front;
front = front.Next;
if(front == null)
{
rear=null;
}
--num;
return p.Data;
}
//获取队头数据元素
public T GetFront()
{
if (IsEmpty())
{
return default(T);
}
return front.Data;
}
}
LinkQueue
- 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
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
9.判断一个字符串是否是回文：采用循环顺序队列和顺序栈 来实现
public bool Main()
{
SeqStack<char> s = new SeqStack<char>(50);
CSeqQueue<char> q = new CSeqQueue<char>(50);
string str = Console.ReadLine();
for(int i = 0; i < str.Length; ++i)
{
s.Push(str[i]);
q.In(str[i]);
}
while(!s.IsEmpty() && !q.IsEmpty())
{
if(s.Pop() != q.Out())
{
return false;
}
}
return true；
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
文章来源: unity3d.blog.csdn.net，作者：爱上游戏开发，版权归原作者所有，如需转载，请联系作者。
原文链接：unity3d.blog.csdn.net/article/details/84977091
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）