数据结构：栈与队列

敖炜 Lv5
  2023-10-26 21:25:40 2023-10-26 21:25:40 创建   2024-04-19 09:30:15 2024-04-19 09:30:15 更新      4.5k 字  23 分钟  

这一篇博客将介绍数据结构——栈与队列

栈

栈是一种遵循先入后出(FILO)的线性数据结构

栈的先入后出规则

栈的常用操作

  • push(): 元素入栈（将元素添加到栈顶），时间复杂度
  • pop(): 栈顶元素出栈，时间复杂度
  • peek(): 访问栈顶元素（不出栈），时间复杂度

我们通常使用编程语言内置的栈类，若未提供栈类，可将数组或链表上与栈无关的操作忽视，当作栈来使用

1
2
3
4
5
6
7
8
9
10
11
12
13
# python没有内置的栈类，将List当作栈来使用
stack = []

stack.append(1)
stack.append(2)

peek = stack[-1]

pop = stack.pop()

size = len(stack)

is_empty = len(stack) == 0
1
2
3
4
5
6
7
8
9
10
11
12
stack<int> stack;

stack.push(1);
stack.push(2);

int top = stack.top();

stack.pop(); // 无返回值

int size = stack.size();

bool isEmpty = stack.empty();

栈的实现

栈可用被视作一种受限制的数组或链表

  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
