栈与队列(一)

发表于 | 分类于
字数统计: 2,856

Java中的栈类

JAVA 中，使用 java.util.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
44
45
46
class Stack<E> extends Vector<E> {

    public Stack() {
    }
    
    public E push(E item) {
        addElement(item);

        return item;
    }

    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    public boolean empty() {
        return size() == 0;
    }

    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }            throw new EmptyStackException();

        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

基于vector实现stack

构造方法 ： public Stack() 创建一个空 Stack。

方法：

  1. public push （item ） 把项 压入栈顶。其作用与 addElement (item ) 相同。
  2. public pop () 移除栈顶对象，并作为函数的值 返回该对象。
    返回：栈顶对象（Vector 对象的中的最后一项）
    抛出异常 ： EmptyStackException 如果堆栈空
  3. public peek() 查看栈顶对象而不移除它
    返回：栈顶对象（Vector 对象的中的最后一项）
    抛出异常 ： EmptyStackException 如果堆栈式空的
  4. public boolean empty （测试堆栈是否为空） 当且仅当堆栈中不含任何项时 返回 true，否则 返回 false.
  5. public int search (object o) 返回对象在堆栈中位置， 以 1 为基数， 如果对象 ｏ是栈中的一项，该方法返回距离　栈顶最近的出现位置到栈顶的距离；　栈中最上端项的距离。使用equals 方法比较 o 与 堆栈中的项

设计一个具有getMin功能的栈

实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回
栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构。

思路1 两栈同步

用一个固定的位置保存最小值。但是还要考虑一个问题，如果有多个重复的最小值时，有pop和push时应该如何处理？是不是还有保存个数呢？这时隐约想起不知在哪看过的一个方法：同时用两个栈，最小值栈同步更新

代码实现 Minstack.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.Stack;

public class Minstack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public Minstack(){
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public Integer push(Integer item){
        stack.push(item);

        if(!minStack.empty()){
            Integer min = ((minStack.peek() - item) > 0 )? item:minStack.peek();
            minStack.push(min);
        }else{
            minStack.push(item);
        }

        return item;
    }

    public Integer pop(){
        Integer moveout;
        moveout = stack.pop();
        minStack.pop();
        return moveout;
    }

    public Integer getMin(){
        if(!minStack.empty()){
            return minStack.peek();
        }else {
            return Integer.MIN_VALUE;
        }
    }

    public boolean empty() {
        return stack.size() == 0;
    }
}

测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Test {
    public static void main(String[] args){
        Integer[] list = {2,3,5,6,4,2,1,0,6,7};
        Minstack minstack = new Minstack();
        for(int i = 0 ; i < list.length; i++){
            minstack.push(list[i]);
            System.out.println("入栈数为"+ list[i] + "  栈中所有元素最小值为"+ minstack.getMin());
        }
        while (!minstack.empty()){
            System.out.print("出栈数为"+ minstack.pop());
            if (minstack.getMin() != Integer.MIN_VALUE){
                System.out.println("  栈中剩余元素最小值为"+ minstack.getMin());
            }else  System.out.println("  栈中已无更多元素");
        }
    }
}

测试结果

思路2 两栈不同步

非同步压入，如果待入栈元素更小或相等，则压入minStack; 否则，不压入。 这样的话，在弹出的时侯还需要做一次比较，相比于思路1是用比较的开销来节省了minStack的空间。

由两个栈组成的队列

用两个栈实现队列，支持队列的基本操作：add poll peek

思路 倒腾来倒腾去

看过很多次的一个题目了，就是把第一个栈满了以后，把元素依次弹出到第二个栈中，这样就从第一个的逆序变成了第二个栈的正序，第二个栈就可以当队列使用了。

队列的peek：查看首个元素，不会移除首个元素

需要注意的问题是，什么时候去倒腾数据，避免产生顺序错乱问题, 暂时想到的方法是要进行poll或者peek操作时，先判断第二个栈是否为空。为空则倒腾一下，不为空，直接对现有数据进行操作。假定第一个栈没有空间限制，add操作就不用涉及到第二个栈了

