目录:

1.设计含min栈要求min、push和pop时间复杂度都是o(1)

2.设计含min栈另解

3.用两个栈实现队列

4.用两个队列实现栈 

5.栈push、pop序列是否致

6.递归反转个栈要求不得重新申请个同样栈空间复杂度o(1)

7.给栈排个序

8..如何用个实现两个栈

9..如何用个实现 3个栈
 

1.设计含min栈要求min、push和pop时间复杂度都是o(1)

　　算法思想:需要设计个辅助栈用来存储当前栈中元素最小值网上有人说存储当前栈中元素最小值所在位置虽然能节省空间这其实是不对我在Min时候只能得到位置还要对存储元素栈不断pop才能得到最小值——时间复杂度o(1)

　　所以还是在辅助栈中存储元素吧

　　此外还要额外注意Push操作第个元素不用比较自动成为最小值入栈其它元素每次都要和栈顶元素比较小那个放到栈顶 

public NewStack { private Stack dataStack; private Stack mindataStack; public NewStack { dataStack = Stack; mindataStack = Stack; } public void Push( element) { dataStack.Push(element); (mindataStack.Count 0) mindataStack.Push(element); (element <= ()mindataStack.Peek) mindataStack.Push(element); //(element > mindataStack.Peek) mindataStack.Push(mindataStack.Peek); } public Pop { (dataStack.Count 0) throw Exception("The stack is empty"); mindataStack.Pop; ()dataStack.Pop; } public Min { (dataStack.Count 0) throw Exception("The stack is empty"); ()mindataStack.Peek; } }

  

2.设计含min栈另解

　　话说和青菜脸呆久了就沾染了上海小市民意识再加上原本我就很抠门儿于是对于上题目我把个栈当成两个用就是说每次push先入站当前元素然后入栈当前栈中最小元素；pop则每次弹出2个元素

　　算法代码如下所示(这里最小元素位于当前元素的上为了下次比较方便):

public NewStack { private Stack stack; public NewStack { stack = Stack; } public void Push( element) { (stack.Count 0) { stack.Push(element); stack.Push(element); } (element <= ()stack.Peek) { stack.Push(element); stack.Push(element); } //(element > stack.Peek) { object min = stack.Peek; stack.Push(element); stack.Push(min); } } public Pop { (stack.Count 0) throw Exception("The stack is empty"); stack.Pop; ()stack.Pop; } public Min { (stack.Count 0) throw Exception("The stack is empty"); ()stack.Peek; } }  

　　的所以说我这个算法比较叩门是我只使用了个栈空间复杂度o(N)节省了半空间(算法1空间复杂度o(2N))

 

 

3.用两个栈实现队列

　　实现队列就要实现它3个思路方法:Enqueue(入队)、Dequeue(出队)和Peek(队头)

1)stack1存是每次进来元素所以Enqueue就是把进来元素push到stack1中

2)而对于Dequeue开始stack2是空所以我们把stack1中元素全都pop到stack2中这样stack2栈顶就是队头只要stack2不为空那么每次出队就相当于stack2pop

3)接下来每入队个元素仍然push到stack1中每出队个元素如果stack2不为空就从stack2中pop个元素；如果stack2为空就重复上面操作——把stack1中元素全都pop到stack2中

4)Peek操作类似于Dequeue只是不需要出队所以我们stack2Peek操作当然如果stack2为空就把stack1中元素全都pop到stack2中

5)注意边界处理如果stack2和stack1都为空才等于队列为空此时不能进行Peek和Dequeue操作
　　按照上述分析算法实现如下:

public NewQueue { private Stack stack1; private Stack stack2; public NewQueue { stack1 = Stack; stack2 = Stack; } public void Enqueue( element) { stack1.Push(element); } public Dequeue { (stack2.Count 0) { (stack1.Count 0) throw Exception("The queue is empty"); while (stack1.Count > 0) stack2.Push(stack1.Pop); } ()stack2.Pop; } public Peek { (stack2.Count 0) { (stack1.Count 0) throw Exception("The queue is empty"); while (stack1.Count > 0) stack2.Push(stack1.Pop); } ()stack2.Peek; } } 

 

4.用两个队列实现栈

