圖片來自 unsplash
棧 , 隊(duì)列 , 背包
- **棧 : **棧 , 在之前的一篇文章里面已經(jīng)講過了 , 遵從先入后出原則 (FILO) .
- **隊(duì)列 : **隊(duì)列 , 顧名思義 , 就像排隊(duì)一樣 , 先排隊(duì)的人先處理 , 遵從先入先出原則 (FIFO) .
- **背包 : **在這里的背包 , 就像平時(shí)用的背包一樣 , 用來裝東西 , 但是里面的東西順序不重要 . 而 棧 和 隊(duì)列 是有序的 . 得注意的是 , 背包 , 只能添加元素節(jié)點(diǎn) , 而不能刪除元素節(jié)點(diǎn) .
方法列表
- 棧 ( Stack )
-
void push(Item item): 添加一個(gè)元素節(jié)點(diǎn) . -
Item pop(): 刪除棧頂元素節(jié)點(diǎn) . -
boolean isEmpty(): 判斷棧是否為空 . -
int size(): 返回棧長(zhǎng)度 .
-
- 隊(duì)列 ( Queue )
-
void enqueue(Item item): 加入新元素節(jié)點(diǎn)到隊(duì)列 . -
Item dequeue(): 刪除最早進(jìn)入隊(duì)列的元素節(jié)點(diǎn) . -
boolean isEmpty(): 判斷隊(duì)列是否為空 . -
int size(): 返回隊(duì)列長(zhǎng)度 .
-
- 背包 ( Bag )
-
void add(Item item): 添加新元素節(jié)點(diǎn)到背包 . -
boolean isEmpty(): 判斷背包是否為空 . -
int size(): 返回背包大小 .
-
鏈表實(shí)現(xiàn)棧 , 隊(duì)列 , 背包
鏈表在之前的文章里已經(jīng)將過了 , 這里就不多說了 .
鏈表實(shí)現(xiàn)棧
public class Stack<Item> implements Iterable<Item> {
private Node head = null;
private int length = 0;
public Stack(){}
public void push(Item item) {
Node node = new Node(item);
node.next = this.head;
this.head = node;
length++;
}
public Item pop() {
Node node = this.head;
this.head = this.head.next;
this.length--;
return node.item;
}
public int size() {
return this.length;
}
public boolean isEmpty() {
return this.length == 0;
}
private class Node {
public Item item;
public Node next;
public Node(Item item) {
this.item = item;
}
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
@Override
public Spliterator<Item> spliterator() {
return null;
}
}
鏈表實(shí)現(xiàn)隊(duì)列
public class Queue<Item> implements Iterable<Item> {
private Node head = null; //最先入隊(duì)的元素
private int length = 0; //隊(duì)列長(zhǎng)度
private Node last = null; //最后入隊(duì)的元素
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
public Queue() {
}
public boolean isEmpty() {
return this.length == 0;
}
public int size() {
return this.length;
}
public void enqueue(Item item) {
Node node = new Node(item);
if (isEmpty()) {
this.head = this.last = node;
}else{
this.last.next = node;
this.last = node;
}
this.length++;
}
public Item dequeue() {
Item item = this.head.item;
this.head = this.head.next;
if (size()==1){
last =null;
}
this.length--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
}
鏈表實(shí)現(xiàn)背包
public class Bag<Item> implements Iterable<Item> {
private int length = 0;
private Node head;
public Bag(){}
private class Node {
public Item item = null;
public Node next = null;
public Node(Item item) {
this.item = item;
}
}
public int size(){
return this.length;
}
public boolean isEmpty(){
return this.length == 0;
}
public void add(Item item){
Node node = new Node(item);
if (isEmpty()){
this.head = node;
}else {
Node current = this.head;
while (current.next!=null){
current = current.next;
}
current.next = node;
}
this.length++;
}
@Override
public Iterator<Item> iterator() {
return new ListIterator<>();
}
private class ListIterator<Item> implements Iterator<Item> {
private Node current = head;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {}
}
}
