算法大全（2）栈和队列

　　声明，本文所有9道算法题目，覆盖了基本上所有常见的栈/队列问题，全都用C#实现，并测试通过，代码下载：StackAndQueue.zip

目录：
1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。
2.设计含min函数的栈的另解
3.用两个栈实现队列
4.用两个队列实现栈 
5.栈的push、pop序列是否一致
6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1)
7.给栈排个序
8..如何用一个数组实现两个栈
9..如何用一个数组实现三个栈

 
1.设计含min函数的栈，要求min、push和pop的时间复杂度都是o(1)。
　　算法思想：需要设计一个辅助栈，用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置，虽然能节省空间，这其实是不对的，因为我在调用Min函数的时候，只能得到位置，还要对存储元素的栈不断的pop，才能得到最小值——时间复杂度o(1)。
　　所以，还是在辅助栈中存储元素吧。
　　此外，还要额外注意Push操作，第一个元素不用比较，自动成为最小值入栈。其它元素每次都要和栈顶元素比较，小的那个放到栈顶。 

1. public class NewStack
2. {
3.     private Stack dataStack;
4.     private Stack mindataStack;
6.     public NewStack()
7.     {
8.         dataStack = new Stack();
9.         mindataStack = new Stack();
10.     }
12.     public void Push(int element)
13.     {
14.         dataStack.Push(element);
16.         if (mindataStack.Count == 0)
17.             mindataStack.Push(element);
18.         else if (element <= (int)mindataStack.Peek())
19.             mindataStack.Push(element);
20.         else //(element > mindataStack.Peek)
21.             mindataStack.Push(mindataStack.Peek());
22.     }
23.    
24.     public int Pop()
25.     {
26.         if (dataStack.Count == 0)
27.             throw new Exception("The stack is empty");
28.         
29.         mindataStack.Pop();
30.         return (int)dataStack.Pop();
31.     }
33.     public int Min()
34.     {
35.         if (dataStack.Count == 0)
36.             throw new Exception("The stack is empty");
37.         
38.         return (int)mindataStack.Peek();
39.     }
40. }

复制代码

  
2.设计含min函数的栈的另解
　　话说，和青菜脸呆久了，就沾染了上海小市民意识，再加上原本我就很抠门儿，于是对于上一题目，我把一个栈当成两个用，就是说，每次push，先入站当前元素，然后入栈当前栈中最小元素；pop则每次弹出2个元素。
　　算法代码如下所示（这里最小元素位于当前元素之上，为了下次比较方便）：

1. public class NewStack
2. {
3.     private Stack stack;
5.     public NewStack()
6.     {
7.         stack = new Stack();
8.     }
10.     public void Push(int element)
11.     {
12.         if (stack.Count == 0)
13.         {
14.             stack.Push(element);
15.             stack.Push(element);
16.         }
17.         else if (element <= (int)stack.Peek())
18.         {
19.             stack.Push(element);
20.             stack.Push(element);
21.         }
22.         else //(element > stack.Peek)
23.         {
24.             object min = stack.Peek();
25.             stack.Push(element);
26.             stack.Push(min);            
27.         }
28.     }
30.     public int Pop()
31.     {
32.         if (stack.Count == 0)
33.             throw new Exception("The stack is empty");
35.         stack.Pop();
36.         return (int)stack.Pop();
37.     }
39.     public int Min()
40.     {
41.         if (stack.Count == 0)
42.             throw new Exception("The stack is empty");
44.         return (int)stack.Peek();
45.     }
46. }  

复制代码

　　之所以说我这个算法比较叩门，是因为我只使用了一个栈，空间复杂度o(N)，节省了一半的空间（算法1的空间复杂度o(2N)）。
 
 
3.用两个栈实现队列
　　实现队列，就要实现它的3个方法：Enqueue（入队）、Dequeue（出队）和Peek（队头）。

1）stack1存的是每次进来的元素，所以Enqueue就是把进来的元素push到stack1中。
2）而对于Dequeue，一开始stack2是空的，所以我们把stack1中的元素全都pop到stack2中，这样stack2的栈顶就是队头。只要stack2不为空，那么每次出队，就相当于stack2的pop。
3）接下来，每入队一个元素，仍然push到stack1中。每出队一个元素，如果stack2不为空，就从stack2中pop一个元素；如果stack2为空，就重复上面的操作——把stack1中的元素全都pop到stack2中。
4）Peek操作，类似于Dequeue，只是不需要出队，所以我们调用stack2的Peek操作。当然，如果stack2为空，就把stack1中的元素全都pop到stack2中。
5）注意边界的处理，如果stack2和stack1都为空，才等于队列为空，此时不能进行Peek和Dequeue操作。

