sunwengang blog

developer | android display/graphics

数据结构之栈和队列

sunwengang's Avatar 2021-05-19 cpp

分享本文
  1. 1. FIFO（先入先出数据结构）
    1. 1.1. 队列实现
      1. 1.1.1. cpp
      2. 1.1.2. java
    2. 1.2. 循环队列
      1. 1.2.1. 定义和接口
      2. 1.2.2. cpp实现
      3. 1.2.3. Leetcode实现方式-C++
      4. 1.2.4. Leetcode实现方式-Java
    3. 1.3. ☆内置队列库
      1. 1.3.1. cpp
      2. 1.3.2. java
  2. 2. LIFO（后入先出数据结构）
    1. 2.1. 栈定义和实现
      1. 2.1.1. cpp
      2. 2.1.2. java
    2. 2.2. ☆内置栈库
      1. 2.2.1. cpp
      2. 2.2.2. java
  3. 3. 顺序栈
    1. 3.1. 基本运算
      1. 3.1.1. 判断栈是否为空
      2. 3.1.2. 入栈
      3. 3.1.3. 出栈
      4. 3.1.4. 取栈顶元素操作
  4. 4. 链栈
  5. 5. 参考

栈和队列以及相关代码实现（阅读《数据结构（C++语言版）》及leetcode课题）

FIFO（先入先出数据结构）

FIFO数据结构中，将首先处理添加到队列中的第一个元素。

队列是典型的FIFO数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队（dequeue)。你只能移除第一个元素。

队列实现

为了实现队列，可以使用动态数组和指向队列头部的索引。

队列应支持两种操作：入队和出队。入队会向队列追加一个新元素，而出队会删除第一个元素。 所以我们需要一个索引来指出起点

以下是简单的代码实现，但是某些场景效率会很低。随着起始指针的移动，会造成更多的空间浪费。

cpp

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
#include <iostream>

class MyQueue {
    private:
        // store elements
        vector<int> data;       
        // a pointer to indicate the start position
        int p_start;            
    public:
        MyQueue() {p_start = 0;}
        /** Insert an element into the queue. Return true if the operation is successful. */
        //入队增加元素
        bool enQueue(int x) {
            data.push_back(x);
            return true;
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        //出队删除一个元素
        bool deQueue() {
            if (isEmpty()) {
                return false;
            }
            p_start++;  //队列头部索引后移
            return true;
        };
        /** Get the front item from the queue. */
        //队列第一个元素
        int Front() {
            return data[p_start];
        };
        /** Checks whether the queue is empty or not. */
        //判断是否为空
        bool isEmpty()  {
            return p_start >= data.size();
        }
};

int main() {
    MyQueue q;
    q.enQueue(5);
    q.enQueue(3);
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
}

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
44
45
46
47
48
49
50
51
52
// "static void main" must be defined in a public class.

class MyQueue {
    // store elements
    private List<Integer> data;         
    // a pointer to indicate the start position
    private int p_start;            
    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** Insert an element into the queue. Return true if the operation is successful. */
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }
    /** Get the front item from the queue. */
    public int Front() {
        return data.get(p_start);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return p_start >= data.size();
    }     
};

public class Main {
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

循环队列

上面的方式简单但是低效。

更有效的方法是使用循环队列。具体来说，就是使用固定大小的数组和两个指针来指示起始位置和结束位置

目的是重用我们之前提到的被浪费的存储。

定义和接口

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k
  • Front: 从队首获取元素。如果队列为空，返回 -1
  • Rear: 获取队尾元素。如果队列为空，返回 -1
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真
  • isEmpty(): 检查循环队列是否为空
  • isFull(): 检查循环队列是否已满

cpp实现

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
76
77
78
79
80
81
82
83
84
85
86
87
class MyCircularQueue {
private:
    int queue[1000] = {0};  //假设值范围在0-1000内
    int k = 0;      //队列长度
    int head = 0;   //头指针
    int end = -1;   //尾指针
    int count = 0;
    
public:
    MyCircularQueue(int k) {
        this->k = k;
    }
    
    //入队
    bool enQueue(int value) {
        if (count < k) {
            count++;    //当前入队元素数量，判断队列是否已满
            end = (end + 1) % k; //取余，注意end初始化是-1
            queue[end] = value;
            return true;
        }
        return false;
    }

    //出队
    bool deQueue() {
        if (count == 0) {
            return false;
        }
        count--;  //队列元素减一
        head = (head + 1) % k;  //队列元素后移，即第一次更新是1（移除了下标为0的元素）
        return true;
    }
    
    int Front() {
        if (count == 0) {
            return -1;
        }
        return queue[head]; //队首元素
    }
    
    int Rear() {
        if (count == 0) {
            return -1;
        }
        return queue[end]; //获取队尾元素
    }
    
    bool isEmpty() {
        if (count == 0) {  //队列元素是0，即空队列
            return true;
        }
        return false;
    }
    
