C#棧和隊列的實現 用雙向鏈表實現一個隊列 public class DoubleNode { public int Value; public DoubleNode pre; public DoubleNode next; public DoubleNode(int value) { this.V ...
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;
}
}