　　按照上述分析，算法实现如下：

1. public class NewQueue
2. {
3.     private Stack stack1;
4.     private Stack stack2;
6.     public NewQueue()
7.     {
8.         stack1 = new Stack();
9.         stack2 = new Stack();
10.     }
12.     public void Enqueue(int element)
13.     {
14.         stack1.Push(element);
15.     }
17.     public int Dequeue()
18.     {
19.         if (stack2.Count == 0)
20.         {
21.             if (stack1.Count == 0)
22.                 throw new Exception("The queue is empty");
23.             else
24.                 while (stack1.Count > 0)
25.                     stack2.Push(stack1.Pop());
26.         }
28.         return (int)stack2.Pop();
29.     }
31.     public int Peek()
32.     {
33.         if (stack2.Count == 0)
34.         {
35.             if (stack1.Count == 0)
36.                 throw new Exception("The queue is empty");
37.             else
38.                 while (stack1.Count > 0)
39.                     stack2.Push(stack1.Pop());
40.         }
42.         return (int)stack2.Peek();
43.     }
44. } 

复制代码

 
4.用两个队列实现栈
　　这个嘛，就要queue1和queue2轮流存储数据了。这个“轮流”发生在Pop和Peek的时候，假设此时我们把所有数据存在queue1中（此时queue2为空），我们把queue1的n-1个元素放到queue2中，queue中最后一个元素就是我们想要pop的元素，此时queue2存有n-1个元素（queue1为空）。
　　至于Peek，则是每次转移n个数据，再转移最后一个元素的时候，将其计下并返回。
　　那么Push的操作，则需要判断当前queue1和queue2哪个为空，将新元素放到不为空的队列中。

1. public class NewStack
2. {
3.     private Queue queue1;
4.     private Queue queue2;
6.     public NewStack()
7.     {
8.         queue1 = new Queue();
9.         queue2 = new Queue();
10.     }
12.     public void Push(int element)
13.     {
14.         if (queue1.Count == 0)
15.             queue2.Enqueue(element);
16.         else
17.             queue1.Enqueue(element);
18.     }
20.     public int Pop()
21.     {
22.         if (queue1.Count == 0 && queue2.Count == 0)
23.             throw new Exception("The stack is empty");
25.         if (queue1.Count > 0)
26.         {
27.             while (queue1.Count > 1)
28.             {
29.                 queue2.Enqueue(queue1.Dequeue());
30.             }
32.             //还剩一个
33.             return (int)queue1.Dequeue();
34.         }
35.         else  //queue2.Count > 0
36.         {
37.             while (queue2.Count > 1)
38.             {
39.                 queue1.Enqueue(queue2.Dequeue());
40.             }
42.             //还剩一个
43.             return (int)queue2.Dequeue();
44.         }
45.     }
47.     public int Peek()
48.     {
49.         if (queue1.Count == 0 && queue2.Count == 0)
50.             throw new Exception("The stack is empty");
52.         int result = 0;
54.         if (queue1.Count > 0)
55.         {
56.             while (queue1.Count > 1)
57.             {
58.                 queue2.Enqueue(queue1.Dequeue());
59.             }
61.             //还剩一个
62.             result = (int)queue1.Dequeue();
63.             queue2.Enqueue(result);
65.         }
66.         else  //queue2.Count > 0
67.         {
68.             while (queue2.Count > 1)
69.             {
70.                 queue1.Enqueue(queue2.Dequeue());
71.             }
73.             //还剩一个
74.             result = (int)queue2.Dequeue();
75.             queue1.Enqueue(result);
76.         }
78.         return result;
79.     }
80. } 

复制代码

 
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)
{
    Stack stack = new Stack();

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

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

    return stack.Count == 0;
}

 
 
6.递归反转一个栈，要求不得重新申请一个同样的栈，空间复杂度o(1)
　　算法思想：汉诺塔的思想，非常复杂，玩过九连环的人都想得通的

1. static void ReverseStack(ref Stack stack)
2. {
3.     if (stack.Count == 0)
4.         return;
6.     object top = stack.Pop();
8.     ReverseStack(ref stack);
10.     if (stack.Count == 0)
11.     {
12.         stack.Push(top);
13.         return;
14.     }
16.     object top2 = stack.Pop();
17.     ReverseStack(ref stack);
19.     stack.Push(top);
20.     ReverseStack(ref stack);
21.     stack.Push(top2);        
22. }

