栈和队列

Posted on | In | Visitors:

1.用两个栈实现一个队列

问题描述：

用两个栈实现一个队列。队列的声明如下：实现它的两个函数 appendChild 和 deleteChild，分别在队列尾部插入结点和在队列头部删除结点的功能。

思路：

enter image description here

  • 往队列中插入元素：放入 stack1；

  • 从队列中删除元素：

    • 当 stack2 不为空时，在 stack2 栈顶的元素弹出，作为被删除元素；
    • 当 stack2 为空，把 stack1 的元素依次 pop 再 push 到stack2 中，然后在 stack2 栈顶的元素弹出，作为被删除元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.Stack;
public class QueueImplementByTwoStacks {
	QueueImplementByTwoStacks() {
		Stack<Intager> stack1 = new Stack<Integar> ();
		Stack<Integar> stack2 = new Stack<Intager> ();
	}
	
	public void push(int node) {  //入队列
		stack1.push(node);  
		return;
	}
	public int pop() {    //出队列
		if (stack2.size() <= 0) {
			while (stack1.size > 0) {
				int data = stack1.peek();  //查看栈顶元素，但不移除它
				stack1.pop();  //弹出 stack1 中元素
				stack2.push(data);  //压入 stack2 中
			}
		}
		if (stack2.size() == 0) {
			try {
				throw new Exception("queue is empty")
			} catch (Exception e) {
			}
		}
		//删完指定队列头
		int head = stack2.peek();
		//删
		stack2.pop();
		return head;	
	}
	public static void main (String[] args) {
		QueueImplementByTwoStacks queue = new QueueImplementByTwoStacks();
		List<Integrr> result = new ArrayList<Integer>();
		queue.push(1);
		queue.push(2);
		queue.push(3);
		result.add(queue.pop());
		queue.push(4);
		result.add(queue.pop());
		queue.push(5);
		result.add(queue.pop());
		result.add(queue.pop());
		result.add(queue.pop());
		System.out.println(result.toString());
	}
}

2.用两个队列实现一个栈

思路：

enter image description here

  • 入队列时，

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Queue;
import java.util.ArrayDeque;
public class StackImplementByTwoQueues {
	Queue<Integer> queue1 = new ArrayDeque<>();
	Queue<Integer> queue2 = new ArrayDeque<>();
	public void push(int node) {
		//两个队列都为空时，优先放入 queue1
		if (queue1.isEmpty() && queue2.isEmpty()) {
			queue1.add(node);
			return;
		}
		//如果 queue1为空，queue2非空，放入queue2
		if (queue1.isEmpty()) {
			queue2.add(node);
			return;
		}
		if (queue2.isEmpty()) {
			queue1.add(node);
			return;
		}
	}
	public int pop() {
		//两个队列都为空时，异常
		if (queue1.isEmpty() && queue2.isEmpty) {
			try {
				throw new Exception("stack is empty");
			} catch (Exception e) {
			}
		}
		
		//如果 queue1为空，queue2 非空，将 queue2 除待删除元素外的元素依次放入 queue1 中
		if (queue1.isEmpty()) {
			while (queue2.size > 1) {
				queue1.add(queue2.poll());
			}
			// pop
			return queue2.poll();
		}
		if (queue2.isEmpty()) {
			while (queue1.size > 1) {
				queue2.add(queue1.poll());
			}
			// pop
			return queue1.poll();
		}
	}
	public static void main(String[] args) {
	StackImplementByTwoQueues stack = new StackImplementByTwoQueues();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    stack.push(5);
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());	
	}
}

3.包含 min 函数的栈

问题描述：

定义栈的数据结构，在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O（1）。

思路：

再用一个辅助栈。
当向栈中添加元素时，与辅助栈中元素比较：

  • 如果小，向辅助栈中添加该元素，
  • 否则向辅助栈中再次添加辅助栈栈顶元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Stack;
