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;
}
}