    bool isFull() {
        if (count == k) { //队列已满
            return true;
        }
        return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

int main() {
    MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
    circularQueue.enQueue(1);  // 返回 true
    circularQueue.enQueue(2);  // 返回 true
    circularQueue.enQueue(3);  // 返回 true
    circularQueue.enQueue(4);  // 返回 false，队列已满
    circularQueue.Rear();  // 返回 3
    circularQueue.isFull();  // 返回 true
    circularQueue.deQueue();  // 返回 true
    circularQueue.enQueue(4);  // 返回 true
    circularQueue.Rear();  // 返回 4
    return 0;
}

Leetcode实现方式-C++

在循环队列中，我们使用一个数组和两个指针（head 和 tail）。 head 表示队列的起始位置，tail 表示队列的结束位置。

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
76
77
78
79
class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        data.resize(k);  //重置size
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return ((tail + 1) % size) == head;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * bool param_1 = obj.enQueue(value);
 * bool param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * bool param_5 = obj.isEmpty();
 * bool param_6 = obj.isFull();
 */

Leetcode实现方式-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
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
76
77
78
79
class MyCircularQueue {
    
    private int[] data;
    private int head;
    private int tail;
    private int size;

    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

☆内置队列库

大多数流行语言都提供内置的队列库，因此您无需重新发明轮子。

队列有两个重要的操作，入队 enqueue 和出队 dequeue。 此外，我们应该能够获得队列中的第一个元素，因为应该首先处理它。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

int main() {
    // 1. Initialize a queue.
    queue<int> q;
    // 2. Push new element.
    q.push(5);
    q.push(13);
    q.push(8);
    q.push(6);
    // 3. Check if queue is empty.
    if (q.empty()) {
        cout << "Queue is empty!" << endl;
        return 0;
    }
    // 4. Pop an element.移除一个元素
    q.pop();
    // 5. Get the first element.获取第一个元素
    cout << "The first element is: " << q.front() << endl;
    // 6. Get the last element.获取最后一个元素
    cout << "The last element is: " << q.back() << endl;
    // 7. Get the size of the queue.长度
    cout << "The size is: " << q.size() << endl;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a queue.
        Queue<Integer> q = new LinkedList();
        // 2. Get the first element - return null if queue is empty.
        System.out.println("The first element is: " + q.peek());
        // 3. Push new element.
        q.offer(5);
        q.offer(13);
        q.offer(8);
        q.offer(6);
        // 4. Pop an element.
        q.poll();
        // 5. Get the first element.
        System.out.println("The first element is: " + q.peek());
        // 7. Get the size of the queue.
        System.out.println("The size is: " + q.size());
    }
}

LIFO（后入先出数据结构）

参考：leetcode-后入先出的数据结构

在LIFO数据结构中，将首先处理添加到队列中的最新元素。

与队列不同，栈是一个LIFO数据结构。通常，插入操作在栈中被称作入栈push。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈pop，将始终删除队列中相对于它的最后一个元素

栈定义和实现

栈是限制在表的一端进行插入和删除的线性表。表中允许插入、删除的这一端称为栈顶，栈顶的当前位置是动态变化的；不允许插入和删除的另一端称为栈底，栈底是固定不变的。当表中没有元素时称为空栈。栈的插入运算称为进栈、压栈或入栈，栈的删除运算称为退栈或出栈。

cpp

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
#include <iostream>

class MyStack {
    private:
        vector<int> data;               // store elements
    public:
        /** Insert an element into the stack. */
        void push(int x) {
            data.push_back(x);
        }
        /** Checks whether the queue is empty or not. */
        bool isEmpty() {
            return data.empty();
        }
        /** Get the top item from the queue. */
        int top() {
            return data.back();
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool pop() {
            if (isEmpty()) {
                return false;
            }
            data.pop_back();
            return true;
        }
};

int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    for (int i = 0; i < 4; ++i) {
        if (!s.isEmpty()) {
            cout << s.top() << endl;
        }
        cout << (s.pop() ? "true" : "false") << endl;
    }
}

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
// "static void main" must be defined in a public class.
class MyStack {
    private List<Integer> data;               // store elements
    public MyStack() {
        data = new ArrayList<>();
    }
    /** Insert an element into the stack. */
    public void push(int x) {
        data.add(x);
    }
    /** Checks whether the queue is empty or not. */
    public boolean isEmpty() {
        return data.isEmpty();
    }
    /** Get the top item from the queue. */
    public int top() {
        return data.get(data.size() - 1);
    }
    /** Delete an element from the queue. Return true if the operation is successful. */
    public boolean pop() {
        if (isEmpty()) {
            return false;
        }
        data.remove(data.size() - 1);
        return true;
    }
};

public class Main {
    public static void main(String[] args) {
        MyStack s = new MyStack();
        s.push(1);
        s.push(2);
        s.push(3);
        for (int i = 0; i < 4; ++i) {
            if (!s.isEmpty()) {
                System.out.println(s.top());
            }
            System.out.println(s.pop());
        }
    }
}

☆内置栈库

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

int main() {
    // 1. Initialize a stack.
    stack<int> s;
    // 2. Push new element.
    s.push(5);
    s.push(13);
    s.push(8);
    s.push(6);
    // 3. Check if stack is empty.
    if (s.empty()) {
        cout << "Stack is empty!" << endl;
        return 0;
    }
    // 4. Pop an element.
    s.pop();
    // 5. Get the top element.
    cout << "The top element is: " << s.top() << endl;
    // 6. Get the size of the stack.
    cout << "The size is: " << s.size() << endl;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a stack.
        Stack<Integer> s = new Stack<>();
        // 2. Push new element.
        s.push(5);
        s.push(13);
        s.push(8);
        s.push(6);
        // 3. Check if stack is empty.
        if (s.empty() == true) {
            System.out.println("Stack is empty!");
            return;
        }
        // 4. Pop an element.
        s.pop();
        // 5. Get the top element.
        System.out.println("The top element is: " + s.peek());
        // 6. Get the size of the stack.
        System.out.println("The size is: " + s.size());
    }
}

栈的存储与一般的线性表的存储类似，主要有两种存储方式：顺序存储和链式存储。

顺序栈

利用顺序存储方式实现的栈称为顺序栈。
类似于顺序表的定义，要分配一块连续的存储空间存放栈中的元素，栈底位置可以固定地设置在数组的任何一端（一般在下标为0的一端），而栈顶是随着插入和删除而变化的，再用一个变量指明当前栈顶的位置（实际上是栈顶元素的下一个位置）

类描述：

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
typedef int DataType;
class SeqStack {
private:
    DataType *base; //栈底指针
    DataType *top;  //栈顶指针，始终指向栈顶元素的后一个位置
    int size;       //栈大小

public:
    //构造一个空栈
    SeqStack(int stacksize=100) {
        base = new DataType[stacksize];
        top=base;   //只想栈顶元素的后一个位置
        size=stacksize;
    }
    //销毁一个已存在的栈
    ~SeqStack() {
        delete[] base;
        top=NULL;
        base=NULL;
    }

