第一篇：数据结构之链表
这次，我们主要看栈和队列的相关题目。
栈是“后进先出”的数据结构，队列是“先进先出”的数据结构，我们假设栈和队列中存储的都是整型数值，先来定义这两种数据结构（都采用数组的形式来存储信息，当达到数组边界时，对数组进行扩容处理）。
栈主要包括Push、Pop和Peek和Count三个方法，如下：
栈的定义
1 public class Stack {
2 private int[] arrValue = null;
3 private int m_Capacity;
4 private int m_Count;
5 private void set_Count(int m_Count) {
6 this.m_Count = m_Count;
7 }
8
9 public int get_Count() {
10 return m_Count;
11 }
12
13 public Stack(int capacity)
14 {
15 m_Capacity = capacity;
16 arrValue = new int[capacity];
17 set_Count(0);
18 }
19
20 public void push(int value)
21 {
22 if (get_Count() == m_Capacity)
23 {
24 System.out.println("Need to malloc more space for stack.");
25 int[] temp = new int[m_Capacity*2];
26 for(int i = 0; i < m_Capacity; i++)
27 {
28 temp[i] = arrValue[i];
29 }
30 arrValue = temp;
31 m_Capacity = m_Capacity*2;
32 System.out.println("The capacity of stack is " + m_Capacity);
33 }
34 set_Count(get_Count() + 1);
35 arrValue[get_Count() - 1] = value;
36
37 }
38
39 public int peek()
40 {
41 if (get_Count() == 0)
42 {
43 System.out.println("Stack is empty;");
44 return Integer.MIN_VALUE;
45 }
46 return arrValue[get_Count() - 1];
47 }
48
49 public int pop()
50 {
51 if (get_Count() == 0)
52 {
53 System.out.println("Stack is empty;");
54 return Integer.MIN_VALUE;
55 }
56 int result = arrValue[get_Count() - 1];
57 set_Count(get_Count() - 1);
58 return result;
59 }
60 }
队列主要包括EnQueue和DeQueue两个方法，如下：
队列的定义
1 public class Queue {
2 private int m_Capacity;
3 private int m_Count;
4 private int[] m_arrValue;
5
6 public Queue(int capacity)
7 {
8 m_Capacity = capacity;
9 m_arrValue = new int[capacity];
10 set_Count(0);
11 }
12
13 public void enQueue(int value)
14 {
15 if (get_Count() == m_Capacity)
16 {
17 System.out.println("Need to malloc more space for queue.");
18 int[] temp = new int[m_Capacity*2];
19 for(int i = 0; i < m_Capacity; i++)
20 {
21 temp[i] = m_arrValue[i];
22 }
23 m_arrValue = temp;
24 m_Capacity = m_Capacity*2;
25 System.out.println("The capacity of queue is " + m_Capacity);
26 }
27 set_Count(get_Count() + 1);
28 m_arrValue[get_Count() - 1] = value;
29 }
30
31 public int deQueue()
32 {
33 if(get_Count() == 0)
34 {
35 System.out.println("The queue is empty.");
36 return Integer.MIN_VALUE;
37 }
38 int result = m_arrValue[0];
39 for (int i = 1; i < get_Count(); i++)
40 {
41 m_arrValue[ i - 1] = m_arrValue[i];
42 }
43 set_Count(get_Count() - 1);
44 return result;
45 }
46
47 private void set_Count(int m_Count) {
48 this.m_Count = m_Count;
49 }
50
51 public int get_Count() {
52 return m_Count;
53 }
54 }
下面，我们来看和这两种数据类型相关的题目。
- 设计含有min函数的栈，要求min、push和pop的时间复杂度是O（1）。
思路：使用一个栈来实现上述要求，在栈顶保存min（）值，每次Push或者Pop，向栈操作两次，第一次针对min，第二次是实际的值，这样我们可以使用Peek方法来取得min值。1 public class NewStack {
2 private int[] m_arrValue = null;
3 private int m_Capacity;
4 private int m_Count;
5
6 public NewStack(int capacity)
7 {
8 m_arrValue = new int[2*capacity];
9 m_Capacity = 2*capacity;
10 m_Count = 0;
11 }
12
13 public void push(int value)
14 {
15 if (m_Count * 2 + 2 > m_Capacity)
16 {
17 System.out.println("Need to malloc more space for stack.");
18 int[] temp = new int[m_Capacity*2];
19 for(int i = 0; i < m_Capacity; i++)
20 {
21 temp[i] = m_arrValue[i];
22 }
23 m_arrValue = temp;
24 m_Capacity = m_Capacity*2;
25 System.out.println("The capacity of stack is " + m_Capacity/2);
26 }
27 int min = Integer.MAX_VALUE;
28 if (m_Count > 0)
29 {
30 min = m_arrValue[2*m_Count - 1];
31 }
32 m_Count++;
33 m_arrValue[2*m_Count -2] = value;
34 m_arrValue[2*m_Count - 1] = min < value ? min : value;
35 }
36
37 public int peek()
38 {
39 if (m_Count == 0)
40 {
41 System.out.println("stack is empty.");
42 return Integer.MIN_VALUE;
43 }
44 return m_arrValue[2*m_Count - 2];
45 }
46
47 public int min()
48 {
49 if (m_Count == 0)
50 {
51 System.out.println("stack is empty.");
52 return Integer.MIN_VALUE;
53 }
54 return m_arrValue[2*m_Count - 1];
55 }
56
57 public int pop()
58 {
59 if (m_Count == 0)
60 {
61 System.out.println("stack is empty.");
62 return Integer.MIN_VALUE;
63 }
64 int result = m_arrValue[2*m_Count - 2];
65 m_Count--;
66 return result;
67 }
68
69 public void set_Count(int m_Count) {
70 this.m_Count = m_Count;
71 }
72
73 public int get_Count() {
74 return m_Count;
75 }
76 }上述代码是从头开始实现的栈，包括对存储结构的处理细节，我们可以看上面关于Stack的定义，其实已经包括了这些细节，因此我们可以直接拿来用，代码会更清晰。
1 public class NewStack2 {
2 private Stack stack;
3
4 public NewStack2(int capacity)
5 {
6 stack = new Stack(capacity*2);
7 }
8
9 public void push(int value)
10 {
11 if(stack.get_Count() == 0)
12 {
13 stack.push(value);
14 stack.push(value);
15 }
16 else
17 {
18 int min = stack.peek();
19 stack.push(value);
20 stack.push(value > min ? min : value);
21 }
22 }
23
24 public int min()
25 {
26 return stack.peek();
27 }
28
29 public int pop()
30 {
31 stack.pop();
32 return stack.pop();
33 }
34
35 public int get_Count()
36 {
37 return stack.get_Count()/2;
38 }
39 } - 用两个栈实现一个队列
思路：两个栈一个作为入值栈，一个作为出值栈，当执行Push操作时，将值压入入值栈，当执行Pop或者Peek操作时，取出值栈的栈顶元素，当出值栈为空时，需要将入值栈的元素依次压入出值栈。1 public class NewQueue {
2 private Stack inStack;
3 private Stack outStack;
4
5 public NewQueue(int capacity)
6 {
7 inStack = new Stack(capacity);
8 outStack = new Stack(capacity);
9 }
10
11 public void enQueue(int value)
12 {
13 inStack.push(value);
14 }
15
16 public int deQueue()
17 {
18 if(inStack.get_Count() == 0 && outStack.get_Count() == 0)
19 {
20 System.out.println("The queue is empty.");
21 return Integer.MIN_VALUE;
22 }
23 if (outStack.get_Count() == 0)
24 {
25 while(inStack.get_Count() > 0)
26 {
27 outStack.push(inStack.pop());
28 }
29 }
30 return outStack.pop();
31 }
32
33 public int get_Count()
34 {
35 return inStack.get_Count() + outStack.get_Count();
36 }
37 } - 用两个队列实现一个栈
思路：根据“后进先出”和“先进后出”的特点，在运行过程中，其中一个队列应该一直为空，对于push操作，将值放到非空队列中，当进行Push或者Pop操作时，先将非空队列全部导入空队列，然后此时的非空队列的头元素就是我们期望的元素。1 public class NewStack3 {
2
3 private Queue queue1;
4 private Queue queue2;
5
6 public NewStack3(int capacity)
7 {
8 queue1 = new Queue(capacity);
9 queue2 = new Queue(capacity);
10 }
11
12 public void push(int value)
13 {
14 if (queue1.get_Count() == 0)
15 {
16 queue2.enQueue(value);
17 }
18 else
19 {
20 queue1.enQueue(value);
21 }
22 }
23
24 public int peek()
25 {
26 if (queue1.get_Count() == 0 && queue2.get_Count() == 0)
27 {
28 System.out.println("The stack is empty.");
29 return Integer.MIN_VALUE;
30 }
31 int result = Integer.MIN_VALUE;
32 if (queue1.get_Count() > 0 && queue2.get_Count() == 0)
33 {
34 while(queue1.get_Count() > 1)
35 {
36 queue2.enQueue(queue1.deQueue());
37 }
38 result = queue1.deQueue();
39 queue2.enQueue(result);
40 }
41 else if (queue1.get_Count() == 0 && queue2.get_Count() > 0)
42 {
43 while(queue2.get_Count() > 1)
44 {
45 queue1.enQueue(queue2.deQueue());
46 }
47 result = queue2.deQueue();
48 queue1.enQueue(result);
49 }
50
51 return result;
52 }
53
54 public int pop()
55 {
56 if (queue1.get_Count() == 0 && queue2.get_Count() == 0)
57 {
58 System.out.println("The stack is empty.");
59 return Integer.MIN_VALUE;
60 }
61 int result = Integer.MIN_VALUE;
62 if (queue1.get_Count() > 0 && queue2.get_Count() == 0)
63 {
64 while(queue1.get_Count() > 1)
65 {
66 queue2.enQueue(queue1.deQueue());
67 }
68 result = queue1.deQueue();
69 }
70 else if (queue1.get_Count() == 0 && queue2.get_Count() > 0)
71 {
72 while(queue2.get_Count() > 1)
73 {
74 queue1.enQueue(queue2.deQueue());
75 }
76 result = queue2.deQueue();
77 }
78
79 return result;
80 }
81
82 public int get_Count()
83 {
84 return queue1.get_Count() + queue2.get_Count();
85 }
86 } - 递归反转一个栈，要求不能重建一个新栈，空间复杂度为O(1)。
思路：参考汉诺塔的递归思路。1 public static void Reverse(Stack stack)
2 {
3 if (stack.get_Count() == 0)
4 {
5 return;
6 }
7 int value1 = stack.pop();
8 Reverse(stack);
9 if (stack.get_Count() == 0)
10 {
11 stack.push(value1);
12 return;
13 }
14 int value2 = stack.pop();
15 Reverse(stack);
16 stack.push(value1);
17 Reverse(stack);
18 stack.push(value2);
19 } - 对栈进行排序
思路：依旧采取递归的套路1 public static void sort(Stack stack)
2 {
3 if (stack.get_Count() == 0)
4 {
5 return;
6 }
7 int value1 = stack.pop();
8 sort(stack);
9 if (stack.get_Count() == 0)
10 {
11 stack.push(value1);
12 return;
13 }
14 int value2 = stack.pop();
15 if (value1 > value2)
16 {
17 stack.push(value1);
18 sort(stack);
19 stack.push(value2);
20 }
21 else
22 {
23 stack.push(value2);
24 sort(stack);
25 stack.push(value1);
26 }
27 } - 判断栈的push、pop序列是否一致
思路：创建一个新栈，依次将push队列中的值压入，在压入过程中，判断pop队列，如果找到相同的值，执行stack.pop操作，以此类推，最终判断stack是否为空。1 public static boolean isMatch(int[] arrPush, int[] arrPop)
2 {
3 if (arrPush == null || arrPop == null || arrPush.length != arrPop.length)
4 {
5 return false;
6 }
7 Stack stack = new Stack(arrPush.length);
8 for(int i = 0, j = 0; i < arrPush.length; i++)
9 {
10 stack.push(arrPush[i]);
11 while(j < arrPop.length)
12 {
13 if (stack.peek() == arrPop[j])
14 {
15 stack.pop();
16 j++;
17 }
18 else
19 {
20 break;
21 }
22 }
23 }
24
25 return stack.get_Count() == 0;
26 } - 如何用一个数组实现两个栈
思路：用0、2、4、6……表示第一个栈的元素，用1、3、5、7表示第二个栈的元素1 public class NewStack4 {
2 private int[] arrValue;
3 private int capacity;
4 private int m_Count1;
5 private int m_Count2;
6
7 public NewStack4(int capacity)
8 {
9 arrValue = new int[capacity];
10 this.capacity = capacity;
11 m_Count1 = 0;
12 m_Count2 = 0;
13 }
14
15 public void push(int value, int type)
16 {
17 boolean bExtend = false;
18 if (type == 1)
19 {
20 if (m_Count1 * 2 + 1 >= capacity)
21 {
22 bExtend = true;
23 }
24 }
25 if (type == 2)
26 {
27 if (m_Count2 * 2 + 2 >= capacity)
28 {
29 bExtend=true;
30 }
31 }
32 if (bExtend)
33 {
34 int[] temp = new int[capacity*2];
35 capacity = capacity*2;
36 for(int i = 0; i < arrValue.length; i++)
37 {
38 temp[i] = arrValue[i];
39 }
40 arrValue = temp;
41 }
42
43 if (type == 1)
44 {
45 m_Count1++;
46 arrValue[m_Count1*2 - 1] = value;
47 }
48
49 if (type == 2)
50 {
51 m_Count2++;
52 arrValue[m_Count2*2] = value;
53 }
54 }
55
56 public int peek(int type)
57 {
58 if (type == 1)
59 {
60 if (m_Count1 == 0)
61 {
62 System.out.println("Stack 1 is empty.");
63 return Integer.MIN_VALUE;
64 }
65 else
66 {
67 return arrValue[m_Count1*2 - 1];
68 }
69 }
70 if (type == 2)
71 {
72 if (m_Count2 == 0)
73 {
74 System.out.println("Stack 1 is empty.");
75 return Integer.MIN_VALUE;
76 }
77 else
78 {
79 return arrValue[m_Count2*2];
80 }
81 }
82
83 return Integer.MIN_VALUE;
84 }
85
86 public int pop(int type)
87 {
88 if (type == 1)
89 {
90 if (m_Count1 == 0)
91 {
92 System.out.println("Stack 1 is empty.");
93 return Integer.MIN_VALUE;
94 }
95 else
96 {
97 int result = arrValue[m_Count1*2 - 1];
98 m_Count1--;
99 return result;
100 }
101 }
102 if (type == 2)
103 {
104 if (m_Count2 == 0)
105 {
106 System.out.println("Stack 1 is empty.");
107 return Integer.MIN_VALUE;
108 }
109 else
110 {
111 int result =arrValue[m_Count2*2];
112 m_Count2--;
113 return result;
114 }
115 }
116
117 return Integer.MIN_VALUE;
118 }
119
120 public int get_Count(int type)
121 {
122 if (type == 1)
123 {
124 return m_Count1;
125 }
126 else if (type == 2)
127 {
128 return m_Count2;
129 }
130 return Integer.MIN_VALUE;
131 }
132
133 }这种方式在两个栈的容量接近时比较好，如果两个栈的容量相差很大， 那么会浪费很多存储空间。针对这个问题的解决方法是用0、1、2、3……表示第一个栈，用n、n-1、n-2、n-3……表示第二个栈，代码实现类似，这种情况下也可以对数组进行扩容。
最后，欢迎大家提出更多相关的面试题目，我们可以一起讨论。