數(shù)據(jù)結(jié)構(gòu)（二）–隊(duì)列

文章目錄

• 數(shù)據(jù)結(jié)構(gòu)（二）--隊(duì)列
• • 介紹
  • 代碼實(shí)現(xiàn)
  • • 數(shù)組方式實(shí)現(xiàn)
    • • 普通隊(duì)列
      • 環(huán)形隊(duì)列
    • 鏈?zhǔn)綄?shí)現(xiàn)
    • • 單向隊(duì)列

介紹

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。

**特點(diǎn)：**先進(jìn)先出

代碼實(shí)現(xiàn)

數(shù)組方式實(shí)現(xiàn)

普通隊(duì)列

front代表隊(duì)列隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素當(dāng)前位置

初始化：front=-1，rear=-1

當(dāng)隊(duì)列空：front==rear

對(duì)滿了：rear ==maxsize-1

queue類

public class queue {private int maxSize;private int front;private int rear;private int[] arr;public queue(int maxSize){this.maxSize = maxSize;arr = new int[maxSize];//初始化隊(duì)列為空，所以為-1//front指向隊(duì)列第一個(gè)元素的前一個(gè)位置front = -1;//rear指向隊(duì)列最后一個(gè)元素位置rear = -1;}public boolean isFull(){return rear==maxSize-1;}public boolean isEmpty(){return front==rear;}public void addQueue(int n){if(isFull()) System.out.println("隊(duì)列滿了");else arr[++rear] = n;}public int outQueue(){if (isEmpty()) throw new RuntimeException("隊(duì)列為空");else return arr[++front];}public void showQueue(){if (isEmpty()) {System.out.println("隊(duì)列為空");return;}for(int i = front+1;i<=rear;i++){System.out.printf("arr[%d]=%d\t",i,arr[i]);}System.out.println();}}

主函數(shù)

public static void main(String[] args) {queue q = new queue(6);q.addQueue(5);q.addQueue(8);q.addQueue(10);q.addQueue(7);q.showQueue();System.out.println("出隊(duì)元素:"+q.outQueue());System.out.println("出隊(duì)元素:"+q.outQueue());q.showQueue();}

結(jié)果

arr[0]=5 arr[1]=8 arr[2]=10 arr[3]=7 出隊(duì)元素:5 出隊(duì)元素:8 arr[2]=10 arr[3]=7

環(huán)形隊(duì)列

front代表隊(duì)列隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素當(dāng)前位置，并且約定留一個(gè)空位區(qū)分隊(duì)列空和隊(duì)列滿的情況。

初始化：front=0，rear=0

當(dāng)隊(duì)列空：front==rear

對(duì)滿了：(rear+1)%maxSize==front

出隊(duì)和入隊(duì)時(shí)，front和rear變化：rear=(++rear)%maxSize，front=(++front)%maxSize

public class Cirqueue {private int maxSize;private int front;private int rear;private int[] arr;public Cirqueue(int maxSize){this.maxSize = maxSize;arr = new int[maxSize];//初始化隊(duì)列為空，所以為-1//front指向隊(duì)列第一個(gè)元素的前一個(gè)位置front = 0;//rear指向隊(duì)列最后一個(gè)元素位置rear = 0;}public boolean isFull(){return (rear+1)%maxSize==front;}public boolean isEmpty(){return front==rear;}public void addQueue(int n){if(isFull()) {System.out.println("隊(duì)列滿了");return;}rear = (++rear)%maxSize;arr[rear] = n;}public int outQueue(){if (isEmpty()) throw new RuntimeException("隊(duì)列為空");front = (++front)%maxSize;return arr[front];}public void showQueue(){if (isEmpty()) {System.out.println("隊(duì)列為空");return;}int i ;for(i = front+1;i!=rear;i=(i+1)%maxSize){System.out.printf("arr[%d]=%d\t",i,arr[i]);}System.out.printf("arr[%d]=%d\t",i,arr[i]);System.out.println();} }

mian函數(shù)

public static void main(String[] args) {Cirqueue q = new Cirqueue(6);q.addQueue(5);q.addQueue(8);q.addQueue(10);q.addQueue(7);q.addQueue(8);q.showQueue();System.out.println("出隊(duì)元素:"+q.outQueue());System.out.println("出隊(duì)元素:"+q.outQueue());System.out.println("出隊(duì)元素:"+q.outQueue());q.addQueue(4);q.addQueue(1);q.showQueue();}

結(jié)果

arr[1]=5 arr[2]=8 arr[3]=10 arr[4]=7 arr[5]=8 出隊(duì)元素:5 出隊(duì)元素:8 出隊(duì)元素:10 arr[4]=7 arr[5]=8 arr[0]=4 arr[1]=1

鏈?zhǔn)綄?shí)現(xiàn)

單向隊(duì)列

先實(shí)現(xiàn)節(jié)點(diǎn)

根據(jù)需要可以將數(shù)據(jù)域data的類型改為泛型**< T >**

public class Node {private String data;private Node next;public Node(){}public Node(String data,Node next){this.data = data;this.next = next;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}public String getData() {return data;}public void setData(String data) {this.data = data;}@Overridepublic String toString() {return "Node{" +"data='" + data + '\''+"}";} }

單鏈表

頭節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，所有操作臨時(shí)引用指向head；

刪除/插入節(jié)點(diǎn)：先判斷當(dāng)前節(jié)點(diǎn)是否滿足刪除或插入條件，然后判斷是否可以移動(dòng)，最后移動(dòng)（反復(fù)）

遍歷節(jié)點(diǎn)：判斷是否可以移動(dòng)，移動(dòng)，打印

打印某一節(jié)點(diǎn)：判斷是否可以移動(dòng)，移動(dòng)，判斷當(dāng)前節(jié)點(diǎn)是否可以打印（反復(fù)）

public class Linelist {private Node head ;public Linelist(){head = new Node(null,null);}//打印所有節(jié)點(diǎn)public void printNodes(){Node tepm = head;while (true){if (tepm.getNext()==null) break;tepm = tepm.getNext();System.out.println(tepm);}}//尾部添加數(shù)據(jù)public void addNode(String data){Node node = new Node(data,null);Node temp = head;while (true){if (temp.getNext()==null){temp.setNext(node);break;}temp = temp.getNext();}}//插入數(shù)據(jù)public void insertNode(int index,String data){//判斷越界if (index<=0) throw new RuntimeException("越界");Node node = new Node(data,null);Node temp = head;int i=0;while (true){//添加節(jié)點(diǎn)if (i==index-1){node.setNext(temp.getNext());temp.setNext(node);break;}//判斷越界if (temp.getNext()==null) throw new RuntimeException("越界！！！");//移動(dòng)temp = temp.getNext();i++;}}//刪除節(jié)點(diǎn)public Node deleteNode(int index) {//判斷越界if (index <=0 )new RuntimeException("越界!!!");Node temp = head;int i = 0;while (true) {//刪除節(jié)點(diǎn)if (i == index - 1 && temp.getNext() != null) {Node temp2 = temp.getNext();temp.setNext(temp2.getNext());temp2.setNext(null);return temp2;}//判斷越界if (temp.getNext()==null)throw new RuntimeException("越界!!!");//移動(dòng)temp = temp.getNext();i++;}}//打印某一節(jié)點(diǎn)public void printNode(int index){//判斷越界if (index<=0) new RuntimeException("越界!!!");Node temp = head;int i=0;while (true){//判斷越界if (temp.getNext()==null) {new RuntimeException("越界!!!");}//移動(dòng)i++;temp = temp.getNext();//打印if (i==index){System.out.println(temp);break;}}}}

單鏈隊(duì)列

public class Linequeue {private Linelist linelist ;public Linequeue(){linelist =new Linelist();}public void addQueue(String data){linelist.addNode(data);}public String outQueue(){Node node = linelist.deleteNode(1);return node.getData();}public void printQueue(){linelist.printNodes();}public static void main(String[] args) {Linequeue q = new Linequeue();q.addQueue("第一人");q.addQueue("第二人");q.addQueue("第三人");q.printQueue();System.out.println("--------------------");q.outQueue();q.addQueue("第四人");q.addQueue("第五人");q.printQueue();} }

結(jié)果

Node{data='第一人'} Node{data='第二人'} Node{data='第三人'} -------------------- Node{data='第二人'} Node{data='第三人'} Node{data='第四人'} Node{data='第五人'}

總結(jié)

以上是生活随笔為你收集整理的数据结构（二）--队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。