public class StackWithMin {
	private static Stack<Integer> stack1;
	private static Stack<Integer> stack2;  //辅助栈，存放最小值
	public static void push(Integer i) {
		stack1.push(i);
		if (stack1.size == 0 || i < stack2.peek()) {
			stack2.push(i);
		}
		else {
			stack2.push(stack2.peek());
		}
	}
	public static void pop() {
		if (stack1.size() > 0 && stack2.size() > 0) {
			stack2.pop();
			stack1.pop();
		}
	}
	public static int min() {
		if (stack1.size() > 0 && stack2.size() > 0) {
			return stack2.peek();
		}
	}
	public static void main(String[] args) {
		push(3);
        System.out.println(min());
        push(4);
        System.out.println(min());
        push(2);
        System.out.println(min());
        push(1);
        System.out.println(min());
        pop();
        System.out.println(min());
        pop();
        System.out.println(min());
        push(0);
        System.out.println(min());
	}
}

4.栈的压入、弹出序列

问题描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如：
序列 1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列。但4、3、5、1、2就不可能是该压栈序列的弹出序列。

思路：

  • 建立一个辅助栈，把序列一的数字依次压入辅助栈，并按照序列二的顺序依次从该栈中弹出数字。

  • 遍历序列一，判断序列二是不是栈的弹出序列：

    • 向栈中压入序列一的数值；
    • 如果下一个要弹出的数字刚好是栈顶数字，那么直接弹出；
    • 如果下一个弹出的数字不在栈顶，我们把序列一中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。
    • 如果所有的数字都压入栈了，仍然没有找到下一个要弹出的数字，那么该序列不是一个弹出序列。
    • 反之，如果是弹出序列，则辅助栈最后应为空。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Stack;
public class eg22 {
	poblic static boolean idPopOrder(int[] pushA, int[] popA) {
		if (pushA == null || popA == null || pushA.length != popA.length) {
			return false;
		}
		Stack<Integer> stack = new Stack<>();
		boolean isPossible = false;
		int pushIndex;
		int popIndex = 0;
		for (pushIndex = 0; pushIndex < pushA.length; pushIndex++) {
			stack.push(pushA[pushIndex]);
			while (!stack.isEmpty() && stack.peek() == popA[popIndex]) {
				stack.pop();
				popIndex++;
			}
		}
		if (stack.isEmpty()) {
			isPossible = true;
		}
		return isPossible;
	}
}

5.滑动窗口的最大值

问题描述：

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如：
如果给定数组 {2，3，4，2，6，2，5，1} 及滑动窗口的大小3，那么一共存在 6 个滑动窗口，她们的最大值分别是{4，4，6，6，6，5}。

思路：

  • 把有可能成为滑动窗口最大值的数值 存储到一个双端队列 deque 中。
    • 为了知道一个数字是否还包括在当前的滑动窗口中，应该在队列里存储数组元素的下标，而非数值本身。当一个数字的下标与当前处理的数字的下标之差大于等于滑动窗口大小时，这个数字就可以从滑动窗口中滑出了。

处理过程：

  1. 如果新来的数值比队列尾部的数小，那就追加到后面，因为它可能在前面的最大值滑出窗口后成为最大值；
  2. 如果新来的数值比队列尾部的数大，那就删掉尾部，再追加到后面，循环下去直到小于；
  3. 如果追加的值的索引与队列头部的值的索引之差，超过窗口大小，那就删掉头部的值；
  4. 这样每次队列头部都是最大的那个。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class eg65 {
	public ArrayList<Integer> maxInWindows(int[] num, int size) {
		ArrayList<Integer> result = new ArrayList<>();
		if (num == null || num.length < size || size < 1) {
			return result;
		}
		//双向队列，保存可能成为窗口最大值的数值的下标
		Deque<Integer> deque = new ArrayDeque<>();
		for (int i = 0; i < num.length; i++) {
			//如果队列头部元素已经滑出窗口，删除
			if (!deque.isEmpty && (i - deque.peekFirst()) >= size) {
				deque.pollFirst();
			}
			//如果新来的数值比队列尾部数值大，删掉尾部数值
			if (!deque.isEmpty() && num[i] > num[deque.getLast()]) {
				deque.pollLast();
			}
			deque.addlast(i);
			//如果遍历的元素已经达到一个滑动窗口大小，久提取窗口最大值
			if (i >= (size - 1)) {
				result.add(num[deque.peekFirst()]);
			}
		}
		return result;
	}
}