【剑指offer】-两个栈来实现一个队列-05/67

@TOC

一 题目描述

用两个栈来实现一个队列,完成队列的Push和Pop操作( 队列中的元素为int类型)。

二 题目分析

(一)题目思路

  1. 用两个栈实现一个队列的功能?
    入队:将元素进栈A
    出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;如果不为空,栈B直接出栈。
  2. 用两个队列实现一个栈的功能?
    入栈:将元素进队列A
    出栈:判断队列A中元素的个数是否为1,如果等于1,则出队列,否则将队列A中的元素 以此出队列并放入队列B,直到队列A中的元素留下一个,然后队列A出队列,再把 队列B中的元素出队列以此放入队列A中。

(二)栈和队列的解释

  1. 队列(Queue):是限定只能在表的一端进行插入和另一端删除操作的线性表
  2. 栈(Stack):是限定只能在表的一端进行插入和删除操作的线性表

(三)队列和栈的规则

  1. 队列:先进先出
  2. 栈:先进后出

(四)队列和栈的遍历数据速度

  1. 队列:基于地址指针进行遍历,而且可以从头部或者尾部进行遍历,但不能同时遍历,无需开辟空间,因为在遍历的过程中不影响数据结构,所以遍历速度要快
  2. 栈:只能从顶部取数据,也就是说最先进入栈底的,需要遍历整个栈才能取出来,遍历数据时需要为数据开辟临时空间,保持数据在遍历前的一致性

(五)Java和C++中栈和队列的区别

1 Java栈和队列

1.1 栈的创建方法(Stack)

  • 创建方法: Stack<Integer> stack1 = new Stack<Integer>();

1.2 Stack类中的方法

1
2
3
4
5
6
Object push(Object element):将元素推送到堆栈顶部。
Object pop():移除并返回堆栈的顶部元素。如果我们在调用堆栈为空时调用pop(),则抛出’EmptyStackException’异常。
Object peek():返回堆栈顶部的元素,但不删除它。
boolean empty():如果堆栈顶部没有任何内容,则返回true。否则,返回false
int search(Object element):确定对象是否存在于堆栈中。如果找到该元素,它将从堆栈顶部返回元素的位置。否则,它返回-1
Object size() : 代表栈中含有多少个元素

1.3. 队列的创建方法(Queue)

  • 创建方法: Queue<Integer> queue = new LinkedList<>();

1.4. Queue类中的方法**

1
2
3
4
5
offer(element: E): boolean     插入一个元素到队列中
poll(): E 获取并移除队列的头元素,如果队列空则返回null
remove(): E 获取并移除队列头元素,如果队列空则抛出异常
peek(): E 获取但不移除队列头元素,如果队列为空则返回null
element(): E 获取但不移除队列头元素,如果队列为空则抛出异常

2 C++栈和队列

2.1. 栈的创建方法(Stack)

  • 创建方法: stack<int> stack1;

    2.2 Stack类中的方法

    1
    2
    3
    4
    5
    push(): 向栈内压入一个成员;
    pop(): 从栈顶弹出一个成员;
    empty(): 如果栈为空返回true,否则返回false
    top(): 返回栈顶,但不删除成员;
    size(): 返回栈内元素的大小;

    2.3 队列的创建方法(Queue)

  • 创建方法: queue<int> q;

2.4 Queue类中的方法

1
2
3
4
5
入队:q.push(x); 将x 接到队列的末端。
出队:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
访问队首元素:q.front(),即最早被压入队列的元素。
访问队尾元素:q.back(),即最后被压入队列的元素。
判断队列空:q.empty(),当队列空时,返回true

三 题目代码

(一)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
import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node){
stack1.push(node);
}

public int pop(){
int a;
if(stack2.size() != 0){
a = stack2.peek();
stack2.pop();
return a;
}else{
while(stack1.size() != 0){
a = stack1.peek();
stack2.push(a);
stack1.pop();
}
a = stack2.peek();
stack2.pop();
return a;
}
}
}

(二)C++版本

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
class Solution
{
public:
void push(int node) {
stack1.push(node);
}

int pop() {
int a;
if(stack2.size() != 0){
a = stack2.top();
stack2.pop();
return a;
}else{
while(stack1.size() != 0){
a = stack1.top();
stack2.push(a);
stack1.pop();
}
a = stack2.top();
stack2.pop();
return a;
}

}

private:
stack<int> stack1;
stack<int> stack2;
};

四 随笔

  1. 要好好的从C向JAVA方向的转变,争取在开学之前完成剑指offer的第一遍刷题
  2. 刷题过程中要把之间忘记的和没学过的重新学习一遍
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信