1 总述
1.1栈 stack
定义：栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。
特点：先进后出
基本操作：
入栈push,
出栈pop,
获取栈定元素peek，
判断栈是否为空isEmpty.
实现：栈可以用数组实现，也可以用链表实现。
栈的链表实现
栈的数组实现
1.2 队列queue
队列：先进先出
基本操作：
add添加元素到队尾
remove移除队头元素
peek获取队头元素
isEmpty方法判断队列是否为空
2 JSE中的实现
Dequeue是JSE定义的双端队列接口（double ended queue），定义了元素可以从两端插入和删除元素。可以利用Dequeue定义的方法实现栈和队列。在使用该接口时可以用对应的方法作为栈或者队列这2种数据结构的操作（下图中左边的方法其实调用了右边方法）：
栈和队列的数组实现是ArrayDeque，链表实现是LinkedList。其类关系图如下
2.1 栈实现
使用
public static void main(String[] args) {
Deque<Integer> stack=new ArrayDeque<Integer>(); //LinkedList<Integer>(); //stack can be implemented as array or linked list
for(int i=0;i<10;i++){ //add item in stack
stack.push(new Integer(i));
}//end for
System.out.println("stack size:"+stack.size());
if(!stack.isEmpty()){ //if stack is not empty, then do
Integer peekValue=stack.peek(); //get the last item inserted
System.out.println("peek item:"+peekValue.toString());
Integer popValue=stack.pop(); //remove the last item inserted
System.out.println("pop item:"+popValue.toString());
}//end if
}
输出
JSE的栈实现
1）ArrayDeque
当数组放满元素时，会将其元素复制到另一个更大容量的数组中。
/**
* Double the capacity of this deque. Call only when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1; //n*2
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = (E[])a;
head = 0;
tail = n;
}
ArrayDeque的实现和下面代码的实现原理类似，下面代码对理解栈的java实现比较容易理解：
// stack.java
// demonstrates stacks
// to run this program: C>java StackApp
////////////////////////////////////////////////////////////////
class StackX<E>
{
private int maxSize; // size of stack array
private E[] stackArray;
private int top; // top of stack
//--------------------------------------------------------------
public StackX(int s) // constructor
{
maxSize = s; // set array size
stackArray =(E[]) new Object[maxSize]; // create array
top = -1; // no items yet
}
//--------------------------------------------------------------
public void push(E j) // put item on top of stack
{
stackArray[++top] = j; // increment top, insert item
}
//--------------------------------------------------------------
public long pop() // take item from top of stack
{
return stackArray[top--]; // access item, decrement top
}
//--------------------------------------------------------------
public long peek() // peek at top of stack
{
return stackArray[top];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if stack is empty
{
return (top == -1);
}
//--------------------------------------------------------------
public boolean isFull() // true if stack is full
{
return (top == maxSize-1);
}
//--------------------------------------------------------------
} // end class StackX
////////////////////////////////////////////////////////////////
class StackApp
{
public static void main(String[] args)
{
StackX theStack = new StackX(10); // make new stack
theStack.push(20); // push items onto stack
theStack.push(40);
theStack.push(60);
theStack.push(80);
while( !theStack.isEmpty() ) // until it's empty,
{ // delete item from stack
long value = theStack.pop();
System.out.print(value); // display it
System.out.print(" ");
} // end while
System.out.println("");
} // end main()
} // end class StackApp
////////////////////////////////////////////////////////////////
2)LinkedList
push方法调用了likFirst方法
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
pop方法调用了removeFirst方法。
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
/**
* Unlinks non-null first node f.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
peek方法调用了
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
3.2 队列实现
使用
public static void main(String[] args) {
Deque<Integer> queue=new ArrayDeque<Integer>(); //LinkedList
for(int i=0;i<10;i++){ //insert item in queue
queue.add(new Integer(i));
}//end for
System.out.print("items in queue:");
for(Integer q: queue){
System.out.print(q.toString()+",");
}//end for
System.out.println();
if(!queue.isEmpty()){
Integer peekValue=queue.peek();
System.out.println("peek item:"+peekValue.toString());
}//end if
Integer popValue=queue.remove();
System.out.println("remove item:"+popValue.toString());
输出
1)ArrayDeque
其内部实现类似于下述代码，用front和rear记录当前队列的队头和队尾。用数组实现队列是需要，需要考虑当rear到达数组最大位置处，如何添加元素？
当rear指向数组最大位置处时，需要重新回来数组开始处，如此形成循环，如下图
// Queue.java
// demonstrates queue
// to run this program: C>java QueueApp
////////////////////////////////////////////////////////////////
class Queue
{
private int maxSize;
private E[] queArray;
private int front;
private int rear;
private int nItems;
//--------------------------------------------------------------
public Queue(int s) // constructor
{
maxSize = s;
queArray = (E())new Object[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//--------------------------------------------------------------
public void insert(E j) // put item at rear of queue
{
if(rear == maxSize-1) // deal with wraparound
rear = -1;
queArray[++rear] = j; // increment rear and insert
nItems++; // one more item
}
//--------------------------------------------------------------
public E remove() // take item from front of queue
{
E temp = queArray[front++]; // get value and incr front
if(front == maxSize) // deal with wraparound
front = 0;
nItems--; // one less item
return temp;
}
//--------------------------------------------------------------
public E peekFront() // peek at front of queue
{
return queArray[front];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return (nItems==0);
}
//--------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return (nItems==maxSize);
}
//--------------------------------------------------------------
public int size() // number of items in queue
{
return nItems;
}
//--------------------------------------------------------------
} // end class Queue
////////////////////////////////////////////////////////////////
class QueueApp
{
public static void main(String[] args)
{
Queue theQueue = new Queue(5); // queue holds 5 items
theQueue.insert(10); // insert 4 items
theQueue.insert(20);
theQueue.insert(30);
theQueue.insert(40);
theQueue.remove(); // remove 3 items
theQueue.remove(); // (10, 20, 30)
theQueue.remove();
theQueue.insert(50); // insert 4 more items
theQueue.insert(60); // (wraps around)
theQueue.insert(70);
theQueue.insert(80);
while( !theQueue.isEmpty() ) // remove and display
{ // all items
E n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
} // end main()
} // end class QueueApp
////////////////////////////////////////////////////////////////
2）LinkdedList
add方法将元素加入链表末端
remove方法移除链表头元素
peek方法获取链表头元素
isEmpty方法判断队列是否为空