栈与队列-java实现

<h2>栈和队列算是最最基础的两种数据结构了，两种数据结构也很好理解。</h2>

<h3>栈：先进后出。</h3>

<h3>队列：先进先出。</h3>

对于这两种数据结构我实在也找不出更加通俗易懂的解释，因为实在基础，简单。还是直接上代码好了。

<blockquote>用数组方式实现栈和队列</blockquote>
栈的数组实现方式
<pre>
'''
package com.example.linkedlist;

import java.util.Iterator;

public class ArrayStack<Item> implements Iterable<Item>{
private Item stack[] = (Item[])new Object[20];
private int N = 0;
public boolean isEmpty(){
return N==0;
}
public int size(){
return N;
}
private void resize(int max){
Item temp[] = (Item[])new Object[max];
for(int i=0;i<N;i++){
temp[i] = stack[i];
}
stack = temp;
}
public void push(Item item){
if(N == stack.length){
resize(2*stack.length);
}
stack[N++] = item;
}
public Item pop(){
Item item = stack[N--];
stack[N] = null;//避免对象游离
if(N >0 && N == stack.length/4){
resize(stack.length/2);
}
return item;
}
@Override
public Iterator<Item> iterator() {
return new ArrayStackIterator();
}
private class ArrayStackIterator implements Iterator<Item>{
private int index = N;
@Override
public boolean hasNext() {
return index > 0;
}

    @Override
    public Item next() {
        return stack[--index];
    }

    @Override
    public void remove() {
        // TODO Auto-generated method stub
        
    }
    
}

}
'''
</pre>

队列的数组实现方式
<pre>
<code>
import java.util.Iterator;

public class ArrayQueue<Item> implements Iterable<Item>{

private Item queue[] = (Item[]) new Object[20];
private int N = 0;
public boolean isEmpty(){
    return N == 0;
}
public int size(){
    return N;
} 
private void resize(int max){
    Item[] temp = (Item[])new Object[max];
    for(int i=0;i<N;i++){
        temp[i] = queue[i];
    }
    queue = temp;
}
public void enqueue(Item item){
    queue[N++] = item;
    if(N > 0 && N == queue.length){
        resize(queue.length*2);
    }
}
public Item dequeue(){
    Item item = queue[0];
    for(int i=0;i<N;i++){
        queue[i] = queue[i+1];
    }
    queue[N--] = null;//避免对象游离
    if(N <= queue.length/4){
        resize(queue.length/2);
    }
    return item;
}
@Override
public Iterator<Item> iterator() {
    // TODO Auto-generated method stub
    return new ArrayQueueIterator();
}
private class ArrayQueueIterator implements Iterator{

    @Override
    public boolean hasNext() {
        
        return N != 0;
    }

    @Override
    public Object next() {
        Item item = queue[0];
        for(int i=0;i<N;i++){
            queue[i] = queue[i+1];
        }
        queue[N--] = null;//避免对象游离
        if(N <= queue.length/4){
            resize(queue.length/2); 
        }
        return item;
    }
    
}

}
</code>
</pre>
<h3>代码很简单，但是有两个点需要注意，一个是resize()函数，即动态调整数组大小，这也是数组实现栈和队列的缺点之一，一个是每次出栈或者出队列都要将其值为null，来避免对象游离。
然后另一个缺点是其时间复杂度，这点在队列中尤为明显，每次出列都要将队列数组向前移位，然后将最后一位置为null。所以采用链表的方式通过移动指针会很方便。</h3>
<blockquote>用链表方式实现栈和队列</blockquote>
栈的链表实现方式
<pre>
''
package com.example.linkedlist;

public class Stack<Item>{
private Node first;
private int N = 0;
private class Node {
Item item;
Node next;
}
public boolean isEmpty(){
return first == null;
}
public int size(){
return N;
}
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop(){
Item item = first.item;
first = first.next;
return item;
}
}
''</pre>
队列的链表实现方式
<pre>
'''
public class LinkedQueue<Item>{
private Node head;
private Node first;
private int N = 0;
private class Node {
Item item;
Node next;
}
public boolean isEmpty(){
return head == null;
}
public int size(){
return N;
}
public void enqueue(Item item){
Node temp = new Node();
temp.item = item;
if(first == null){
first = temp;
head = first;
return;
}
first.next = temp;
first = first.next;
N++;
}
public Item dequeue(){
Item item = head.item;
head = head.next;
N--;
return item;
}

}
'''
</pre>

---

<h2>以上就是最基础的两种数据结构了，当然也是往后实现树，图等复杂数据结构的基础知识！<h2>