复制代码

1.  

复制代码

7.给栈排个序
　　本题目是上一题目的延伸

1. static void Sort(ref Stack stack)
2. {
3.     if (stack.Count == 0)
4.         return;
6.     object top = stack.Pop();
8.     Sort(ref stack);
10.     if (stack.Count == 0)
11.     {
12.         stack.Push(top);
13.         return;
14.     }
16.     object top2 = stack.Pop();
17.     if ((int)top > (int)top2)
18.     {
19.         stack.Push(top);
20.         Sort(ref stack);
21.         stack.Push(top2);
22.     }
23.     else
24.     {
25.         stack.Push(top2);
26.         Sort(ref stack);
27.         stack.Push(top);
28.     }
29. }

复制代码

 
 
8..如何用一个数组实现两个栈
　　继续我所提倡的抠门儿思想，也不枉我和青菜脸相交一场。
　　网上流传着两种方法：
　　方法1  采用交叉索引的方法

一号栈所占数组索引为0, 2, 4, 6, 8......(K*2)  
二号栈所占数组索引为1，3，5，7，9 ......(K*2 + 1) 

　　算法实现如下：

1. public class NewStack
2. {
3.     object[] arr;
4.     int top1;
5.     int top2;
7.     public NewStack(int capticy)
8.     {
9.         arr = new object[capticy];
11.         top1 = -1;
12.         top2 = -2;
13.     }
15.     public void Push(int type, object element)
16.     {
17.         if (type == 1)
18.         {
19.             if (top1 + 2 >= arr.Length)
20.                 throw new Exception("The stack is full");
21.             else
22.             {
23.                 top1 += 2;
24.                 arr[top1] = element;
25.             }
26.         }
28.         else //type==2
29.         {
30.             if (top2 + 2 >= arr.Length)
31.                 throw new Exception("The stack is full");
32.             else
33.             {
34.                 top2 += 2;
35.                 arr[top2] = element;
36.             }
37.         }
38.     }
40.     public object Pop(int type)
41.     {
42.         object obj = null;
44.         if (type == 1)
45.         {
46.             if (top1 == -1)
47.                 throw new Exception("The stack is empty");
48.             else
49.             {
50.                 obj = arr[top1];
51.                 arr[top1] = null;
52.                 top1 -= 2;
53.             }
54.         }
56.         else //type == 2
57.         {
58.             if (top2 == -2)
59.                 throw new Exception("The stack is empty");
60.             else
61.             {
62.                 obj = arr[top2];
63.                 arr[top2] = null;
64.                 top2 -= 2;
65.             }
66.         }
68.         return obj;
69.     }
71.     public object Peek(int type)
72.     {
73.         if (type == 1)
74.         {
75.             if (top1 == -1)
76.                 throw new Exception("The stack is empty");
78.             return arr[top1];
79.         }
81.         else //type == 2
82.         {
83.             if (top2 == -2)
84.                 throw new Exception("The stack is empty");
86.             return arr[top2];
87.         }
88.     }
89. }

复制代码

  
　　方法2：

第一个栈A：从最左向右增长
第二个栈B：从最右向左增长 

　　代码实现如下：

1. public class NewStack
2. {
3.     object[] arr;
4.     int top1;
5.     int top2;
7.     public NewStack(int capticy)
8.     {
9.         arr = new object[capticy];
11.         top1 = 0;
12.         top2 = capticy;
13.     }
15.     public void Push(int type, object element)
16.     {
17.         if (top1 == top2)
18.             throw new Exception("The stack is full");
20.         if (type == 1)
21.         {
22.             arr[top1] = element;
23.             top1++;
24.         }
25.         else //type==2
26.         {
27.             top2--;
28.             arr[top2] = element;
29.         }            
30.     }
32.     public object Pop(int type)
33.     {
34.         object obj = null;
36.         if (type == 1)
37.         {
38.             if (top1 == 0)
39.                 throw new Exception("The stack is empty");
40.             else
41.             {
42.                 top1--;
43.                 obj = arr[top1];
44.                 arr[top1] = null;
45.             }
46.         }
48.         else //type == 2
49.         {
50.             if (top2 == arr.Length)
51.                 throw new Exception("The stack is empty");
52.             else
53.             {
54.                 obj = arr[top2];
55.                 arr[top2] = null;
56.                 top2++;
57.             }
58.         }
60.         return obj;
61.     }
63.     public object Peek(int type)
64.     {
65.         if (type == 1)
66.         {
67.             if (top1 == 0)
68.                 throw new Exception("The stack is empty");
70.             return arr[top1 - 1];
71.         }
73.         else //type == 2
74.         {
75.             if (top2 == arr.Length)
76.                 throw new Exception("The stack is empty");
78.             return arr[top2];
79.         }
80.     }
81. }

