代码随想录Day10

 · 2024-1-5 · 次阅读


代码随想录Day10|

[视频讲解](队列的基本操作! | LeetCode:225. 用队列实现栈_哔哩哔哩_bilibili)

[代码随想录 (programmercarl.com)](代码随想录 (programmercarl.com))

栈-先进后出

队列-先进先出

基本操作

PUSH,POP,isempty(),size(),back(),top(),front().

232栈实现队列

基本思路

一个栈用来入队,一个栈用来出队,逻辑很简单没有太复杂的地方,写代码的时候需要清晰记住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
class MyQueue {
public:
stack<int> IN;
stack<int> OUT;
MyQueue() {

}

void push(int x) {
IN.push(x);
}

int pop() {
if(OUT.empty()){
while(!IN.empty()){
OUT.push(IN.top());
IN.pop();
}
}
int res=OUT.top();
OUT.pop();
return res;
}

int peek() {
int res =this->pop();
OUT.push(res);
return res;
}

bool empty() {
return IN.empty()&&OUT.empty();
}
};

/**
* 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();
* bool param_4 = obj->empty();
*/

225队列实现栈

基本思路

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

在队列的前面弹出一个然后再入队,最后剩下的就是当做栈需要的

过程

1 2 3 4
2 3 4 1
3 4 1 2
4 3 2 1

front 值为4 和压栈是一样的即可实现

代码实现

代码实现要注意在调用的时候需要size-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
class MyStack {
public:
queue<int> que;
MyStack() {

}

void push(int x) {
que.push(x);
}

int pop() {
int size=que.size();
size --;
while(size--){
que.push(que.front());
que.pop();
}
int res= que.front();
que.pop();

return res;
}

int top() {
return que.back();
}

bool empty() {
return que.empty();
}
};

/**
* 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();
* bool param_4 = obj->empty();
*/

总结

今天的知识点比较基础也比较简单,关键是代码得手熟才能完成后面的相关学习,1.5H