    int Empty_Stack();   //判断栈是否为空
    int Push_Stack(DataType e);   //将元素e插入栈顶
    int Pop_Stack(DataType &e);   //从栈顶删除一个元素到e中返回
    int GetTop_Stack(DataType &e); //从栈顶取出一个元素到e中返回
};

基本运算

判断栈是否为空

算法思想：判断top是否小于等于base，小于等于则为空栈，返回1，否则返回0

1
2
3
int SeqStack::Empty_Stack() {
    return((top <= base));
}

入栈

入栈操作是在栈的顶部进行插入操作，相当于在顺序表的表尾进行插入，因而无须移动元素。

算法思想：首先判断栈是否已满，若满则失败，返回0；否则，由于栈的top 指向栈顶元素的后一个位置，将入栈元素赋到top的位置，再将top+1指向新的位置，成功返回1

1
2
3
4
5
6
7
8
9
int SeqStack::Push_Stack(DataType e) {
    if ((top-base) < size) {  //是否栈满
        *top = e;
        top++;
        return 1;
    } else {
        return 0;
    }
}

出栈

出栈操作是在栈的顶部进行删除操作，相当于在顺序表的表尾进行删除，因而也无须移动元素。

算法思想：首先判断栈是否为空，若空则失败，返回0；否则，由于栈的top 指向栈顶元素的后一位置，要先修改top为top-1，再将其所指向的元素以引用参数e返回，成功返回1。

1
2
3
4
5
6
7
8
9
int SeqStack::Pop_Stack(DataType &e) {
    if (top > base) {  //是否栈为空
        top--;
        e = *top;
        return 1;
    } else {
        return 0;
    }
}

取栈顶元素操作

取栈顶元素是获取出栈顶元素的值，而不改变栈。

算法思想：首先判断栈是否为空，若空则失败，返回0；否则，由于栈的top 指向栈顶元素的后一位置，返回top-1所指单元的值，栈不发生变化。

1
2
3
4
5
6
7
8
int SeqStack::Get_Stack(DataType &e) {
    if (top > base) {  //是否栈为空
        e = *(top-1);
        return 1;
    } else {
        return 0;
    }
}

链栈

用链式存储结构的栈，节点结构和单链表相同

因为栈中的主要运算是在栈顶进行插入和删除操作，显然在单链表的表头插入和删除都比较方便

因此以其作为栈顶，而且没有必要像单链表那样为了运算方便而附加一个头结点

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
typedf int DataType;
class StackNode {
    public:
        DataType data;
        StackNode *next;
        StackNode() {
            next = NULL;
        };
}

class LinkStack {
    private:
        StackNode *top;
    public:
        LinkStack() {
            top = NULL;
        }
        ~LinkStack() {
            while(top) {
                p = top;
                top = top->next;
                delete p;
            }
            top = NULL;
        }

    int Empty_Stack();              //判空
    int Push_Stack(DataType e);     //将元素e插入栈顶
    int Pop_Satck(DataType &e);     //从栈顶删除一个元素到e中返回
    int GetTop_Stack(DataType &e);  //从栈顶去除元素到e中返回
}；

参考

Leetcode-队列&栈

本文作者 : sunwengang
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
本文链接 : https://alonealive.github.io/Blog/2021/05/19/2021/210519_cpp_DataStructure3/

本文最后更新于 天前，文中所描述的信息可能已发生改变

本文发表于  , 最后修改于 

cpp