844 比较含退格的字符串
实时变换字符串，注意退格符超过string长度的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public boolean backspaceCompare(String s, String t) {
String sB = getFinalString(s);
String tB = getFinalString(t);
return sB.equals(tB);
}
private String getFinalString(String s){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++){
if (s.charAt(i) != '#'){
sb.append(s.charAt(i));
} else {
sb.delete(sb.length() == 0 ? 0 :sb.length() - 1, sb.length());
}
}
return sb.toString();
}
}
|
栈与队列理论基础
队列，先进先出
栈， 先进后出
栈，push(), pop(),top();
注意deque是双向队列，封住一端，可以成为栈
232 用栈实现队列
push(x) 放入队列尾部
pop() 从队列首部移除元素
peek() 返回队列首部元素
empty() 返回队列是否为空
Java 创建栈的方法 Stack
栈的使用方法
.push(x) 放入栈
.pop() 退出栈
.peek() 返回栈顶元素
.isEmpty() 栈是否为空
用栈实现队列，需要两个栈，一个栈进，一个栈出
如果队列要pop就要把栈进元素推进栈出，然后pop出来元素
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 {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
public MyQueue() {
this.stackIn = new Stack<>();
this.stackOut = new Stack<>();
}
public void push(int x) {
stackIn.push(x);
}
public int pop() {
dumpInStackOut();
return stackOut.pop();
}
public int peek() {
dumpInStackOut();
return stackOut.peek();
}
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
private void dumpInStackOut(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
|
225 用队列实现栈
push(x) 元素x入栈
pop() 移除栈顶元素
top() 获取栈顶元素
empty() 返回栈是否为空
两个队列实现
用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
先把新元素推入q2之后把q1推到q2，之后q1 q2交换
LinkedList Queue用法
.offer(x) 尾部添加元素
.isEmpty() 队列是否为空
.poll() 头部推出元素
.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
| class MyStack{
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack(){
queue1 = new LinkedList();
queue2 = new LinkedList();
}
public void push(int x){
queue2.offer(x);
while (!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
Queue<Integer> queueTemp = queue1;
queue1 = queue2;
queue2 = queueTemp;
}
public int pop(){
return queue1.poll();
}
public int top(){
return queue1.peek();
}
public boolean empty(){
return queue1.isEmpty();
}
}
|
两个ArrayDeque 但是实际是两个Queue
ArrayDeque queue 用法
.add(int x) 尾部添加元素
.poll() 推出头部元素
.peek() 返回头部元素
.isEmpty() 队列是否为空
先把q1 推到q2 之后q1推入新元素，再之后把q2推入q1完成队列
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
|
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
public MyStack(){
queue1 = new ArrayDeque<>();
queue2 = new ArrayDeque<>();
}
public void push(int x){
while (!queue1.isEmpty()){
queue2.add(queue1.poll());
}
queue1.add(x);
while (!queue2.isEmpty()){
queue1.add(queue2.poll());
}
}
public int pop(){ return queue1.poll();}
public int top(){ return queue1.peek();}
public boolean empty() {return queue1.isEmpty();}
}
|
两个Deque实现
.addLast();
.pollFirst();
.peekFirst();
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
| class MyStack {
Deque<Integer> que1;
Deque<Integer> que2;
public MyStack() {
que1 = new ArrayDeque<>();
que2 = new ArrayDeque<>();
}
public void push(int x) {
que1.addLast(x);
}
public int pop() {
int size = que1.size();
size--;
while (size-- > 0) {
que2.addLast(que1.peekFirst());
que1.pollFirst();
}
int res = que1.pollFirst();
que1 = que2;
que2 = new ArrayDeque<>();
return res;
}
public int top() {
return que1.peekLast();
}
public boolean empty() {
return que1.isEmpty();
}
}
|
一个Deque实现
调整q1顺序，把最后的元素推出
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 MyStack {
Deque<Integer> que1;
Deque<Integer> que2;
public MyStack() {
que1 = new ArrayDeque<>();
}
public void push(int x) {
que1.addLast(x);
}
public int pop() {
int size = que1.size();
size--;
while (size-- > 0) {
que1.addLast(que1.peekFirst());
que1.pollFirst();
}
int res = que1.pollFirst();
return res;
}
public int top() {
return que1.peekLast();
}
public boolean empty() {
return que1.isEmpty();
}
}
|
一个队列实现
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
把新元素推入queue之后，重新排列，把新元素推到顶上
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
| class MyStack{
Queue<Integer> queue;
pulic MyStack(){
queue = new LinkedList<>();
}
public void push(int x){
queue.offer(x);
int size = queue.size();
while (size-- > 1){
queue.offer(queue.poll());
}
}
public int pop(){
return queue.poll();
}
public int top(){
return queue.peek();
}
public boolean empty(){
return queue.isEmpty();
}
}
|