1.隊列
1.1 什么是隊列
只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作得特殊線性表，隊列是先進先出，入隊：進行插入操作得一端稱為隊尾（rear），出隊：進行刪除操作的一端稱為隊頭(front)。隊列Queue是個接口，底層通過鏈表實現(xiàn)的。
- boolean offer(E e) – 入隊列
- E poll() – 出隊列
- peek() – 獲取隊頭元素
- int size() – 獲取隊列中有效元素個數(shù)
- boolean isEmpty() – 檢測隊列是否為空
注意：Queue是個接口，在實例化時必須實例化LinkedList的對象，因為LinkedList實現(xiàn)了Queue接口。
1.2 創(chuàng)建隊列
public class MyQueue {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head; // 隊頭
public ListNode last; // 隊尾
}
1.3 隊列是否為空和獲取隊頭元素 empty()+peek()
public boolean empty() {
return head == null;
}
public int peek() {
if (head == null) {
return -1;
}
return head.val;
}
1.4 入隊offer()
入隊相當于鏈表的尾插法，入隊元素node，然后隊列為空，直接把頭尾節(jié)點指向node，不為空：從隊尾入隊操作，last的后節(jié)點指向node，node的前節(jié)點指向last，last再指向node。
public void offer(int val) {
ListNode node = new ListNode(val);
if (head == null) {
head = last = node;
}else {
last.next = node;
node.prev = last;
last = node;
}
}
1.5 出隊（頭刪）poll()
給個臨時變量val，當只有一個節(jié)點時：val指向head.val，出隊完head指向null，返回val。不止一個節(jié)點：val指向head.val，head指向head的后節(jié)點，head的前驅節(jié)點指向null，返回val。
public int poll() {
if(head == null) {
return -1;
}
//只有一個節(jié)點
int val = -1;
if (head.next == null) {
val = head.val;
head = null;
return val;
}
val = head.val;
head = head.next;
head.prev = null;
return val;
}
2. 循環(huán)隊列
假如隊列的大小為8，當7走到下一個下標0的時候，下標+1實現(xiàn)不了，所有在循環(huán)隊列當中，實現(xiàn)數(shù)組下標循環(huán)：隊頭：front = (front + 1) % elem.length，隊尾：rear = (rear + 1) % elem.length，區(qū)分隊列空和滿：當隊頭front和隊尾rear相遇時為空。當隊尾rear的下個為隊頭front為滿。
2.1 創(chuàng)建循環(huán)隊列
class MyCircularQueue {
// 循環(huán)隊列
public int[] elem;
public int front;
public int rear;
public MyCircularQueue(int k) {
elem = new int[k+1];
}
}
2.2 判斷是否為空isEmpty()和滿isFull()
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear+1) % elem.length == front;
}
2.3 入隊enQueue()
public boolean enQueue(int value) {
if (isFull()) {
return false;
}else {
elem[rear] = value;
rear = (rear + 1) % elem.length;
return true;
}
}
2.4 出隊 deQueue()
public boolean deQueue() {
if(isEmpty()) {
return false;
}else {
// 得到數(shù)組下標最后再完后的下標 如果最大是8，后面跳轉到0
front = (front + 1) % elem.length;
return true;
}
}
2.5 得到隊頭元素不刪除 Front()
public int Front() {
if (isEmpty()) {
return -1;
}
return elem[front];
}
2.6 得到隊尾元素不刪除 Rear()
public int Rear() {
if (isEmpty()) {
return -1;
}
int index = (rear == 0) ? elem.length-1 : rear-1;
return elem[index];
}
3.用隊列模擬棧
在這里用到兩個先進先出的隊列來實現(xiàn)棧。
思路：
- 1.當兩個隊列都是空的時候，放到第一個隊列
- 2.再次入棧的時候，放到不為空的隊列
- 3.出棧的時候，出不為空的隊列 出size-1個元素，剩下的元素就是要出棧的元素
3.1 實例化兩個隊列
class MyStack{
private Queue<Integer> qu1;
private Queue<Integer> qu2;
public MyStack() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
}
3.2 判斷棧是否為空
判斷棧是否為空我們直接返回兩個隊列是否為空。
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
3.1 入棧push()
當兩個隊列都是空的時候，放到第一個隊列，再次入棧的時候，放到不為空的隊列
public void push(int x) {
if (empty()) {
qu1.offer(x);
return;
}
if (!qu1.isEmpty()) {
qu1.offer(x);
}else {
qu2.offer(x);
}
}
3.2 出棧pop()
找到不為空的隊列 出size-1個元素 剩下的元素就是出棧的元素，每彈出一個size都在變小一次，
public int pop() {
if (empty()) {
return -1;
}
// 找到不為空的隊列 出size-1個元素 剩下的元素就是出棧的元素
if (!qu1.isEmpty()) {
int size = qu1.size();
for (int i = 0; i < size-1; i++) {
qu2.offer(qu1.poll());
}
return qu1.poll();
}else {
// 沒彈出一個size都在變小一次
int size = qu2.size();
for (int i = 0; i < size-1; i++) {
qu1.offer(qu2.poll());
}
return qu2.poll();
}
}
3.3 獲取棧頂元素top()
和出棧一樣，給一個臨時變量tmp，用tmp接收隊列的最后一個元素。
public int top() {
if (empty()) {
return -1;
}
if (!qu1.isEmpty()) {
int size = qu1.size();
int tmp = -1;
for (int i = 0; i < size; i++) {
tmp = qu1.poll();
qu2.offer(tmp);
}
return tmp;
}else {
// 沒彈出一個size都在變小一次
int size = qu2.size();
int tmp = -1;
for (int i = 0; i < size; i++) {
tmp = qu2.poll();
qu1.offer(tmp);
}
return tmp;
}
}
4.用棧模擬隊列
用棧模擬實現(xiàn)隊列也需要用到兩個棧，思路：
- 1.入隊：把數(shù)據(jù)放到第一個棧中
- 2.出隊：把第一個棧的全部元素放進第二棧當中，出st2這個棧當中的棧頂元素即可，如果st2為空，把st1里面所有的元素全部放到st2
- 3.當兩個棧為空 說明模擬的棧隊列為空
4.1 實例化兩個棧
class MyQueue {
private Stack<Integer> st1;
private Stack<Integer> st2;
public MyQueue() {
st1 = new Stack<>();
st2 = new Stack<>();
}
}
4.2 入隊push()
入棧直接全部放進第一個棧中
public void push(int x) {
st1.push(x);
}
4.3 出隊pop()
把第一個棧的全部元素放進第二棧當中，出st2這個棧當中的棧頂元素即可，如果st2為空，把st1里面所有的元素全部放到st2文章來源：http://www.zghlxwxcb.cn/news/detail-824106.html
public int pop() {
if(empty()) {
return -1;
}
if(st2.empty()) {
while(!st1.empty()) {
st2.push(st1.pop());
}
}
return st2.pop();
}
4.4 獲取隊頂元素peek()+隊列是否為空empty()
和出隊一樣，peek第二個棧的棧頂元素即可文章來源地址http://www.zghlxwxcb.cn/news/detail-824106.html
public int peek() {
if(empty()) {
return -1;
}
if(st2.empty()) {
while(!st1.empty()) {
st2.push(st1.pop());
}
}
return st2.peek();
}
public boolean empty() {
return st1.empty() && st2.empty();
}
到了這里，關于【Java數(shù)據(jù)結構 -- 隊列:隊列有關面試oj算法題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