代码实现 Stacklist.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Stack;

public class Stacklist {
    private Stack<Integer> firstStack;
    private Stack<Integer> secondStack;

    public Stacklist(){
        this.firstStack = new Stack<>();
        this.secondStack = new Stack<>();
    }

    public Integer add(Integer item){
        firstStack.push(item);
        return item;
    }

    public Integer poll(){
        if(!secondStack.empty()){
            return secondStack.pop();
        }else {
            while (!firstStack.empty()){
                secondStack.push(firstStack.pop());
            }
            if(!secondStack.empty()){
                return secondStack.pop();
            }else throw new RuntimeException("已无更多元素");
        }
    }

    public Integer peek(){
        if(!secondStack.empty()){
            return secondStack.peek();
        }else {
            while (!firstStack.empty()){
                secondStack.push(firstStack.pop());
            }
            if(!secondStack.empty()){
                return secondStack.peek();
            }else throw new RuntimeException("已无更多元素");
        }
    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
public class Test {
    public static void main(String[] args){
        Stacklist stacklist = new Stacklist();
        System.out.println("元素 "+stacklist.add(2)+" 入队");
        System.out.println("元素 "+stacklist.add(4)+" 入队");
        System.out.println("队首元素为 "+stacklist.peek());
        System.out.println("元素 "+stacklist.poll()+" 出队");
        System.out.println("队首元素为 "+stacklist.peek());
        System.out.println("元素 "+stacklist.poll()+" 出队");
        System.out.println("队首元素为 "+stacklist.peek());
    }
}

结果

1
2
3
4
5
6
元素 2 入队
元素 4 入队
队首元素为 2
元素 2 出队
队首元素为 4
元素 4 出队

代码优化

自己写的时候就感觉到了…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
35
36
37
38
39
40
import java.util.Stack;

public class Stacklist {
    private Stack<Integer> firstStack;
    private Stack<Integer> secondStack;

    public Stacklist(){
        this.firstStack = new Stack<>();
        this.secondStack = new Stack<>();
    }

    public Integer add(Integer item){
        firstStack.push(item);
        return item;
    }

    public Integer poll(){
        if(firstStack.empty() && secondStack.empty()){
            throw new RuntimeException("已无更多元素");
        }
        firstToSecond();
        return secondStack.pop();
    }

    public Integer peek(){
        if(firstStack.empty() && secondStack.empty()){
            throw new RuntimeException("已无更多元素");
        }
        firstToSecond();
        return secondStack.peek();
    }

    private void firstToSecond(){
        if(secondStack.empty()){
            while (!firstStack.empty()){
                secondStack.push(firstStack.pop());
            }
        }
    }
}

将两个栈均为空的判断放在最前面，判断起来会更加简洁，代码也更具有可读性。

递归函数和栈逆序

一个栈依次压入1，2，3，4，5, 然后将栈转置。只能用递归函数实现，不能用其他数据结构。

错误思路

要用递归去实现，首先考虑递归的出口，和每一步变化中递归返回值之间的关系。

问题的关键在于：不能用额外的数据结构来保存中间弹出的数据。所以只能考虑用栈的返回值来保存了

最初是这样写的，然后发现结果并没有变。。

1
2
3
4
5
6
public void reverse(){
    Integer temp = stack.pop();
    if(stack.size() > 0)    reverse();
    stack.push(temp);
    return ;
}

问题在于，拿到的数据还是只能按照原来的路径重新压入。

正确思路

需要设计两个递归函数

递归函数一：将栈stack的栈底元素返回并移除。取完值后重新压栈

递归函数二：逆序一个栈，每层栈用 i 保存栈底值

也就是说，一个函数用来取数，一个函数用来逆序。

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
47
48
49
import java.util.Stack;

public class ReverseStack {

    private Integer[] list;
    private Stack<Integer> stack;

    public ReverseStack(Integer[] List){
        this.list = List;
        this.stack = new Stack<>();
        for(int i = 0; i < list.length;i++){
            this.stack.push(list[i]);
      }
    }

    public Integer getLast(){
        Integer result = stack.pop();
        if(stack.size() > 0){
            Integer last = getLast();
            stack.push(result);
            return last;
        }
        return result;
    }

    public void reverse(){
        if(stack.size() == 0)   return ;
        Integer i = getLast();
        reverse();
        stack.push(i);
    }

    public void result(){
        while (stack.size() != 0){
            System.out.println(stack.pop());
        }
    }
}

//test
public class Test {
    public static void main(String[] args) {
        Integer[] list = {1,2,3,4,5,6};
        ReverseStack reverseStack = new ReverseStack(list);
        reverseStack.reverse();
        System.out.println("------ after reverse ------");
        reverseStack.result();
    }
}

测试结果

猫狗队列

要求：

● 用户可以调用add方法将cat类或dog类的实例放入队列中；

● 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；

● 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；

● 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；

● 用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；

● 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；

● 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。

初步思路

这题考察的是面向对象中的继承重写问题，尝试着写了一下，有点问题，一是队列到底应该放在哪一个层次；二是没有实现接口时如何实例化。遇到了空指针问题，不知道如何写下去了。说到底还是基础不行啊..

参考思路

给不同的实例添上时间戳。为了不改变原本的类，封装一个新类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class PetEnterQueue {
    private Pet pet;
    private long count;

    public PetEnterQueue(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return pet;
    }

    public long getCount() {
        return count;
    }
    
    public String getEnterPetType(){
        return this.pet.getPetType();
    }
}

设置一个全局计数器，同时用两个队列分别放dog和cat —- 我一开始的思路很有问题，我是打算两种放一起的。。然而线性表只能放同一种数据类型

所以从逻辑上来说这是一个混合队列，但是实现的时候，却要分别处理。时间戳主要是为了比较两个队列之间的先后顺序，可以看作是联系两个队列的桥梁 — 更一般的来说，其实这个一个特殊的队列合并问题

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
47
48
49
50
51
52
53
54
55
56
57
import java.util.LinkedList;
import java.util.Queue;

public class DogCatQueue {
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue(){
        this.dogQ = new LinkedList<>();
        this.catQ = new LinkedList<>();
        this.count = 0;
    }

    public  void add(Pet pet){
        if(pet.getPetType().equals("dog")) this.dogQ.add(new PetEnterQueue(pet,this.count++));
        else if(pet.getPetType().equals("cat")) this.catQ.add(new PetEnterQueue(pet,this.count++));
        else throw new RuntimeException("err,not dog or cat");
    }

    // 按题意这里是弹出dog cat中先进去的一个，而不是所有元素
    public Pet pollAll(){
        if(!this.isDogQueueEmpty() && !this.isCatQueueEmpty()){
            if(this.dogQ.peek().getCount() < this.catQ.peek().getCount()){
                return this.dogQ.poll().getPet();
            }else {
                return this.catQ.poll().getPet();
            }
        }else if(!this.isDogQueueEmpty()){
            return this.dogQ.poll().getPet();
        }else if(!this.isCatQueueEmpty()) {
            return this.catQ.poll().getPet();
        }else throw new RuntimeException("err,queue is empty");
    }

    public Pet pollDog(){
        if(!this.isDogQueueEmpty()) return (Dog)this.dogQ.poll().getPet();
        else throw new RuntimeException("err,dogqueue is empty");
    }

    public Pet pollCat(){
        if(!this.isCatQueueEmpty()) return (Cat)this.catQ.poll().getPet();
        else throw new RuntimeException("err,catqueue is empty");
    }

    public boolean isEmpty(){
        return this.dogQ.isEmpty() && this.catQ.isEmpty();
    }

    public boolean isDogQueueEmpty(){
        return this.dogQ.isEmpty();
    }

    public boolean isCatQueueEmpty(){
        return this.catQ.isEmpty();
    }
}

注意Queue是用链表实现的。