1+ /*
2+ * File: array_deque.rs
3+ * Created Time: 2023-03-11
4+ * Author: sjinzh (sjinzh@gmail.com)
5+ */
6+
7+ include ! ( "../include/include.rs" ) ;
8+
9+ /* 基于环形数组实现的双向队列 */
10+ struct ArrayDeque {
11+ nums : Vec < i32 > , // 用于存储双向队列元素的数组
12+ front : usize , // 队首指针，指向队首元素
13+ que_size : usize , // 双向队列长度
14+ }
15+
16+ impl ArrayDeque {
17+ /* 构造方法 */
18+ pub fn new ( capacity : usize ) -> Self {
19+ Self {
20+ nums : vec ! [ 0 ; capacity] ,
21+ front : 0 ,
22+ que_size : 0 ,
23+ }
24+ }
25+
26+ /* 获取双向队列的容量 */
27+ pub fn capacity ( & self ) -> usize {
28+ self . nums . len ( )
29+ }
30+
31+ /* 获取双向队列的长度 */
32+ pub fn size ( & self ) -> usize {
33+ self . que_size
34+ }
35+
36+ /* 判断双向队列是否为空 */
37+ pub fn is_empty ( & self ) -> bool {
38+ self . que_size == 0
39+ }
40+
41+ /* 计算环形数组索引 */
42+ fn index ( & self , i : i32 ) -> usize {
43+ // 通过取余操作实现数组首尾相连
44+ // 当 i 越过数组尾部后，回到头部
45+ // 当 i 越过数组头部后，回到尾部
46+ return ( ( i + self . capacity ( ) as i32 ) % self . capacity ( ) as i32 ) as usize ;
47+ }
48+
49+ /* 队首入队 */
50+ pub fn push_first ( & mut self , num : i32 ) {
51+ if self . que_size == self . capacity ( ) {
52+ println ! ( "双向队列已满" ) ;
53+ return
54+ }
55+ // 队首指针向左移动一位
56+ // 通过取余操作，实现 front 越过数组头部后回到尾部
57+ self . front = self . index ( self . front as i32 - 1 ) ;
58+ // 将 num 添加至队首
59+ self . nums [ self . front ] = num;
60+ self . que_size += 1 ;
61+ }
62+
63+ /* 队尾入队 */
64+ pub fn push_last ( & mut self , num : i32 ) {
65+ if self . que_size == self . capacity ( ) {
66+ println ! ( "双向队列已满" ) ;
67+ return
68+ }
69+ // 计算尾指针，指向队尾索引 + 1
70+ let rear = self . index ( self . front as i32 + self . que_size as i32 ) ;
71+ // 将 num 添加至队尾
72+ self . nums [ rear] = num;
73+ self . que_size += 1 ;
74+ }
75+
76+ /* 队首出队 */
77+ fn pop_first ( & mut self ) -> i32 {
78+ let num = self . peek_first ( ) ;
79+ // 队首指针向后移动一位
80+ self . front = self . index ( self . front as i32 + 1 ) ;
81+ self . que_size -= 1 ;
82+ num
83+ }
84+
85+ /* 队尾出队 */
86+ fn pop_last ( & mut self ) -> i32 {
87+ let num = self . peek_last ( ) ;
88+ self . que_size -= 1 ;
89+ num
90+ }
91+
92+ /* 访问队首元素 */
93+ fn peek_first ( & self ) -> i32 {
94+ if self . is_empty ( ) { panic ! ( "双向队列为空" ) } ;
95+ self . nums [ self . front ]
96+ }
97+
98+ /* 访问队尾元素 */
99+ fn peek_last ( & self ) -> i32 {
100+ if self . is_empty ( ) { panic ! ( "双向队列为空" ) } ;
101+ // 计算尾元素索引
102+ let last = self . index ( self . front as i32 + self . que_size as i32 - 1 ) ;
103+ self . nums [ last]
104+ }
105+
106+ /* 返回数组用于打印 */
107+ fn to_array ( & self ) -> Vec < i32 > {
108+ // 仅转换有效长度范围内的列表元素
109+ let mut res = vec ! [ 0 ; self . que_size] ;
110+ let mut j = self . front ;
111+ for i in 0 ..self . que_size {
112+ res[ i] = self . nums [ self . index ( j as i32 ) ] ;
113+ j += 1 ;
114+ }
115+ res
116+ }
117+ }
118+
119+ fn main ( ) {
120+ /* 初始化双向队列 */
121+ let mut deque = ArrayDeque :: new ( 10 ) ;
122+ deque. push_last ( 3 ) ;
123+ deque. push_last ( 2 ) ;
124+ deque. push_last ( 5 ) ;
125+ print ! ( "双向队列 deque = " ) ;
126+ print_util:: print_array ( & deque. to_array ( ) ) ;
127+
128+ /* 访问元素 */
129+ let peek_first = deque. peek_first ( ) ;
130+ print ! ( "\n 队首元素 peek_first = {}" , peek_first) ;
131+ let peek_last = deque. peek_last ( ) ;
132+ print ! ( "\n 队尾元素 peek_last = {}" , peek_last) ;
133+
134+ /* 元素入队 */
135+ deque. push_last ( 4 ) ;
136+ print ! ( "\n 元素 4 队尾入队后 deque = " ) ;
137+ print_util:: print_array ( & deque. to_array ( ) ) ;
138+ deque. push_first ( 1 ) ;
139+ print ! ( "\n 元素 1 队首入队后 deque = " ) ;
140+ print_util:: print_array ( & deque. to_array ( ) ) ;
141+
142+ /* 元素出队 */
143+ let pop_last = deque. pop_last ( ) ;
144+ print ! ( "\n 队尾出队元素 = {}，队尾出队后 deque = " , pop_last) ;
145+ print_util:: print_array ( & deque. to_array ( ) ) ;
146+ let pop_first = deque. pop_first ( ) ;
147+ print ! ( "\n 队首出队元素 = {}，队首出队后 deque = " , pop_first) ;
148+ print_util:: print_array ( & deque. to_array ( ) ) ;
149+
150+ /* 获取双向队列的长度 */
151+ let size = deque. size ( ) ;
152+ print ! ( "\n 双向队列长度 size = {}" , size) ;
153+
154+ /* 判断双向队列是否为空 */
155+ let is_empty = deque. is_empty ( ) ;
156+ print ! ( "\n 双向队列是否为空 = {}" , is_empty) ;
157+ }
0 commit comments