class LinkedListStack:

    def __init__(self):
        self._peek = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return not self._peek

    def push(self, val):
        node = ListNode(val)
        node.next = self._peek
        self._peek = node
        self._size += 1

    def pop(self):
        data = self.peek()
        self._peek = self._peek.next
        self._size -= 1
        return data

    def peek(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._peek.val

    def to_list(self):
        # 转换为列表
        arr = []
        node = self._peek
        while node:
            arr.append(node.val)
            node = node.next
        arr.reverse() # 原本获得的顺序为从栈顶到栈底，现在转变为从栈底(最先入栈)到栈顶
        return arr
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
class LinkedListStack{
    private:
        ListNode* stackTop;
        int stackSize;

        void freeMemoryLinkedList(ListNode* head){
            ListNode* temp;
            while(head){
                temp = head;
                head = head->next;
                delete temp;
            }
        }

    public:
        LinkedListStack(){
            stackTop = nullptr;
            stackSize = 0;
        }

        ~LinkedListStack(){
            // 遍历链表删除节点，释放内存，以下函数只释放栈对象中的链表
            freeMemoryLinkedList(stackTop);
        }

        int size(){
            return stackSize;
        }

        bool isEmpty(){
            return size() == 0;
        }

        void push(int val){
            ListNode* node = new ListNode(val);
            node->next = stackTop;
            stackTop = node;
            stackSize++;
        }

        void pop(){
            int data = top();
            // 注意：C++和C没有垃圾回收机制，不可直接用下面语句
            // stackTop = stackTop->next;
            // 需要暂时记住头节点的地址，用于内存释放
            ListNode* temp = stackTop;
            stackTop =stackTop->next;

            // 释放内存
            delete temp;
            stackSize--;
        }

        int top(){
            if(isEmpty){
                throw out_of_range("栈为空");
            }
            return stackTop->val;
        }

        vector<int> toVector(){
            ListNode* node = stackTop;
            vector<int> res(size());
            for (int i = res.size() - 1; i >= 0; i--){
                res[i] = node->val;
                node = node->next;
            }
            return res;
        }
};
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
typedef struct{
    ListNode* top;
    int size;
}LinkedListStack;

ListedListStack* newListedListStack(){
    ListedListStack* stack = malloc(size(ListedListStack));
    stack->top = NULL;
    stack->size = 0;
    return stack;
}

void deleteListedListStack(ListedListStack* stack){
    ListedListStack* temp;
    while(stack->top){
        temp = stack->top;
        stack-top = stack->top->next;
        free(temp);
    }
    free(stack);
}

int size(ListedListStack* stack){
    assert(stack);
    return stack->size;
}

bool isEmpty(LinkedListStack* stack){
    assert(stack);
    return size(stack) == 0;
}

int peek(ListedListStack* stack){
    assert(stack);
    assert(!isEmpty(stack));
    return stack->top->val;
}

int pusk(ListedListStack* stack, int val){
    assert(stack);
    ListNode* node= (ListedListStack*)malloc(sizeof(ListNode));
    node->next = stack->top;
    node->val = val;
    stack->top = node;
    stack->size++; 
}

int pop(ListedListStack* stack){
    if(stack->size == 0){
        printf("stack is empty.\n");
        return INT_MAX;
    }
    assert(stack);
    int data = peek(stack);
    ListNode* temp = stack->top;
    stack->top = stack->top->next;
    free(temp);
    stack->size--;
    return data;
}
  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
# 使用动态数组实现，无须考虑数组扩容问题
class ArrayStack:

    def __init__(self):
        self._stack = []

    def size(self):
        return len(self._stack)

    def is_empty(self):
        return self._stack == []

    def push(self, item):
        self._stack.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("栈为空")
        return self._stack[-1]

    def to_list(self):
        return self._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
class ArrayStack{
    private:
        vector<int> stack;

    public:
        int size(){
            return stack.size();
        }

        bool isEmpty(){
            return stack.size() == 0;
        }

        void push(int item){
            stack.push_back(item);
        }

        void pop(){
            int oldTop = top();
            stack.pop_back();
        }

        int top(){
            if(isEmpty()){
                throw out_of_range("栈为空");
            }
            return stack.back();
        }

        vector<int> toVector(){
            return 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
47
typedef struct{
    int* data;
    int size;
}ArrayStack;

ArrayStack* newArrayStack(){
    ArrayStack* stack = malloc(sizeof(ArrayStack));
    // 由于C语言没有内置支持动态数组，因此初始化容量较大
    stack->data = malloc(MAX_SIZE * sizeof(int)); 
    stack->size = 0;
    return stack;
}

int size(ArrayStack* stack){
    return stack->size;
}

bool isEmpty(ArrayStack* stack){
    return stack->size == 0;
}

void push(ArrayStack* stack, int item){
    if(stack->size == MAX_SIZE){
        printf("stack is full.\n");
        return;
    }
    stack->data[stack->size] = item;
    stack->size++;
}

int peek(ArrayStack* stack){
    if(stack->size == 0){
        printf("stack is empty.\n");
        return INT_MAX;
    }
    return stack->data[stack->size - 1];
}

int pop(ArrayStack* stack){
    if(stack->size == 0){
        printf("stack is empty.\n");
        return INT_MAX;
    }
    int data = peek(stack);
    stack->size--;
    return data;
}

两种实现的对比

  • 时间效率：基于数组的实现具有良好的缓存本地性，效率较高，但数组扩容时入栈操作时间复杂度为。若入栈的是节点数据，入栈时需要初始化节点对象（若入栈的就是节点对象本身，则不需要初始化）并修改指针，效率相对较低。

    • 当操作元素是基本数据类型时，数组实现的平均效率高，链表实现的效率更稳定（不存在扩容现象）。

  • 空间效率：基于数组的实现可能造成一定的空间浪费，但基于链表的实现需要额外存储指针

典型应用

  • 浏览器中的后退与前进、软件中的撤销与反撤销：

    • 后退：打开一个网页，浏览器将上一个网页入栈，后退则是对上一个网页出栈
    • 前进：需要另一个栈，打开新网页时清空这个栈，后退时出栈的网页入栈到前进栈，前进则是对前进栈中的网页出栈。

  • 内存管理：调用函数时，系统会在为程序分配的栈的栈顶添加一个栈帧，用于记录函数的上下文信息，调用函数时栈帧入栈，返回函数时栈帧出栈

队列

队列是一种遵循先入先出(FIFO)的线性数据结构

队列的先入先出原则

队列常用操作

  • push()：元素入队（添加至队尾），时间复杂度为
  • pop()：队首元素出队，时间复杂度为
  • peek()：访问队首元素
1
2
3
4
5
6
7
8
9
10
11
12
queue = collections.deque()

queue.append(1)
queue.append(2)

front = queue[0]

pop = queue.popleft()

size = len(queue)

is_empty = len(queue) == 0
1
2
3
4
5
6
7
8
9
10
11
12
queue<int> queue;

queue.push(1);
queue.push(2);

int front = queue.front();

queue.pop()

int size = queue.size()

bool isEmpty = queue.empty()

队列实现

  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
42
43
44
class LinkedListQueue:

    def __init__(self):
        self._front = None
        self._rear = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return not self._front

    def push(self, val):
        node = ListNode(val)
        
        # 若队列为空
        if self._front is None:
            self._front = node
            self._rear = node
        else:
            self._rear.next = node
            self._rear = node
        self._size += 1

    def pop(self):
        data = self.peek()
        self._front = self._front.next
        self._size -= 1
        return data

    def peel(self):
        if self.is_empty():
            raise IndexError("队列为空")
        return self._front.val

    def to_list(self):
        queue = []
        # 注意，这里不能用self._front来代替temp，不能直接改变self._front的值，因为这里只是将队列转化为列表，不对队列进行改变
        temp = self._front
        while temp:
            queue.qppend(temp.val)
            temp = temp.next
        return queue
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
class LinkedListQueue{
    private:
        ListNode* front;
        ListNode* rear;
        int size;

        void freeMemoryLinkedList(ListNode* head){
            ListNode* temp;
            while(head){
                temp = head;
                head = head->next;
                delete temp;
            }
        }

    public:

        LinkedListQueue(){
            front = rear = nullptr;
            size = 0;
        }

        ~LinkedListQueue(){
            freeMemoryLinkedList(front);
        }

        int size(){
            return size;
        }

        bool isEmpty(){
            return size == 0;
        }

        void push(int val){
            ListNode* node = new ListNode(val);
            if(front == nullptr){
                front = node;
                rear = node;
            }else{
                rear->next = node;
                rear = node;
            }
            size++;
        }

        void pop(){
            int val = peek();
            ListNode* temp = front;
            front = front->next;
            delete temp;
            size--;
        }

        int peek(){
            if(isEmpty()){
                throw out_of_range("队列为空");
            }
            return front->val;
        }

        vector<int> toVector(){
            vector<int> res = new vector<int>(size());
            ListNode* temp = front;
            for(int i; i < size; i++){
                res[i] = temp->val;
                temp = temp->next;
            }
            return res;
        }
}
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
typedef struct{
    ListNode* front, rear;
    int size;
}LinkedListQueue;

LinkedListQueue* newLinkedListQueue(){
    LinkedListQueue* queue = malloc(sizeof(LinkedListQueue));
    queue->front = queue->rear = NULL;
    queue->size = 0;
    return queue;
}

void deleteLinkedListQueue(LinkedListQueue* queue){
    // 先释放队列内部的链表，再释放队列
    for(int i = 0; i < queue->size && queue->front != NULL; i++){
        ListNode* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
    }

    free(queue);
}

int size(LinkedListQueue* queue){
    return queue->size;
}

bool isEmpty(LinkedListQueue* queue){
    return (size(queue) == 0);
}

void push(LinkedListQueue* queue, int val){
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    if(queue->front == NULL){
        queue->front = node;
        queue->rear = node;
    }else{
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;
}

void pop(LinkedListQueue* queue){
    int val = peek(queue);
    ListNode* temp = queue->front;
    queue->front = queue->front->next;
    free(temp);
    queue->size--;
}

int peek(LinkedListQueue* queue){
    assert(queue);
    assert(!isEmpty());
    return queue->front->val;
}

int* toArray(LinkedListQueue* queue){
    int* array = (int*)malloc(queue->size * sizeof(int));
    ListNode* temp = queue->front;
    for(int i = 0; i < queue->size; i++){
        array[i] = temp->val;
        temp = temp->next;
    }
    return array;
}
  1. 基于数组的实现

在数组删除首元素的时间复杂度为，会导致出队操作效率低。解决方案是，用变量front保存首元素的index，变量size记录队列长度，rear = front + size指向队尾元素的下一个位置。同时，为了解决数组空间有限的问题，可以将数组视为首尾相接的环形数组，对front和rear进行取余操作，实现首尾相接

  • 入队：将元素保存在rear处，size++
  • 出队：front++， size--
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
class ArrayQueue:

    def __init__(self, size):
        self._array = [0] * size
        self._front = 0
        self._size = 0

    def capacity(self):
        return len(self._array)

    def size(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def push(self, val):
        if self._size == self.capacity():
            raise IndexError("队列已满")
        self._array[(self._front + self._size) % self.capacity()] = val
        self._size += 1

    def pop(self):
        res = self.peek()
        self._front = (self._front + 1) % self.capacity()
        self._size -= 1
        return res

    def peek(self):
        if self.is_empty:
            raise IndexError("队列为空")
        return self._array[self._front]

    def to_list(self):
        res = [0] * self.size()
        j = self._front
        for i in range(self.size()):
            res[i] = self._array[(j % self.capacity())]
            j += 1
        return res
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
class ArrayQueue{
    private:
        int* array;
        int front;
        int size;
        int capacity;

    public:
        ArrayQueue(int capacity){
            this.capacity= capacity;
            array = new int[capacity];
            front = size = 0;
        }

        ~ArrayQueue(){
            delete[] array;
        }

        int capacity(){
            return capacity;
        }

        int size(){
            return size;
        }

        bool isEmpty(){
            return size == 0;
        }

        void push(int val){
            if(size() == capacity()){
                throw out_of_range("队列已满");
            }
            array[(front + size) % capacity] = val;
            size++;
        }

        void pop(){
            int val = peek();
            front = (front + 1) % capacity;
            size--;
        }

        int peek(){
            if(isEmpty()){
                throw out_of_range("队列为空");
            }
            return array[front];
        }

        vector<int> toVector(){
            vector<int> res(size());
            for(int i = 0, j = front; i < size(); i++, j++){
                res[i] = array[j % capacity()];
            }
            return res;
        }
}
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
typedef struct {
    int* array;
    int front;
    int size;
    int capacity;
}ArrayQueue;

ArrayQueue* newArrayQueue(int capacity){
    ArrayQueue* queue = (ArrayQueue*)malloc(sizeof(ArrayQueue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->array = (int*)malloc(capacity * sizeof(int));
    return queue;
}

void deleteArrayQueue(ArrayQueue* queue){
    free(queue->array);
    free(queue);
}

int capacity(ArrayQueue* queue){
    return queue->capacity;
}

int size(ArrayQueue* queue){
    return queue->size;
}

bool isEmpty(ArrayQueue* queue){
    return (size(queue) == 0);
}

int peek(ArrayQueue* queue){
    assert(!isEmpty(queue));
    return queue->array[queue->front];
}

void push(ArrayQueue* queue, int val){
    if (size(queue) == capacity(queue)) {
        printf("队列已满\r\n");
        return;
    }
    queue->array[(queue->front + queue->size) % capacity(queue)] = val;
    queue->size++;
}

void pop(ArrayQueue* queue){
    int val = peek(queue);
    queue->front = (queue->front + 1) % capacity(queue);
    queue->size--;
}

int* toArray(ArrayQueue* queue){
    int* res = (int*)malloc(queue->size * sizeof(int));
    for(int i = 0, j = queue->front; i < size(queue); i++, j++){
        res[i] = queue->array[j % capacity(queue)];
    }
    return res;
}

典型应用

  • 电商订单
  • 待办事项

双向队列

双向队列可以在头部和尾部进行添加和删除操作

双向队列的操作

常用操作

  • pushFirst(): 队首添加元素
  • pushLast(): 队尾添加元素
  • popFirst(): 队首删除元素
  • popLast(): 队尾删除元素
  • peekFirst(): 访问队首
  • peekLast(): 访问队尾
    以上操作时间复杂度均为
1
2
3
4
5
6
7
8
9
10
11
12
13
14
deque = collections.deque()

deque.append(1) # 添加到队尾
deque.append(2)

deque.appendleft(3) # 添加到队首

front = deque[0]
rear = deque[-1]

pop_front = deque.popleft()
pop_rear = deque.pop()

size = len(deque)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
deque<int> deque;

deque.push_back(1); // 添加至队尾

deque.push_front(2); // 添加到队首

int front = deque.front();
int rear = deque.back();

deque.pop_front();
deque.pop_back();

int size = deque.size();

bool empty = deque.empty();

实现

  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
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
class ListNode:

    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class LinkedListDeque:

    def __init__(self):
        self._front = None
        self._rear = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return self.size() == 0

    # push的逻辑判断：队列是否为空，push在队首还是队尾
    def push(self, val, is_front):
        node = ListNode(val)
        if self.is_empty():
            self._front = node
            self._rear = node
            self._size += 1
        elif is_front:
            node.next = self._front
            self._front.prev = node
            self._front = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self._size += 1

    def push_first(val):
        push(val, True)

    def push_last(val):
        push(val, False)

    # pop的逻辑判断：队列是否为空，pop在队首或队尾，pop后队列是否为空
    def pop(self, is_front):
        if self.is_isempty():
            raise IndexError("双向队列为空")
        if is_front: # 队首出队
            res = self._front.val
            if self._front.next != None:
                self._front.next.prev = None
                self._front.next = None
            self._front = self._front.next
        else: # 队尾出队
            res = self._rear.val
            if self._rear.prev != None:
                self._rear.prev.next = None
                self._rear.prev = None
            self._rear = self._rear.prev
        self._size -= 1
        return res

    def pop_first(self):
        return self.pop(True)

    def pop_last(self):
        return self.pop(False)

    def peek_first(self):
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._front.val

    def peek_last(self):
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._rear.val

    def to_list(self):
        temp = self._front
        res = [0] * self.size()
        for i in range(self.size()):
            res[i] = temp.val
            temp = temp.next
        return res
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
struct ListNode{
    int val;
    ListNode* prev;
    ListNode* next;
    ListNode(int val) : val(val), prev(nullptr), next(nullptr){}
};

class LinkedListDeque{
    private:
        ListNode* front;
        ListNode* rear;
        int size;
    
    public:
        LinkedListDeque() : front(nullptr), rear(nullptr), size(0) {}

        ~LinkedListDeque(){
            ListNode* temp;
            while(front != nullptr){
                temp = front;
                front = front->next;
                delete temp;
            }
        }

        int size(){
            return size;
        }

        bool isEmpty(){
            return size() == 0;
        }

        void push(int val, bool isFront){
            ListNode* node = new ListNode(val);
            if(isEmpty()){
                front = rear = node;
            }
            else if(isFront){
                front->prev = node;
                node->next = front;
                front = node;
            }else{
                rear->next = node;
                node->prev = rear;
                rear = node;
            }
            size++;
        }

        void pushFirst(int val){
            push(val, true);
        }

        void pushLast(int val){
            push(val, false);
        }

        int pop(bool isFront){
            if (isEmpty()){
                throw out_of_range("双向队列为空");
            }
            int val;
            if(isFront){
                val = front->val;
                ListNode* fNext = front->next;
                if (fNext != nullptr){
                    FNext->prev = nullptr;
                    front->next = nullptr;
                    delete front;
                }
                front = fNext;
            }else{
                val = rear->val;
                ListNode* rPrev = rear->prev;
                if (rPrev != nullptr){
                    rPrev->next = nullptr;
                    rear->prev = nullptr;
                    delete rear;
                }
                rear = rPrev;
            }
            size--;
            return val;
        }

        int popFirst(){
            return pop(true);
        }

        int popLast(){
            return pop(false);
        }

        int peekFirst(){
            if (isEmpty()){
                throw out_of_range("双向队列为空");
            }
            return front->val;
        }

        int peekLast(){
            if (isEmpty()){
                throw out_of_range("双向队列为空");
            }
            return rear->val;
        }

        vector<int> toVector(){
            vector<int> res(sizeof(size()));
            ListNode* temp = front;
            for (int i = 0; i < size(); i++){
                res[i] = temp->val;
                temp = temp->next;
            }
            return res;
        }
};
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
typedef struct ListNode{
    struct ListNode* next;
    struct ListNode* prev;
    int val;
}ListNode;

ListNode* newListNode(int val){
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

void deleteListNode(ListNode* node){
    free(node);
}

typedef struct {
    ListNode* front, rear;
    int size;
}LinkedListDeque;

LinkedListDeque* newLinkedListDeque(){
    LinkedListDeque* deque = (LinkedListDeque*)malloc(sizeof(LinkedListDeque));
    deque->front = NULL;
    deque->rear = NULL;
    deque->size = 0;
    return deque;
}

void deleteLinkedListDeque(LinkedListDeque* deque){
    ListNode* temp;
    for(int i = 0; i < size(deque) && deque->front != NULL; i++){
        temp = deque->front;
        deque->front = deque->front->front;
        free(temp);
    }
    free(deque);
}

int size(LinkedListDeque* deque){
    return deque->size;
}

int isEmpty(LinkedListDeque* deque){
    return (size(deque) == 0);
}

void push(LinkedListDeque* deque, int val, bool isFront){
    ListNode* node = newListNode(val);
    if(isEmpty(deque)){
        deque->front = deque->rear = node;
    }else if (isFront){
        deque->front->prev = node;
        node->next = deque->front;
        deque->front = node;
    }else{
        deque->rear->next = node;
        node->prev = deque->rear;
        deque->rear = node;
    }
    deque->size++;
}

void pushFirst(LinkedListDeque* deque, int val){
    push(deque, val, true);
}

void pushLast(LinkedListDeque* deque, int val){
    push(deque, val, false);
}

int pop(LinkedListDeque* deque, bool isFront){
    asserrt(!isEmpty(deque));
    int val;
    if (isFront){
        val = deque->front->val;
        ListNode* fNext = deque->front->next;
        if (fNext != NULL){
            fNext->prev = NULL;
            deque->front->next = NULL;
            deleteListNode(deque->front);
        }
        deque->front = fNext;
    }else{
        val = deque->rear->val;
        ListNode* rPrev = deque->rear->prev;
        if (rPrev != NULL){
            rPrev->next = NULL;
            deque->rear->prev = NULL;
            deleteListNode(deque->rear);
        }
        deque->rear = rPrev;
    }
    deque->size--;
    return val;
}

int popFirst(LinkedListDeque* deque){
    return pop(deque, true);
}

int popLast(LinkedListDeque* deque){
    return pop(deque, false);
}

int* toArray(LinkedListDeque* deque){
    int* res = (int*)malloc(size(deque) * sizeof(int));
    for(int i = 0, ListNode* temp = deque->front; i < size(deque); i++, temp = temp->next){
        res[i] = temp->val;
    }
    return res;
}
  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
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
class ArrayDeque:

    def __init__(self, capacity):
        self._array = [0] * capacity
        self._front = 0
        self._rear = 0
        self._size = 0
    
    def size(self){
        return self._size
    }

    def capacity(self):
        return len(self._array)

    def is_empty(self):
        return self.size() == 0

    def index(self, i):
        """计算环形数组索引"""
        # 通过取余操作实现数组首尾相连
        # 当 i 越过数组尾部，回到头部
        # 当 i 越过数组头部，回到尾部
        return (i + self.capacity()) % self.capacity()

    def push_first(self, val):
        if self.size() == self.capacity():
            raise IndexError("双向队列已满")
        self._front = self.index(self._front - 1)
        self._array[self._front] = val
        self._size += 1

    def push_last(self, val):
        if self.size() == self.capacity():
            raise IndexError("双向队列已满")
        rear = self.index(self._front + self._size)
        self._array[rear] = val
        self._size += 1

    def pop_first(self):
        res = self.peek_first()
        self._front = self.index(self._front + 1)
        self._size -= 1
        return res

    def pop_last(self):
        res = self.peek_last()
        self._size -= 1
        return res
    
    def peek_first(self):
        if self.is_empty():
            raise IndexError("双向队列为空")
        return self._array[self._front]

    def peek_last(self):
        if self.is_empty():
            raise IndexError("双向队列为空")
        rear = self.index(self._front + self._size - 1)
        return self._array[rear]

    def to_array(self):
        res = []
        for i in range(self._size):
            res.append(self._nums[self.index(self._front + i)])
        return res
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
class ArrayDeque{
    private:
        vector<int> array;
        int front;
        int size;

    public:
        ArrayDeque(int capacity){
            array.resize(capacity);
            front = size = 0;
        }

        int capacity() {
            return array.size();
        }

        int size() {
            return size;
        }

        bool isEmpty() {
            return size() == 0;
        }

        int index(int i) {
            return (i + capacity()) % capacity();
        }

        void pushFirst(int val){
            if (size() == capacity()){
                throw out_of_range("双向队列已满");
            }
            front = index(front - 1);
            array[front] = val;
            size++;
        }

        void pushLast(int val){
            if (size() == capacity()){
                throw out_of_range("双向队列已满");
            }
            int rear = index(front + size);
            array[rear] = val
            size++;
        }

        int popFirst(){
            int res = peekFirst();
            front = index(front + 1);
            size--;
            return res;
        }

        int popLast(){
            int res = peek_last();
            size--;
            return res;
        }

        int peekFirst(){
            if (isEmpty()){
                throw out_of_range("双向队列为空");
            }
            return array[front];
        }

        int peekLast(){
            if (isEmpty()){
                throw out_of_range("双向队列为空");
            }
            return array[index(front + size - 1)];
        }

        vector<int> toVector(){
            vector<int> res(queSize);
            for (int i = 0, j = front; i < queSize; i++, j++) {
                res[i] = nums[index(j)];
            }
            return res;
        }
};
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
typedef struct {
    int *nums;       // 用于存储队列元素的数组
    int front;       // 队首指针，指向队首元素
    int queSize;     // 尾指针，指向队尾 + 1
    int queCapacity; // 队列容量
} ArrayDeque;

ArrayDeque *newArrayDeque(int capacity) {
    ArrayDeque *deque = (ArrayDeque *)malloc(sizeof(ArrayDeque));
    deque->queCapacity = capacity;
    deque->nums = (int *)malloc(sizeof(int) * deque->queCapacity);
    deque->front = deque->queSize = 0;
    return deque;
}

void delArrayDeque(ArrayDeque *deque) {
    free(deque->nums);
    deque->queCapacity = 0;
}

int capacity(ArrayDeque *deque) {
    return deque->queCapacity;
}

int size(ArrayDeque *deque) {
    return deque->queSize;
}

bool empty(ArrayDeque *deque) {
    return deque->queSize == 0;
}

int dequeIndex(ArrayDeque *deque, int i) {
    return ((i + capacity(deque)) % capacity(deque));
}

void pushFirst(ArrayDeque *deque, int num) {
    if (deque->queSize == capacity(deque)) {
        printf("双向队列已满\r\n");
        return;
    }
    deque->front = dequeIndex(deque, deque->front - 1);
    deque->nums[deque->front] = num;
    deque->queSize++;
}

void pushLast(ArrayDeque *deque, int num) {
    if (deque->queSize == capacity(deque)) {
        printf("双向队列已满\r\n");
        return;
    }
    int rear = dequeIndex(deque, deque->front + deque->queSize);
    deque->nums[rear] = num;
    deque->queSize++;
}

int peekFirst(ArrayDeque *deque) {
    assert(empty(deque) == 0);
    return deque->nums[deque->front];
}

int peekLast(ArrayDeque *deque) {
    assert(empty(deque) == 0);
    int last = dequeIndex(deque, deque->front + deque->queSize - 1);
    return deque->nums[last];
}

int popFirst(ArrayDeque *deque) {
    int num = peekFirst(deque);
    deque->front = dequeIndex(deque, deque->front + 1);
    deque->queSize--;
    return num;
}

int popLast(ArrayDeque *deque) {
    int num = peekLast(deque);
    deque->queSize--;
    return num;
}

void printArrayDeque(ArrayDeque *deque) {
    int arr[deque->queSize];
    for (int i = 0, j = deque->front; i < deque->queSize; i++, j++) {
        arr[i] = deque->nums[j % deque->queCapacity];
    }
    printArray(arr, deque->queSize);
}

典型应用

  • 撤销操作：原本撤销操作只需要栈即可，但是不可能无限地往栈中push，当栈的高度超过一定值时，采用双向队列可以将很早之前的操作删除（在队首）
  • 标题: 数据结构：栈与队列
  • 作者: 敖炜
  • 创建于 : 2023-10-26 21:25:40
  • 更新于 : 2024-04-19 09:30:15
  • 链接: https://ao-wei.github.io/2023/10/26/数据结构：栈与队列/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
数据结构：栈与队列
  1. 栈
    1. 栈的常用操作
    2. 栈的实现
    3. 两种实现的对比
    4. 典型应用
  2. 队列
    1. 队列常用操作
    2. 队列实现
    3. 典型应用
  3. 双向队列
    1. 常用操作
    2. 实现
    3. 典型应用