算法大全-面试题-数据结构

if (queue1.Count == 0)

queue2.Enqueue(element); else

queue1.Enqueue(element); }

public int Pop() {

if (queue1.Count == 0 && queue2.Count == 0) throw new Exception(\if (queue1.Count > 0) {

while (queue1.Count > 1) {

queue2.Enqueue(queue1.Dequeue()); } //还剩一个

return (int)queue1.Dequeue(); }

else //queue2.Count > 0 {

while (queue2.Count > 1) {

queue1.Enqueue(queue2.Dequeue()); } //还剩一个

return (int)queue2.Dequeue(); } }

public int Peek() {

if (queue1.Count == 0 && queue2.Count == 0) throw new Exception(\int result = 0;

if (queue1.Count > 0) {

while (queue1.Count > 1) {

queue2.Enqueue(queue1.Dequeue()); } //还剩一个

result = (int)queue1.Dequeue(); queue2.Enqueue(result); }

else //queue2.Count > 0

{

while (queue2.Count > 1) {

queue1.Enqueue(queue2.Dequeue()); } //还剩一个

result = (int)queue2.Dequeue(); queue1.Enqueue(result); } return result; } }

5.栈的push、pop序列是否一致

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

比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

网上的若干算法都太复杂了，现提出包氏算法如下： 先for循环把arr1中的元素入栈，并在每次遍历时，检索arr2中可以pop的元素。如果循环结束，而stack中还有元素，就说明arr2序列不是pop序列。 static bool

JudgeSequenceIsPossible(int[] arr1,int[] arr2) {

Stackstack =newStack();

for(inti = 0, j = 0; i < arr1.Length; i++) {

stack.Push(arr1[i]);

while(stack.Count > 0 && (int)stack.Peek() == arr2[j]) {

stack.Pop(); j++; } }

returnstack.Count == 0;

}

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

算法思想：汉诺塔的思想，非常复杂，玩过九连环的人都想得通的 static void ReverseStack(ref Stack stack) {

if (stack.Count == 0) return;

object top = stack.Pop(); ReverseStack(ref stack); if (stack.Count == 0) {

stack.Push(top); return; }

object top2 = stack.Pop(); ReverseStack(ref stack); stack.Push(top);

ReverseStack(ref stack); stack.Push(top2); }

7.给栈排个序

本题目是上一题目的延伸 static void Sort(ref Stack stack) {

if (stack.Count == 0) return;

object top = stack.Pop(); Sort(ref stack);

if (stack.Count == 0) {

stack.Push(top);

return; }

object top2 = stack.Pop(); if ((int)top > (int)top2) {

stack.Push(top); Sort(ref stack); stack.Push(top2); } else {

stack.Push(top2); Sort(ref stack); stack.Push(top); } }

8..如何用一个数组实现两个栈

继续我所提倡的抠门儿思想，也不枉我和青菜脸相交一场。 网上流传着两种方法： 方法1

采用交叉索引的方法

一号栈所占数组索引为0, 2, 4, 6, 8......(K*2)

二号栈所占数组索引为1，3，5，7，9 ......(K*2 + 1)

算法实现如下：

public class NewStack {

object[] arr; int top1; int top2;

public NewStack(int capticy) {

arr = new object[capticy]; top1 = -1;

top2 = -2;

}

public void Push(int type, object element) {

if (type == 1) {

if (top1 + 2 >= arr.Length)

throw new Exception(\ else {

top1 += 2;

arr[top1] = element; } } else //type==2 {

if (top2 + 2 >= arr.Length)

throw new Exception(\ else {

top2 += 2;

arr[top2] = element; } } }

public object Pop(int type) {

object obj = null; if (type == 1) {

if (top1 == -1)

throw new Exception(\ else {

obj = arr[top1]; arr[top1] = null; top1 -= 2; } } else //type == 2 {

if (top2 == -2)

throw new Exception(\ else {