- A+
所属分类：.NET技术
C#栈和队列的实现
用双向链表实现一个队列
public class DoubleNode { public int Value; public DoubleNode pre; public DoubleNode next; public DoubleNode(int value) { this.Value = value; this.pre=null; this.next=null; } } public class MyQueue//使用双向链表实现队列 { public DoubleNode head; public DoubleNode tail; public void AddFromHead(DoubleNode node)//从队头插入节点 { if(head == null) { head = node; tail = node; } else { node.next = head; head.pre = node; head = node; } } public void AddFromTail(DoubleNode node)//从队尾插入节点 { if(tail == null) { tail = node; head=node; } else { node.pre = tail; tail.next = node; tail = node; } } public DoubleNode PopFromHead()//从队头弹出节点 { if (head == null) return null; DoubleNode res = head; if (head==tail) { head=null; tail=null; } else { head = head.next; res.next=null; head.pre=null; } return res; } public DoubleNode PopFromTail()//从队尾弹出节点 { if (tail==null) return null; DoubleNode res=tail; if (head==tail) { head=null; tail=null; } else { tail=tail.pre; res.pre=null; tail.next=null; } return res; } } 使用双向链表实现栈
public class MyStack//使用双向链表实现栈 { public DoubleNode Head; public DoubleNode Tail; public void Push(int value) { DoubleNode temp = new DoubleNode(value); if (Head == null) { Head = temp; Tail= temp; } else { temp.next= Head; Head.pre = temp; Head = temp; } } public DoubleNode Pop() { if (Head == null) return null; DoubleNode res = Head; if (Head == Tail) { Head = null; Tail = null; return res; } Head = Head.next; res.next = null; Head.pre = null; return res; } public DoubleNode Peek() { if (Head == null) return null; return Head; } } 使用数组实现固定最大长度的栈和队列
public class MyStack1//使用数组实现固定最大长度的栈,暂定为L { public int[]nums; public int index; public int limit; public MyStack1(int L) { limit = L; nums= new int[limit]; index=0; } public void Push(int n) { if (index<limit) nums[index++] = n; else Console.WriteLine("栈已满"); } public int Pop() { int res = nums[--index]; return res; } public int Peek() { return nums[index-1]; } } public class MyQueue1//使用数组实现固定最大长度的队列，暂定为L { public int[] nums; public int headIndex; public int tailIndex; public int size; public int limit; public MyQueue1(int L) { limit = L; nums=new int[limit]; size=0; headIndex=0; tailIndex=0; } public int NextIndex(int i) { return i<=limit-1? i+1:0; } public void Push(int n) { if(size==limit) { Console.WriteLine("队列已经满了"); return; } size++; nums[tailIndex] = n; tailIndex=NextIndex(tailIndex); } public int Pop() { if (size==0) { throw new Exception("队列空了"); } size--; int res = nums[headIndex]; headIndex=NextIndex(headIndex); return res; } } 使用现成的栈结构实现一个能返回最小值的栈
//一个能返回最小值的栈（使用现成的栈结构实现） public class MyStackWithNormal //用现成的栈结构实现 { public Stack<int> stack=new Stack<int>(); public Stack<int> minStack=new Stack<int>(); public void push(int num) { stack.Push(num); if (minStack.Count == 0) { minStack.Push(num); } else { int temp = num > minStack.Peek() ? minStack.Peek() : num; minStack.Push(temp); } } public int pop() { return stack.Pop(); } public int GetMin() { return minStack.Peek(); } } 使用现有的栈实现队列，和使用现有的队列实现栈
public class QueueWithStack//使用现有的栈结构实现队列 { private Stack<int> stack = new Stack<int>(); private Stack<int> outStack = new Stack<int>(); public Stack<int> OutStack { get {//往输出栈中加数据时，输出栈必须为空，且必须把存储栈中的数据全部加入输出栈 if(outStack==null) { if (stack.Count==0) { Console.WriteLine("队列为空"); return null; } while (stack!=null) { outStack.Push(stack.Pop()); } return outStack; } else { return outStack; } } } public int Peek() { return outStack.Peek(); } public int Pop() { return OutStack.Pop(); } public void Push(int value) { stack.Push(value); } } public class StackWithQueue//使用现有的队列结构实现栈 { public Queue<int> queue1 = new Queue<int>(); public Queue<int> queue2 = new Queue<int>(); public void Push(int n) { queue1.Enqueue(n); } public int Peek() { if (queue1.Count==0 &&queue2.Count==0) { throw new Exception("栈为空"); } Queue<int> data=queue1.Count==0 ? queue2 : queue1; Queue<int> help=data==queue1? queue2 : queue1; while(data.Count > 1) { help.Enqueue(data.Dequeue()); } int res=data.Peek(); help.Enqueue(data.Dequeue() ); return res; } public int Pop() { if( queue1.Count==0 &&queue2.Count==0) { throw new Exception("栈为空"); } Queue<int> data=queue1.Count==0 ? queue2 : queue1; Queue<int> help=data==queue1? queue2 : queue1; while(data.Count > 1) { help.Enqueue(data.Dequeue()); } int res=data.Dequeue(); return res; } } 
