【Princeton】算法习题(2):栈与队列

【Princeton】算法习题(2):栈与队列

week2的前半部分面试题(Interview Question)、编程作业(Deques and Randomized Queues)及配套书籍中的部分课后习题详解(仅供参考)。

面试题

  1. 用两个堆栈实现一个队列,而使队列中各操作的成本均为堆栈操作的均摊常量。

    用堆栈A和B实现队列,入队时将元素直接压入栈A;出队时,栈B为空且栈A不为空,则将栈A中的元素依次全部压入栈B中再进行出栈操作,栈B不为空则直接从B出栈。具体实现如下:

    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
    import java.util.LinkedList;

    public class StackQueue<Item> {
    private LinkedList<Item> stackA;
    private LinkedList<Item> stackB;

    public StackQueue() {
    stackA = new LinkedList<>();
    stackB = new LinkedList<>();
    }

    public boolean isEmpty() {
    return stackA.isEmpty() && stackB.isEmpty();
    }

    public void enqueue(Item item) {
    stackA.push(item);
    }

    public int size() {
    return stackA.size() + stackB.size();
    }

    public Item dequeue() {
    if (stackB.isEmpty()) {
    if (stackA.isEmpty())
    throw new NullPointerException("Queue is Empty");
    else {
    while (!stackA.isEmpty())
    stackB.push(stackA.pop());
    }
    }
    return stackB.pop();
    }
    }
  2. 设计一种能够高效地完成入栈、出栈以及返回最大值等操作的数据结构。

    除了A外,另使用一个堆栈B来存储最大值,入栈时,如果栈A为空或入栈元素大于B的栈顶元素,则将该元素同时压入栈B;出栈时,如果A和B的栈顶元素相同,那么该元素需要同时从两个栈中出栈。具体的实现如下:

    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
    import java.util.LinkedList;

    public class MaxStack {
    private LinkedList<Integer> stackA;
    private LinkedList<Integer> stackB;

    public MaxStack() {
    LinkedList<Integer> stackA = new LinkedList<>();
    LinkedList<Integer> stackB = new LinkedList<>();
    }

    public boolean isEmpty() {
    return stackA.isEmpty() && stackB.isEmpty();
    }

    public int size() {
    return stackA.size() + stackB.size();
    }

    public void push(Integer i) {
    if (stackB.isEmpty() || i >= stackB.peek())
    stackB.push(i);

    stackA.push(i);
    }

    public Integer pop() {
    if (stackB.isEmpty())
    throw new NullPointerException("Stack is Empty!!");

    int max = stackB.peek();
    if (stackA.peek() == max)
    stackB.pop();

    return stackA.pop();
    }

    public Integer max() {
    return stackB.peek();
    }
    }
  3. 解释为什么Java中禁止创建泛型数组。

    (参考)为了保证类型安全,向Java数组中插入新元素时都会对元素的类型进行检查,如果元素的类型不匹配则会抛出java.lang.ArrayStoreException错误。而Java中所有的对象都继承自Object,且泛型采用擦除(Erasure)来实现的,即运行过程中元素的类型将被擦除。例如下面的三个容器实际上都是List类型

    1
    2
    3
    List<String> strList = new ArrayList<String>();
    List<Integer> intList = new ArrayList<Integer>();
    List rawList = new ArrayList();

    因此Java中需要采用强制类型转换的方式来创建泛型数组:

    1
    Item[] a = (Item[]) new Object[10];

编程作业:双端、随机队列

描述

实现一个双端队列和一个随机队列,双端队列能够从队头或队尾入队或出队,随机队列则随机选择一个队列的元素出队。

分析

根据两种队列的特点,用双向链表来构建双端队列,随机队列则直接用数组进行实现。

实现

Deque.java

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int n;

private class Node {
private Item item;
private Node prev;
private Node next;
}

public Deque() { // 构造空的双端队列
first = null;
last = null;
n = 0;
}

