随想录日记part8
t
i
m
e
：
time：
time： 2024.03.01
主要内容：今天的主要内容是了解数据结构中栈和队列的了解，并通过两个简单的例子加深对基础知识的认识。
- 理论基础
- 232.用栈实现队列
- 225. 用队列实现栈
Topic1理论基础
队列(
Q
u
e
u
e
Queue
Queue)：先进先出 栈(
S
t
a
c
k
Stack
Stack)： 先进后出，如图所示：
- java中队列(
Q
u
e
u
e
Queue
Queue)的相关函数：
//创建队列
QueueInteger> q = new LinkedList>();
//插入元素1
q.offer(1);
// 获取元素个数
q.size();
// 获取队头元素,但不删除元素
q.peek();
//移除元素，将元素从队头移出并将删除的元素返回
q.poll();
//判断队列是否为空
q.isEmpty()；
- java中栈(
S
t
a
c
k
Stack
Stack)的相关函数：
//创建栈
StackInteger> stack = new Stack>();
//入栈
stack.push(1);
//得到栈的大小
stack.size());
//获取栈顶元素,但是不出栈,栈中元素不变
stack.peek());
//出栈
stack.pop();
// 判断栈中是否为空
stack.isEmpty());
Topic2用栈实现队列
题目：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
p
u
s
h
、
p
o
p
、
p
e
e
k
、
e
m
p
t
y
push、pop、peek、empty
push、pop、peek、empty）：
实现
M
y
Q
u
e
u
e
MyQueue
MyQueue 类：
v
o
i
d
p
u
s
h
(
i
n
t
x
)
void push(int x)
voidpush(intx) 将元素
x
x
x 推到队列的末尾
i
n
t
p
o
p
(
)
int pop()
intpop() 从队列的开头移除并返回元素
i
n
t
p
e
e
k
(
)
int peek()
intpeek() 返回队列开头的元素
b
o
o
l
e
a
n
e
m
p
t
y
(
)
boolean empty()
booleanempty() 如果队列为空，返回t
r
u
e
true
true ；否则，返回
f
a
l
s
e
false
false
解释:
- 你只能使用标准的栈操作 —— 也就是只有
p
u
s
h
t
o
t
o
p
,
p
e
e
k
/
p
o
p
f
r
o
m
t
o
p
,
s
i
z
e
,
和
i
s
e
m
p
t
y
push to top, peek/pop from top, size, 和 is empty
pushtotop,peek/popfromtop,size,和isempty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用
l
i
s
t
list
list 或者
d
e
q
u
e
deque
deque（双端队列）来模拟一个栈，只要是标准的栈操作即可
示例：
输入:
[
”
M
y
Q
u
e
u
e
”
,
”
p
u
s
h
”
,
”
p
u
s
h
”
,
”
p
e
e
k
”
,
”
p
o
p
”
,
”
e
m
p
t
y
”
]
[
[
]
,
[
1
]
,
[
2
]
,
[
]
,
[
]
,
[
]
]
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []]
[“MyQueue“,“push“,“push“,“peek“,“pop“,“empty“][[],[1],[2],[],[],[]]
输出:
[
n
u
l
l
,
n
u
l
l
,
n
u
l
l
,
1
,
1
,
f
a
l
s
e
]
[null, null, null, 1, 1, false]
[null,null,null,1,1,false]
思路：
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。如下图：
java实现的代码如下：
class MyQueue {
StackInteger> s_in;
StackInteger> s_out;
public MyQueue() {
s_in = new Stack>(); // 负责进栈
s_out = new Stack>(); // 负责出栈
}
// 进队列
public void push(int x) {
s_in.push(x);
}
// 出队列
public int pop() {
in_to_out();
return s_out.pop();
}
// 获取队头元素,但不删除元素
public int peek() {
in_to_out();
return s_out.peek();
}
// 判断是否队列为空
public boolean empty() {
if (!s_in.isEmpty() || !s_out.isEmpty())
return false;
return true;
}
private void in_to_out() {
if (!s_out.isEmpty())
return;
while (!s_in.isEmpty()) {
s_out.push(s_in.pop());
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
Topic3用队列实现栈
题目：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
p
u
s
h
、
t
o
p
、
p
e
e
k
、
e
m
p
t
y
push、top、peek、empty
push、top、peek、empty）：
实现
M
y
S
t
a
c
k
MyStack
MyStack 类：
v
o
i
d
p
u
s
h
服务器托管网
(i
n
t
x
)
void push(int x)
voidpush(intx) 将元素
x
x
x压入栈顶
i
n
t
p
o
p
(
)
int pop()
intpop() 移除并返回栈顶元素
i
n
t
p
e
e
k
(
)
int peek()
intpeek() 返回栈顶元素
b
o
o
l
e
a
n
e
m
p
t
y
(
)
boolean empty()
booleanempty() 如果栈为空，返回
t
r
u
e
true
true ；否则，返回
f
a
l
s
e
false
false
解释:
- 你只能使用标准的队列操作 —— 也就是只有
p
u
s
h
t
o
t
o
p
,
p
e
e
k
/
p
o
p
f
r
o
m
f
r
o
n
t
,
s
i
z
e
,
和
i
s
e
m
p
t
y
push to top, peek/pop from front, size, 和 is empty
pushtotop,peek/popfromfront,size,和isempty 操作是合法的。
- 你所使用的语言也许不支持队列。你可以使用
l
i
s
t
list
list 或者
d
e
q
u
e
deque
deque（双端队列）来模拟一个栈，只要是标准的栈操作即可
示例：
输入:
[
”
M
y
Q
u
e
u
e
”
,
”
p
u
s
h
”
,
”
p
u
s
h
”
,
”
p
e
e
k
”
,
”
p
o
p
”
,
”
e
m
p
t
y
”
]
[
[
]
,
[
1
]
,
[
2
]
,
[
]
,
[
]
,
[
]
]
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []]
[“MyQueue“,“push“,“push“,“peek“,“pop“,“empty“][[],[1],[2],[],[],[]]
输出:
[
n
u
l
l
,
n
u
l
l
,
n
u
l
l
,
2
,
2
,
f
a
l
s
e
]
[null, null, null, 2, 2, false]
[null,null,null,2,2,false]
思路：
要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！如下面动画所示，用两个队列
q
u
e
1
que1
que1 和
q
u
e
2
que2
que2 实现队列的功能，
q
u
e
2
que2
que2 其实完全就是一个备份的作用，把
q
u
e
1
que1
que1 最后面的元素以外的元素都备份到
q
u
e
2
que2
que2，然后弹出最后面的元素，再把其他元素从
q
u
e
2
que2
que2 导回
q
u
e
1
que1
que1。
java实现的代码如下：
class MyStack {
QueueInteger> q1;
QueueInteger> q2;
public MyStack() {
q1 = new LinkedList>();// 负责进栈
q2 = new LinkedList>();// 负责辅助出栈
}
// 进栈
public void push(int x) {
q2.offer(x);
while (!q1.isEmpty()) {
q2.offer(q1.poll());
}
QueueInteger> tem;
tem = q1;
q1 = q2;
q2 = tem;
}
// 出栈
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