复制代码

　　综合比较上述两种算法，我们发现，算法1实现的两个栈，每个都只有n/2个空间大小；而算法2实现的两个栈，如果其中一个很小，另一个则可以很大，它们的和为常数n。
 
9..如何用一个数组实现三个栈
　　最后，让我们把抠门儿进行到底，相信看完本文，你已经从物质和精神上都升级为一个抠门儿主义者。
　　如果还使用交叉索引的办法，每个栈都只有N/3个空间。
　　让我们只好使用上个题目的第2个方法，不过这只能容纳2个栈，我们还需要一个位置存放第3个栈，不如考虑数组中间的位置——第3个栈的增长规律可以如下：

第1个入栈C的元素进mid处
第2个入栈C的元素进mid+1处
第3个入栈C的元素进mid-1处
第4个入栈C的元素进mid+2处

　　这个方法的好处是， 每个栈都有接近N/3个空间。

1. public class NewStack
2. {
3.     object[] arr;
4.     int top1;
5.     int top2;
7.     int top3_left;
8.     int top3_right;
9.     bool isLeft;
11.     public NewStack(int capticy)
12.     {
13.         arr = new object[capticy];
15.         top1 = 0;
16.         top2 = capticy;
18.         isLeft = true;
19.         top3_left = capticy / 2;
20.         top3_right = top3_left + 1;
21.     }
23.     public void Push(int type, object element)
24.     {
25.         if (type == 1)
26.         {
27.             if (top1 == top3_left + 1)
28.                 throw new Exception("The stack is full");
30.             arr[top1] = element;
31.             top1++;
32.         }
33.         else if (type == 2)
34.         {
35.             if (top2 == top3_right)
36.                 throw new Exception("The stack is full");
38.             top2--;
39.             arr[top2] = element;
40.         }
41.         else //type==3
42.         {
43.             if (isLeft)
44.             {
45.                 if (top1 == top3_left + 1)
46.                     throw new Exception("The stack is full");
48.                 arr[top3_left] = element;
49.                 top3_left--;
50.             }
51.             else
52.             {
53.                 if (top2 == top3_right)
54.                     throw new Exception("The stack is full");
56.                 arr[top3_right] = element;
57.                 top3_right++;
58.             }
60.             isLeft = !isLeft;
61.         }
62.     }
64.     public object Pop(int type)
65.     {
66.         object obj = null;
68.         if (type == 1)
69.         {
70.             if (top1 == 0)
71.                 throw new Exception("The stack is empty");
72.             else
73.             {
74.                 top1--;
75.                 obj = arr[top1];
76.                 arr[top1] = null;
77.             }
78.         }
79.         else if (type == 2)
80.         {
81.             if (top2 == arr.Length)
82.                 throw new Exception("The stack is empty");
83.             else
84.             {
85.                 obj = arr[top2];
86.                 arr[top2] = null;
87.                 top2++;
88.             }
89.         }
90.         else //type==3
91.         {
92.             if (top3_right == top3_left + 1)
93.                 throw new Exception("The stack is empty");
95.             if (isLeft)
96.             {
97.                 top3_left++;
98.                 obj = arr[top3_left];
99.                 arr[top3_left] = null;
100.             }
101.             else
102.             {
103.                 top3_right--;
104.                 obj = arr[top3_right];
105.                 arr[top3_right] = null;
106.             }
108.             isLeft = !isLeft;
109.         }
111.         return obj;
112.     }
114.     public object Peek(int type)
115.     {
116.         if (type == 1)
117.         {
118.             if (top1 == 0)
119.                 throw new Exception("The stack is empty");
121.             return arr[top1 - 1];
122.         }
124.         else if (type == 2)
125.         {
126.             if (top2 == arr.Length)
127.                 throw new Exception("The stack is empty");
129.             return arr[top2];
130.         }
131.         else //type==3
132.         {
133.             if (top3_right == top3_left + 1)
134.                 throw new Exception("The stack is empty");
136.             if (isLeft)
137.                 return arr[top3_left + 1];
138.             else
139.                 return arr[top3_right - 1];
140.         }
141.     }
142. }

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！