数据结构与算法

使用栈实现队列功能

使用栈实现队列功能

Wenyuan
2021-04-20
1 min
/*
使用栈实现队列

Queue:
isFull()
isEmpty()
pop()
push()
top()

class Stack; // 已经定义好了
isFull();
isEmpty();
pop();
push();
top();
*/
function queueByStack(mystack, cap) {
    let reserveStack = new Stack(cap),
        size = 0;
    while (!mystack.isEmpty()) {
        reserveStack.push(mystack.pop());
        size++;
    };

    function _reserve() {
        if (!reserveStack.isEmpty()) {
            return false;
        }
        while (!mystack.isEmpty()) {
            reserveStack.push(mystack.pop());
        };
        return true;
    }

    function _isEmpty() {
        return reserveStack.isEmpty() && mystack.isEmpty();
    }

    function _isFull() {
        if (mystack.isFull() || reserveStack.isFull() || size == cap) {
            return true;
        }
        return false;
    }

    function _pop() {
        if (_isEmpty()) {
            return false;
        }
        if (reserveStack.isEmpty()) {
            _reserve();
        }
        size--;
        return reserveStack.pop();
    }

    function _push(value) {
        if (_isFull) {
            return
        }
        mystack.push(value);
        size++;
    }

    function _top() {
        if (_isEmpty()) {
            return false;
        }
        if (reserveStack.isEmpty()) {
            _reserve();
        }
        return reserveStack.top();
    }
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75