public boolean isEmpty() { // 队列是否为空
return n == 0;
}

public int size() { // 队列中元素数量
return n;
}

public void addFirst(Item item) { // 从队首添加元素
if (item == null)
throw new java.lang.IllegalArgumentException("item is null!!");

Node oldfirst = first;
first = new Node();
first.item = item;
first.prev = null;

if (oldfirst == null) { // 队列为空
last = first;
first.next = null;
} else { // 队列非空
first.next = oldfirst;
oldfirst.prev = first;
}
n++;
}

public void addLast(Item item) { // 从队尾添加元素
if (item == null)
throw new java.lang.IllegalArgumentException("item is null!!");

Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;

if (oldLast == null) { // 队列为空
first = last;
last.prev = null;
} else { // 队列非空
last.prev = oldLast;
oldLast.next = last;
}
n++;
}

public Item removeFirst() { // 从队首删除
if (isEmpty())
throw new java.util.NoSuchElementException("deque is empty!!");

Item item = first.item;
first = first.next;
n--;

if (isEmpty()) { // 删除后队列为空
last = null;
} else {
first.prev = null;
}

return item;
}

public Item removeLast() { // 从队尾删除
if (isEmpty())
throw new java.util.NoSuchElementException("deque is empty!!");

Item item = last.item;
last = last.prev;
n--;

if (isEmpty()) { // 删除后队列为空
first = null;
} else {
last.next = null;
}

return item;
}

public Iterator<Item> iterator() { // 迭代器
return new DequeIterator();
}

private class DequeIterator implements Iterator<Item> {
private Node current = first;

public boolean hasNext() {
return current != null;
}

public void remove() {
throw new UnsupportedOperationException("remove method is unsupported!!");
}

public Item next() {
if (!hasNext())
throw new NoSuchElementException("deque is empty!!");

Item item = current.item;
current = current.next;

return item;
}
}
}

RandomizedQueue.java

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class RandomizedQueue<Item> implements Iterable<Item> {
private Item[] queue;
private int n;

public RandomizedQueue() { // 构造空的随机队列
queue = (Item[]) new Object[2];
n = 0;
}

public boolean isEmpty() { // 队列是否为空
return n == 0;
}

public int size() { // 队列中元素数量
return n;
}

public void enqueue(Item item) { // 入队
if (item == null)
throw new IllegalArgumentException("item is null!!");

if (n == queue.length)
resize(2 * queue.length); // 动态调整
queue[n++] = item;
}

public Item dequeue() { // 随机出队
if (isEmpty())
throw new NoSuchElementException("RandomizedQuque is empty!!");

int rd = StdRandom.uniform(n); // 生成随机数
Item item = queue[rd];
if (rd != n - 1)
queue[rd] = queue[n - 1]; // 将队尾元素放入随机位置上
queue[n - 1] = null;
n--;

if (n > 0 && n == queue.length / 4) // 动态调整
resize(queue.length / 2);

return item;
}

private void resize(int max) { // 动态调整数组大小
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < n; i++)
temp[i] = queue[i];
queue = temp;
}

public Item sample() { // 随机返回一项
if (isEmpty())
throw new NoSuchElementException("RandomizedQuque is empty!!");

int rd = StdRandom.uniform(n); // 生成随机数

return queue[rd];
}

public Iterator<Item> iterator() {
return new RandomizedQueueIterator();
}

private class RandomizedQueueIterator implements Iterator<Item> {
private Item[] rqueue;
private int current;

public RandomizedQueueIterator() {
rqueue = (Item[]) new Object[n];
current = 0;

for (int k = 0; k < n; k++)
rqueue[k] = queue[k];

StdRandom.shuffle(rqueue); // 随机调整顺序
}

public boolean hasNext() {
return current < n;
}

public void remove() {
throw new UnsupportedOperationException("remove method is unsupported!!");
}

public Item next() {
if (!hasNext())
throw new NoSuchElementException("RandomizedQuque is empty!!");

Item item = rqueue[current];
current++;
return item;
}
}
}