　　这个嘛就要queue1和queue2轮流存储数据了这个“轮流”发生在Pop和Peek时候假设此时我们把所有数据存在queue1中(此时queue2为空)我们把queue1n-1个元素放到queue2中queue中最后个元素就是我们想要pop元素此时queue2存有n-1个元素(queue1为空)

　　至于Peek则是每次转移n个数据再转移最后个元素时候将其计下并返回

　　那么Push操作则需要判断当前queue1和queue2哪个为空将新元素放到不为空队列中

public NewStack { private Queue queue1; private Queue queue2; public NewStack { queue1 = Queue; queue2 = Queue; } public void Push( element) { (queue1.Count 0) queue2.Enqueue(element); queue1.Enqueue(element); } public Pop { (queue1.Count 0 && queue2.Count 0) throw Exception("The stack is empty"); (queue1.Count > 0) { while (queue1.Count > 1) { queue2.Enqueue(queue1.Dequeue); } //还剩个 ()queue1.Dequeue; } //queue2.Count > 0 { while (queue2.Count > 1) { queue1.Enqueue(queue2.Dequeue); } //还剩个 ()queue2.Dequeue; } } public Peek { (queue1.Count 0 && queue2.Count 0) throw Exception("The stack is empty"); result = 0; (queue1.Count > 0) { while (queue1.Count > 1) { queue2.Enqueue(queue1.Dequeue); } //还剩个 result = ()queue1.Dequeue; queue2.Enqueue(result); } //queue2.Count > 0 { while (queue2.Count > 1) { queue1.Enqueue(queue2.Dequeue); } //还剩个 result = ()queue2.Dequeue; queue1.Enqueue(result); } result; } } 

 

5.栈push、pop序列是否致

　　输入两个整数序列其中个序列表示栈push顺序判断另个序列有没有可能是对应pop顺序为了简单起见我们假设push序列任意两个整数都是不相等

　　比如输入push序列是1、2、3、4、5那么4、5、3、2、1就有可能是个pop系列可以有如下push和pop序列:push 1push 2push 3push 4poppush 5poppoppoppop这样得到pop序列就是4、5、3、2、1但序列4、3、5、1、2就不可能是push序列1、2、3、4、5pop序列

 

　　网上若干算法都太复杂了现提出包氏算法如下:

　　先for循环把arr1中元素入栈并在每次遍历时检索arr2中可以pop元素如果循环结束而stack中还有元素就介绍说明arr2序列不是pop序列

boolJudgeSequenceIsPossible( arr1, arr2)
{
    Stackstack = Stack;

    for(i = 0, j = 0; i < arr1.Length; i)
    {
        stack.Push(arr1[i]);

        while(stack.Count > 0 && ()stack.Peek arr2[j])
        {
            stack.Pop;
            j;
        }
    }

    stack.Count 0;
}


 

 

6.递归反转个栈要求不得重新申请个同样栈空间复杂度o(1)

　　算法思想:汉诺塔思想非常复杂玩过 9连环人都想得通

void ReverseStack(ref Stack stack) { (stack.Count 0) ; object top = stack.Pop; ReverseStack(ref stack); (stack.Count 0) { stack.Push(top); ; } object top2 = stack.Pop; ReverseStack(ref stack); stack.Push(top); ReverseStack(ref stack); stack.Push(top2); }

 

7.给栈排个序

　　本题目是上题目延伸

void Sort(ref Stack stack) { (stack.Count 0) ; object top = stack.Pop; Sort(ref stack); (stack.Count 0) { stack.Push(top); ; } object top2 = stack.Pop; (()top > ()top2) { stack.Push(top); Sort(ref stack); stack.Push(top2); } { stack.Push(top2); Sort(ref stack); stack.Push(top); } }

 

 

8..如何用个实现两个栈

　　继续我所提倡抠门儿思想也不枉我和青菜脸相交场

　　网上流传着两种思路方法:

　　思路方法1  采用交叉索引思路方法

号栈所占索引为0, 2, 4, 6, 8......(K*2)  
2号栈所占索引为13579 ......(K*2 + 1) 
　　算法实现如下:

public NewStack { object arr; top1; top2; public NewStack( capticy) { arr = object[capticy]; top1 = -1; top2 = -2; } public void Push( type, object element) { (type 1) { (top1 + 2 >= arr.Length) throw Exception("The stack is full"); { top1 2; arr[top1] = element; } } //type2 { (top2 + 2 >= arr.Length) throw Exception("The stack is full"); { top2 2; arr[top2] = element; } } } public object Pop( type) { object obj = null; (type 1) { (top1 -1) throw Exception("The stack is empty"); { obj = arr[top1]; arr[top1] = null; top1 -= 2; } } //type 2 { (top2 -2) throw Exception("The stack is empty"); { obj = arr[top2]; arr[top2] = null; top2 -= 2; } } obj; } public object Peek( type) { (type 1) { (top1 -1) throw Exception("The stack is empty"); arr[top1]; } //type 2 { (top2 -2) throw Exception("The stack is empty"); arr[top2]; } } }

  

　　思路方法2:

第个栈A:从最左向右增长
第 2个栈B:从最右向左增长 
　　代码实现如下:

public NewStack { object arr; top1; top2; public NewStack( capticy) { arr = object[capticy]; top1 = 0; top2 = capticy; } public void Push( type, object element) { (top1 top2) throw Exception("The stack is full"); (type 1) { arr[top1] = element; top1; } //type2 { top2--; arr[top2] = element; } } public object Pop( type) { object obj = null; (type 1) { (top1 0) throw Exception("The stack is empty"); { top1--; obj = arr[top1]; arr[top1] = null; } } //type 2 { (top2 arr.Length) throw Exception("The stack is empty"); { obj = arr[top2]; arr[top2] = null; top2; } } obj; } public object Peek( type) { (type 1) { (top1 0) throw Exception("The stack is empty"); arr[top1 - 1]; } //type 2 { (top2 arr.Length) throw Exception("The stack is empty"); arr[top2]; } } }

　　综合比较上述两种算法我们发现算法1实现两个栈每个都只有n/2个空间大小；而算法2实现两个栈如果其中个很小另个则可以很大它们和为常数n

 

9..如何用个实现 3个栈

　　最后让我们把抠门儿进行到底相信看完本文你已经从物质和精神上都升级为个抠门儿主义者

　　如果还使用交叉索引办法每个栈都只有N/3个空间

　　让我们只好使用上个题目第2个思路方法不过这只能容纳2个栈我们还需要个位置存放第3个栈不如考虑中间位置——第3个栈增长规律可以如下:

第1个入栈C元素进mid处
第2个入栈C元素进mid+1处
第3个入栈C元素进mid-1处
第4个入栈C元素进mid+2处
　　这个思路方法好处是 每个栈都有接近N/3个空间

public NewStack { object arr; top1; top2; top3_left; top3_right; bool isLeft; public NewStack( capticy) { arr = object[capticy]; top1 = 0; top2 = capticy; isLeft = true; top3_left = capticy / 2; top3_right = top3_left + 1; } public void Push( type, object element) { (type 1) { (top1 top3_left + 1) throw Exception("The stack is full"); arr[top1] = element; top1; } (type 2) { (top2 top3_right) throw Exception("The stack is full"); top2--; arr[top2] = element; } //type3 { (isLeft) { (top1 top3_left + 1) throw Exception("The stack is full"); arr[top3_left] = element; top3_left--; } { (top2 top3_right) throw Exception("The stack is full"); arr[top3_right] = element; top3_right; } isLeft = !isLeft; } } public object Pop( type) { object obj = null; (type 1) { (top1 0) throw Exception("The stack is empty"); { top1--; obj = arr[top1]; arr[top1] = null; } } (type 2) { (top2 arr.Length) throw Exception("The stack is empty"); { obj = arr[top2]; arr[top2] = null; top2; } } //type3 { (top3_right top3_left + 1) throw Exception("The stack is empty"); (isLeft) { top3_left; obj = arr[top3_left]; arr[top3_left] = null; } { top3_right--; obj = arr[top3_right]; arr[top3_right] = null; } isLeft = !isLeft; } obj; } public object Peek( type) { (type 1) { (top1 0) throw Exception("The stack is empty"); arr[top1 - 1]; } (type 2) { (top2 arr.Length) throw Exception("The stack is empty"); arr[top2]; } //type3 { (top3_right top3_left + 1) throw Exception("The stack is empty"); (isLeft) arr[top3_left + 1]; arr[top3_right - 1]; } } }