java实现栈和队列数据结构,java队列遍历

　　00-1010 1.栈)1。什么是堆栈？2.堆栈的常用方法3。自己实现一个栈(底层用数组实现)2。队列)1。什么是队列？2.队列的常用方法3。队列的实现(单链表实现)4。循环队列。

一、栈（Stack）

公共类my stack { public int[]elem；public int usedSizepublic my stack(){ this . elem=new int[4]；}//Put元素public void push(intval){ If(is full()){//如果已满，将this.elem=arrays.copyof (elem，2 * elem.length)的容量翻倍；} this . elem[this . usedsize]=val；}//获取栈顶元素并弹出public int pop(){ if(isempty()){ throw new runtime exception( stack is empty！);} usedSize-；return elem[usedSize]；}//获取栈顶元素，public int peek(){ if(isempty()){ throw new runtime exception( stack is empty！);} return elem[usedSize-1]；}//是否为空公共布尔值isempty(){ returnusedsize==0；}//是否满public boolean为full(){ return elem . length==usedsize；}}

1、什么是栈？

　　00-1010一种特殊的线性表，只允许一端插入数据，另一端删除数据。队列有-FIFO。

　　队列：执行插入操作的一端称为队列的尾部。

　　队列外：执行删除的一端称为队列头。

2、栈的常见方法

　　//普通队列Integer Queue=new linked List()；queue . offer(1)；//队列以int top=queue.peek()结尾；//获取队列头的queue.poll()元素；//弹出尾部元素，返回/

　　/ 双端队列Deque<Integer> deque = new LinkedList<>();deque.offer(1);// 默认队尾入deque.offerFirst(2);// 队头入deque.offerLast(3);// 队尾入deque.peekFirst();// 获取队头元素deque.peekLast();// 获取队尾元素deque.pollFirst();// 弹出队头元素并返回deque.pollLast();// 弹出队尾元素并返回

3、队列的实现（单链表实现）

/** * 每个节点 */class Node{ public int val; public Node next; public Node(int val) { this.val = val; }}public class MyQueue { public Node head; public Node tail; /** * 插入元素 -- 尾插法 * @param val */ public void offer(int val) { Node node = new Node(val); if (head == null) { head = node; tail = node; }else { tail.next = node; tail = tail.next; } } /** * 出队列 */ public int poll() { if(isEmpty()) { throw new RuntimeException("队列为空！"); } int val = head.val; head = head.next; return val; } /** * 获取队头元素 */ public int peek() { if(isEmpty()) { throw new RuntimeException("队列为空！"); } return head.val; } // 队列是否为空 public boolean isEmpty() { return head == null; }}

4、循环队列

当考虑用数组来实现一个队列，很容易想到以下结构：

　　当我们连续从该队头中弹出元素时，就可以发现问题了

　　可以看到此时数组并没有满，但是当我们再次插入元素时，队尾却插入不了了，这时候我们可以想到将该数组看成是循环的数组，结构如下。

　　可以看出，当 front 和 rear 相遇时，队列可能的情况有两种，要么为空，要么是满的状态。那么队列什么时候为空，什么时候是满的呢？

　　我们有两种方法：

　　1、设置usedSize 当usedSize和数组长度相等时为满，等于0 则为空。

　　2、设置标志位设 flag = true，每放一个元素，将 flag 置为 false，每有一个元素出队列，则将 flag 置为 true。当 front 和 rear 相遇时，flag为 true 则是空的，反之则是满的。

public class MyCircularQueue { public int[] elem; public int front;// 队头下标 public int rear;// 队尾下标 boolean flag = true;// 是否为空 public MyCircularQueue(int k) { elem = new int[k]; } // 向循环队列插入一个元素。如果成功插入则返回真。 public boolean enQueue(int value) { if (isFull()) { return false;// throw new RuntimeException("队列已满!"); } elem[rear] = value; rear = (rear + 1) % elem.length; flag = false; return true; } // 从循环队列中删除一个元素。如果成功删除则返回真。 public boolean deQueue() { if (isEmpty()) { return false;// throw new RuntimeException("队列为空!"); } front = (front + 1) % elem.length; flag = true; return true; } // 从队首获取元素。如果队列为空，返回 -1 。 public int Front() { if (isEmpty()) { return -1;// throw new RuntimeException("队列为空!"); } return elem[front]; } // 获取队尾元素。如果队列为空，返回 -1 。 public int Rear() { if (isEmpty()) { return -1;// throw new RuntimeException("队列为空!"); } // 如果是0下标，拿最后一个元素 if (rear == 0) { return elem[elem.length-1]; }else { return elem[rear - 1]; } } // 检查循环队列是否为空。 public boolean isEmpty() { if (rear == front && flag){ return true; } return false; } // 检查循环队列是否已满。 public boolean isFull() { if (rear == front && !flag){ return true; } return false; }}

到此这篇关于Java 栈与队列超详细分析讲解的文章就介绍到这了,更多相关Java 栈与队列内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。