课后习题

1.3.4 编写Stack的用例Parentheses,从标准输入中读取文本流后使用Stack判断其中的括号是否完整匹配。

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
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;

public class Parentheses {
private static final char L_PAREN = '(';
private static final char R_PAREN = ')';
private static final char L_BRACE = '{';
private static final char R_BRACE = '}';
private static final char L_BRACKET = '[';
private static final char R_BRACKET = ']';

public static boolean isBalanced(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == L_PAREN || s.charAt(i) == L_BRACE || s.charAt(i) == L_BRACKET)
stack.push(s.charAt(i));

if (s.charAt(i) == R_PAREN) {
if (stack.isEmpty())
return false;
if (stack.pop() != L_PAREN)
return false;
} else if (s.charAt(i) == R_BRACE) {
if (stack.isEmpty())
return false;
if (stack.pop() != L_BRACE)
return false;
} else if (s.charAt(i) == R_BRACKET) {
if (stack.isEmpty())
return false;
if (stack.pop() != L_BRACKET)
return false;
}
}
return stack.isEmpty();
}

public static void main(String[] args) {
In in = new In();
String s = in.readAll().trim();
StdOut.println(isBalanced(s));
}
}

1.3.9 编写程序,从标准输入得到缺少左括号的数学表达式,输出补全括号后的中序表达式。

使用双栈法,一个栈保存数据,另一个保存运算符,依次遍历输入中的字符,将他们压入相应的栈中。遇到右括号时,两个数字出栈和一个运算符出栈组成带左括号的表达式并压入数据栈,最后用剩余的运算符将栈中各个表达式组合起来。具体实现如下:

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
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class CompleteParentheses {
public static void main(String[] args) {
Stack<String> ops = new Stack<>();
Stack<String> vals = new Stack<> ();

while(!StdIn.isEmpty()) {
String tmp = StdIn.readString();
if (tmp.equals(")")) {
String v2 = vals.pop();
String v1 = vals.pop();
vals.push('(' + v1 + ops.pop() + v2 + ')');
} else if (tmp.equals("+") || tmp.equals("-") || tmp.equals("*") || tmp.equals("/"))
ops.push(tmp);
else
vals.push(tmp);
}

while (ops.size() > 0) {
String v2 = vals.pop();
String v1 = vals.pop();
vals.push('(' + v1 + ops.pop() + v2 + ')');
}

StdOut.println(vals.pop());
}
}

1.3.10 编写程序InfixToPostfix,将算术表达式由中序转为后序。

(参考)

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
public class InfixToPostfix {
public static void main(String[] args) {
Stack<String> ops = new Stack<String>();

while (!StdIn.isEmpty()) {
String str = StdIn.readString();
if (str.equals("("))
ops.push(str);
else if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
boolean isEmpty = ops.isEmpty();
boolean isLeftParen = false;
boolean isLowerOperator = false;

if (!isEmpty) {
String stackTop = ops.peek();
isLeftParen = ops.peek().equals("(");
if ((stackTop.equals("+") || stackTop.equals("-")) && (str.equals("*") || str.equals("/")))
isLowerOperator = true;
}

if (!(isEmpty || isLeftParen || isLowerOperator)) {
while (!ops.isEmpty())
StdOut.print(ops.pop());
}
ops.push(str);
} else if (str.equals(")")) {
while (!ops.isEmpty()) {
String tmp = ops.pop();
if (!tmp.equals("("))
StdOut.print(tmp);
}
} else {
StdOut.print(str);
}
}
StdOut.println();
}
}

参考资料

  1. Algorithms-Coursera
  2. 算法(第四版)

Tip:本文涉及的图片及资料均整理翻译自普林斯顿大学的Robert Sedgewick教授在Coursera上讲授的的Algorithms课程以及他撰写的配套书籍的《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:
2019.07.31 完成初稿

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×