一、隊列的介紹 隊列的定義:隊列是一種特殊的線性表,只允許在表的頭部(front處)進行刪除操作,在表的尾部(rear處)進行插入操作的線性數據結構,這種結構就叫做隊列。進行插入操作的一端稱為隊尾,進行刪除操作的一端稱為隊尾。 隊列的類型:鏈式隊列,即用鏈表實現的隊列。靜態隊列:即用數組實現的隊列。 ...
一、隊列的介紹
隊列的定義:隊列是一種特殊的線性表,只允許在表的頭部(front處)進行刪除操作,在表的尾部(rear處)進行插入操作的線性數據結構,這種結構就叫做隊列。進行插入操作的一端稱為隊尾,進行刪除操作的一端稱為隊尾。
隊列的類型:鏈式隊列,即用鏈表實現的隊列。靜態隊列:即用數組實現的隊列。
隊列的特性:
-
- 在隊尾插入元素,在隊首刪除元素。
- FIFO(先進先出),就向排隊取票一樣。
二、隊列的python代碼實現
class Queue(object): def __init__(self): print("===創建隊列===") self.element = [] def inQueue(self,num): self.element.append(num) print("%d進入隊列"%num,end=" ") def is_empty(self): if len(self.element)==0: return True else: return False def outQueue(self): if self.is_empty()==True: print("你要刪除的隊列為空") return else: num = self.element[0] print("%d要出隊列"%num,end=" ") self.element.pop(0) def length(self): return len(self.element) def travel(self): if self.is_empty()==True: print("你要遍歷的隊列為空") return else: print("你要遍歷的隊列元素有:",end=" ") for i in range(0,self.length()): print("%d "%self.element[i],end=" ") print("\n") def main(): q = Queue() print("===驗證空隊列===") q.travel() print("===往隊列中添加數據===") q.inQueue(1) q.travel() q.inQueue(2) q.inQueue(3) q.inQueue(4) q.inQueue(5) q.travel() print("===驗證出隊列===") q.outQueue() q.travel() q.outQueue() q.travel() if __name__ == '__main__': main()
運行結果為:
===創建隊列=== ===驗證空隊列=== 你要遍歷的隊列為空 ===往隊列中添加數據=== 1進入隊列 你要遍歷的隊列元素有: 1 2進入隊列 3進入隊列 4進入隊列 5進入隊列 你要遍歷的隊列元素有: 1 2 3 4 5 ===驗證出隊列=== 1要出隊列 你要遍歷的隊列元素有: 2 3 4 5 2要出隊列 你要遍歷的隊列元素有: 3 4 5
三、隊列的C語言代碼實現
// main.m // 隊列 // Created by 侯壘 on 2019/7/3. // Copyright © 2019 可愛的侯老師. All rights reserved. #include<stdio.h> #define SIZE 20 typedef struct Q { int array[SIZE]; int front; int rear; int length; }Queue; void createQueue(Queue *q) { q->front = 0; q->rear = -1; q->length = 0; printf("創建隊列成功\n"); } void inQueue(Queue *q,int num) { if (q->length >= SIZE) { printf("該隊列已經滿了\n"); } else { q->rear = q->rear+1; q->array[q->rear] = num; q->length++; printf("%d進入隊列\n",num); } } void outQueue(Queue *q) { if (q->length <= 0) { printf("這是一個空隊列"); } else { int num = q->array[q->front]; printf("%d出隊列 ",num); q->front = q->front+1; q->length--; } } void travel(Queue *q) { if (q->length <= 0) { printf("這是一個空隊列\n"); } else { printf("你遍歷的隊列裡面的數據有:"); for (int i=q->front; i<q->rear+1; i++) { printf(" %d ",q->array[i]); } printf("\n"); } } int main(int argc, const char * argv[]) { Queue q; createQueue(&q); travel(&q); inQueue(&q, 1); inQueue(&q, 2); inQueue(&q, 3); inQueue(&q, 4); inQueue(&q, 5); inQueue(&q, 6); travel(&q); outQueue(&q); travel(&q); outQueue(&q); travel(&q); outQueue(&q); travel(&q); return 0; }
運行結果為:
創建隊列成功 這是一個空隊列 1進入隊列 2進入隊列 3進入隊列 4進入隊列 5進入隊列 6進入隊列 你遍歷的隊列裡面的數據有: 1 2 3 4 5 6 1出隊列 你遍歷的隊列裡面的數據有: 2 3 4 5 6 2出隊列 你遍歷的隊列裡面的數據有: 3 4 5 6 3出隊列 你遍歷的隊列裡面的數據有: 4 5 6
四、雙端隊列
雙端隊列(deque,全名double-ended queue),是一種具有隊列和棧的性質的數據結構。
雙端隊列中的元素可以從兩端彈出,其限定插入和刪除操作在表的兩端進行。雙端隊列可以在隊列任意一端入隊和出隊。
雙端隊列的常用操作
- Deque() 創建一個空的雙端隊列
- add_front(item) 從隊頭加入一個item元素
- add_rear(item) 從隊尾加入一個item元素
- remove_front() 從隊頭刪除一個item元素
- remove_rear() 從隊尾刪除一個item元素
- is_empty() 判斷雙端隊列是否為空
- size() 返回隊列的大小
五、雙端隊列的python代碼實現
class Deque(object): """雙端隊列""" def __init__(self): self.items = [] print("初始化雙端隊列") def is_empty(self): """判斷隊列是否為空""" return self.items == [] def add_front(self, item): """在隊頭添加元素""" print("%d在隊首進入隊列"%item) self.items.insert(0,item) def add_rear(self, item): """在隊尾添加元素""" print("%d在隊尾進入隊列"%item) self.items.append(item) def remove_front(self): """從隊頭刪除元素""" item = self.items[0] print("%d從隊首出隊列"%item) return self.items.pop(0) def remove_rear(self): """從隊尾刪除元素""" print("%d從隊尾出隊列"%self.items[len(self.items)-1]) return self.items.pop() def size(self): """返回隊列大小""" return len(self.items) def travel(self): if len(self.items)==0: print("你要遍歷的隊列是空隊列") else: print("你要遍歷的隊列元素有:",end=" ") for i in range(0,len(self.items)): print("%d "%self.items[i],end=" ") print("\n") if __name__ == "__main__": deque = Deque() deque.add_front(1) deque.add_front(2) deque.add_rear(3) deque.add_rear(4) deque.travel() print("隊列長度為:%d\n"%deque.size()) deque.remove_front() deque.travel() deque.remove_front() deque.travel() deque.remove_rear() deque.travel() deque.remove_rear() deque.travel()
運行結果為:
初始化雙端隊列 1在隊首進入隊列 2在隊首進入隊列 3在隊尾進入隊列 4在隊尾進入隊列 你要遍歷的隊列元素有: 2 1 3 4 隊列長度為:4 2從隊首出隊列 你要遍歷的隊列元素有: 1 3 4 1從隊首出隊列 你要遍歷的隊列元素有: 3 4 4從隊尾出隊列 你要遍歷的隊列元素有: 3 3從隊尾出隊列 你要遍歷的隊列是空隊列
六、雙端隊列的C語言代碼實現
// main.m // 雙端隊列 // Created by 侯壘 on 2019/7/4. // Copyright © 2019 可愛的侯老師. All rights reserved. #include<stdio.h> // 創建隊列的節點結構體 typedef struct N { int num; struct N *next; }Node; // 創建節點 Node * createNode(int num) { Node *node = (Node *)malloc(sizeof(Node)); node->num = num; node->next = NULL; return node; } // 創建雙端隊列 Node * createDeQue() { printf("初始化隊列\n"); Node *head = NULL; return head; } // 判斷是否為空 int is_empty(Node *head) { if (head == NULL) { return 1; } else { return 0; } } // 求雙向隊列的長度 int length(Node *head) { Node *current = head; if (is_empty(head)) { return 0; } int count = 1; while (current->next!=NULL) { count++; current = current->next; } return count; } // 頭部插入 Node *add_front(Node *head, int num) { Node *node = createNode(num); Node *current = head; if (is_empty(head)==1) { head = node; } else { node->next = head; head = node; } printf("%d從隊列頭部進入隊列\n",num); return head; } // 尾部插入 Node *add_rear(Node *head,int num) { Node *node = createNode(num); if (is_empty(head)==1) { head = add_front(head, num); } else { Node *current = head; while (current->next != NULL) { current = current->next; } current->next = node; } printf("%d從尾部進入隊列\n",num); return head; } // 頭部刪除 Node *remove_front(Node *head) { if (is_empty(head) == 1) { printf("這是一個空隊列"); return head; } else { int num = head->num; //head->next = head->next->next; printf("%d從隊列頭部出隊列\n",num); head = head->next; return head; } } // 尾部刪除 Node *remove_rear(Node *head) { if (is_empty(head) == 1) { printf("這是一個空隊列"); return head; } else if (length(head) == 1) { head = remove_front(head); return head; } else { Node *current = head; for (int i=0; i<length(head)-2; i++) { current = current->next; } printf("%d從隊列尾部出隊列\n",current->next->num); current->next = NULL; return head; } } // 遍歷 void travel(Node *head) { if (is_empty(head) == 1) { printf("你遍歷的隊列為空\n"); } else { printf("你要遍歷的隊列元素有:"); Node *current = head; //printf("%d ",current->num); for (int i = 0; i<length(head); i++) { printf("%d ",current->num); current = current->next; } printf("\n"); } } int main(int argc, const char * argv[]) { Node *head = createDeQue(); head = add_front(head, 1); travel(head); head = add_front(head, 2); travel(head); head = add_rear(head, 3); travel(head); head = add_rear(head, 4); travel(head); int len = length(head); printf("現在隊列的長度為%d\n",len); head = remove_front(head); travel(head); head = remove_front(head); travel(head); len = length(head); printf("現在隊列的長度為%d\n",len); head = remove_rear(head); travel(head); head = remove_rear(head); travel(head); return 0; }
運行結果為:
初始化隊列 1從隊列頭部進入隊列 你要遍歷的隊列元素有:1 2從隊列頭部進入隊列 你要遍歷的隊列元素有:2 1 3從尾部進入隊列 你要遍歷的隊列元素有:2 1 3 4從尾部進入隊列 你要遍歷的隊列元素有:2 1 3 4 現在隊列的長度為4 2從隊列頭部出隊列 你要遍歷的隊列元素有:1 3 4 1從隊列頭部出隊列 你要遍歷的隊列元素有:3 4 現在隊列的長度為2 4從隊列尾部出隊列 你要遍歷的隊列元素有:3 3從隊列頭部出隊列 你遍歷的隊列為空