先進先出隊列（或簡稱隊列）
是一種基于先進先出（FIFO）策略的集合類型。
典型的先進先出隊列
隊列的API:
public class Queue<Item> implements Iterable<Item>
Queue() 創(chuàng)建空隊列
void enqueue(Item item) 添加一個元素
Item dequeue() 刪除最早添加的元素
boolean isEmpty() 隊列是否為空
int size() 隊列中的元素數(shù)量
隊列的鏈表實現(xiàn)
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item> {
private class Node{
//定義節(jié)點嵌套類
Item item;
Node next;
}
private Node first;//指向最早添加的節(jié)點的鏈接
private Node last;//指向最近添加的節(jié)點的鏈接
private int count;//隊列中元素的數(shù)量
public Queue(){
first = null;
last = null;
count = 0;
}
public void enqueue(Item item){
//向表尾添加元素
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldLast.next = last;
count++;
}
public Item dequeue(){
//從表頭刪除元素
if (isEmpty()){
return null;
}
Item item = first.item;
first = first.next;
count--;
if (isEmpty())last = null;
return item;
}
public boolean isEmpty(){
return count==0;
}
public int size(){
return count;
}
@Override
public Iterator<Item> iterator() {
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item>{
@Override
public boolean hasNext() {
return !isEmpty();
}
@Override
public Item next() {
return dequeue();
}
}
}
下壓棧（或簡稱棧）
是一種基于后進先出（LIFO）策略的集合類型
下壓棧上的操作
棧的API：
/*
* public class Stack<Item> implements Iterable<Item>
* Stack() 創(chuàng)建一個空棧
* void push(Item item) 添加一個元素
* Item pop() 刪除最近添加的一個元素
* boolean isEmpty() 棧是否為空
* int size() 棧中元素的數(shù)量
* */
棧的鏈表實現(xiàn)
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item>{
private class Node{
//定義了節(jié)點嵌套類
Item item;
Node next;
}
private Node first; //棧頂,最近添加的元素
private int count; //棧中元素的數(shù)量
//無參構(gòu)造方法
public Stack(){
first = null;
count = 0;
}
public void push(Item item){
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
count++;
}
public Item pop(){
if (isEmpty()) return null;
Item item = first.item;
first = first.next;
count--;
return item;
}
public boolean isEmpty(){
return count == 0;
}
public int size(){
return count;
}
@Override
public Iterator<Item> iterator() {
return new StackIterator<Item>();
}
private class StackIterator<Item> implements Iterator<Item>{
@Override
public boolean hasNext() {
return !isEmpty();
}
@Override
public Item next() {
return (Item) pop();
}
}
}
挑戰(zhàn)------用有限個棧實現(xiàn)一個隊列
解答：用兩個棧實現(xiàn)一個隊列，棧0專門用來push，棧1專門用來pop戳粒，每當需要dequeue的時候，就將棧0中的元素放入棧1中，然后就可以將先進入隊列的元素pop出來了绑咱，如果需要連續(xù)pop那就直接pop就行，讓后在需要enqueue的時候就將棧1中的元素push回棧0枢泰，然后就可以繼續(xù)push了描融。雖然中間遇到多次迷之bug，但是好歹也是敲出來了??衡蚂，果然在開始敲代碼之前先理清一下思路比較好窿克，下面上代碼：
import java.util.Iterator;
/**
* public class Queue<Item> implements Iterable<Item>
* Queue() 創(chuàng)建空隊列
* void enqueue(Item item) 添加一個元素
* Item dequeue() 刪除最早添加的元素
* boolean isEmpty() 隊列是否為空
* int size() 隊列中的元素數(shù)量
*/
public class Squeue<Item> implements Iterable<Item>{
private Stack<Item>[] stacks;
private int count;
public Squeue(){
stacks = new Stack[2];
stacks[0] = new Stack<Item>();
stacks[1] = new Stack<Item>();
count = 0;
}
public void enqueue(Item item){
if (stacks[0].size() == 0&&count!=0){
for (int i = 0;i < count; i++){
stacks[0].push(stacks[1].pop());
}
}
stacks[0].push(item);
System.out.println(item);
count++;
System.out.println(count);
}
public Item dequeue(){
if (isEmpty()) return null;
if (stacks[0].size()==0) {
count--;
return stacks[1].pop();
}
for (int i = 0; i < count; i++){
stacks[1].push(stacks[0].pop());
}
Item item = stacks[1].pop();
count--;
System.out.println(count);
return item;
}
public boolean isEmpty(){
return count==0;
}
public int size(){
return count;
}
@Override
public Iterator<Item> iterator() {
return new SIterator<>();
}
private class SIterator<Item> implements Iterator<Item>{
@Override
public boolean hasNext() {
return !isEmpty();
}
@Override
public Item next() {
return (Item) dequeue();
}
}
}
aha!忘了寫注釋
討論一下隊列和棧的鏈表實現(xiàn)和數(shù)組實現(xiàn)
鏈表實現(xiàn)因為要創(chuàng)建新對象調(diào)整關(guān)系等導(dǎo)致了總的來說速度要慢于數(shù)組實現(xiàn)，但數(shù)組實現(xiàn)中會不時因為數(shù)組大小的調(diào)整而出現(xiàn)一次緩慢操作讳窟，這樣就使得需要穩(wěn)定快速的操作的情況下數(shù)組實現(xiàn)不合適让歼，但是如果只考慮總的時間消耗的話，數(shù)組實現(xiàn)是要更快的丽啡。
資源及參考
本筆記是學(xué)習(xí)普林斯頓大學(xué)算法課程以及閱讀其教材《算法》第四版所作
