数据结构和算法-栈和队列

Stack(栈)

栈的特点是:First In Last Out(FILO)

栈的实现有:数组或链表

相关API

  • push(E item):将一个元素压入栈
  • pop():将栈顶元素弹出
  • peek():返回栈顶元素,但不弹出(英文的意思是偷看)

Leetcode

No20.判断括号是否有效

给定一个字符串只包含如下字符: '(', ')', '{', '}', '[' and ']' ,判断输入的字符串是否有效。验证规则如下:

  • 开括号必须用相同类型的括号关闭
  • 开括号必须以正确的顺序关闭

请注意,空字符串也被视为有效。

可能的解

使用栈的方式实现。

代码实现
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
public static boolean isValid(String s) {
if (s == null || s.length() == 0) {
return true;
}

Map<Character, Character> mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put(']', '[');
mapping.put('}', '{');

Stack<Character> stack = new Stack<>();

char[] chars = s.toCharArray();
for (char c : chars) {
if (mapping.containsKey(c)) {
if (stack.empty()) {
return false;
}
if (stack.pop() != mapping.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.empty();
}

复杂度分析:

时间复杂度:O(n),需要遍历一次给定的字符。空间复杂度:O(n),最坏的情况下,需要将所有字符串都进行一次push()。

No232.使用栈来实现队列

使用栈来实现队列的如下操作:

  • push(x) – 将一个元素放入队列的尾部。
  • pop() – 从队列首部移除元素。
  • peek() – 返回队列首部的元素。
  • empty() – 返回队列是否为空。

说明:

  • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
代码实现
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
class MyQueue {
private Stack<Integer> inputStack;
private Stack<Integer> outputStack;

/** Initialize your data structure here. */
public MyQueue() {
inputStack = new Stack<>();
outputStack = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
inputStack.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(outputStack.empty()) {
while(!inputStack.empty()) {
outputStack.push(inputStack.pop());
}
}
return outputStack.pop();
}

/** Get the front element. */
public int peek() {
if(outputStack.empty()) {
while(!inputStack.empty()) {
outputStack.push(inputStack.pop());
}
}
return outputStack.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return inputStack.empty() && outputStack.empty();
}
}

复杂度分析:

时间复杂度:O(n)。

Queue(队列)

队列的特点是:First In First Out(FIFO)

队列的实现有:数组或链表

相关API

  • offer(E item):将一个元素入队。
  • poll():移除队列首部元素。
  • peek():返回队列首部元素。
  • isEmpty():判断队列是否为空。
  • size():返回队列长度。

Leetcode

No225.用队列实现栈

代码实现
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
class MyStack {
Queue<Integer> in;
Queue<Integer> out;

/** Initialize your data structure here. */
public MyStack() {
in = new LinkedList<>();
out = new LinkedList<>();
}

/** Push element x onto stack. */
public void push(int x) {
in.offer(x);
while(!out.isEmpty()) {
in.offer(out.poll());
}
Queue temp =in;
in = out;
out = temp;
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
return out.poll();
}

/** Get the top element. */
public int top() {
return out.peek();
}

/** Returns whether the stack is empty. */
public boolean empty() {
return out.isEmpty();
}
}

复杂度分析:

时间复杂度:O(n)。空间复杂度:O(n)。

0%