双端队列(deque)和双端栈(double ended stack)

组别:提高组
难度:5

双端队列(deque)和双端栈(Double-ended Stack)是一种特殊的数据结构,它允许在两端进行操作。双端栈结合了栈和队列的特性,使得在头部和尾部都可以进行插入和删除的操作,适用于需要双向访问的场景。

deque的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
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
/**************************************************************** 
 * Description: double ended stack
 * Author: Alex Li
 * Date: 2024-06-24 11:54:08
 * LastEditTime: 2024-06-24 12:02:03
****************************************************************/
#include <iostream>
#include <deque>

std::deque<int> deq;

// 检查栈是否为空
bool isEmpty(){
      return deq.empty();
    }

// 从头部入栈
void pushFront(int value) {
        deq.push_front(value);
    }

// 从尾部入栈
void pushBack(int value) {
      deq.push_back(value);
    }

 // 从头部出栈
 int popFront() {
      if (!deq.empty()) {
          int value = deq.front();
          deq.pop_front();
          return value;
        } else {
            throw std::out_of_range("Stack is empty");
        }
    }

// 从尾部出栈
int popBack() {
     if (!deq.empty()) {
          int value = deq.back();
          deq.pop_back();
          return value;
      } else {
          throw std::out_of_range("Stack is empty");
      }
  }

// 获取头部元素
int front(){
        if (!deq.empty()) {
            return deq.front();
        } else {
            throw std::out_of_range("Stack is empty");
        }
    }

// 获取尾部元素
int back(){
    if (!deq.empty()) {
        return deq.back();
    } else {
        throw std::out_of_range("Stack is empty");
        }
    }



    // 获取栈的大小
    size_t size(){
        return deq.size();
    }


int main() {    
    // 测试双端栈功能
    pushFront(10);
    pushBack(20);
    pushFront(5);
    pushBack(25);

    std::cout << "Front element: " <<front() << std::endl;  // 输出 5
    std::cout << "Back element: " << back() << std::endl;    // 输出 25
    std::cout << "Popping from front: " <<popFront() << std::endl;  // 输出 5
    std::cout << "Popping from back: " << popBack() << std::endl;    // 输出 25
    std::cout << "Stack size: " <<size() << std::endl;  // 输出 2

    return 0;
}

常用函数

push_front(int value): 从头部入栈一个元素。
push_back(int value): 从尾部入栈一个元素。
pop_front(): 从头部出栈一个元素并返回该元素的值。
pop_back(): 从尾部出栈一个元素并返回该元素的值。
front(): 获取头部元素的值。
back(): 获取尾部元素的值。
empty(): 检查栈是否为空。
size(): 获取栈的当前大小(元素数量)。
clear(): 清空栈中的所有元素。
print(): 打印栈中的所有元素。
find(int value): 查找某个元素是否在栈中存在。
capacity(): 返回栈的最大容量。

Scroll to Top