C#中的栈与队列/练习

  • C#中的栈与队列/练习已关闭评论
  • 147 次浏览
  • 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;      } }