Java数据结构-栈

1，Java中的栈

1）Java栈是一种特殊的线性表。
栈：只能在一端进行push和pop操作eg：Stack
线性表：可以在任意位置add和remove操作eg：Vertor

2，Stack

1）Java数据结构-栈Stack
java.util.Stack<E>represents a last-in-first-out (LIFO) stack of objects一个后进先出的栈。
底层是数组protected Object[] elementData;
继承Vertor类，包含了5中栈的操作。with five operations that allow a vector to be treated as a stack.

image.png

2）public E push(E item) 入栈，调用父类Vertor中的同步方法addElement
Pushes an item onto the top of this stack.

image.png

image.png

3）public synchronized E pop() 出栈，调用父类Vertor中的removeElementAt(int index)同步方法
Removes the object at the top of this stack and returns that object

image.png

4）public synchronized E peek() 获取栈顶元素，不会移除，调用父类的elementAt方法
Looks at the object at the top of this stack without removing it from the stack.

image.png

5） public boolean empty() Tests if this stack is empty.
6）public synchroinzed int search(Object o) 栈中查找一个元素，返回第一个位置。the 1-based position from the top of the stack， return -1 indicates that the object is not on the stack.

image.png

3，Vector简介

1）Vector底层是数组protected Object[] elementData;
2）线程安全的成员方法。

image.png

3）扩容elementData = Arrays.copyOf(elementData, newCapacity);

image.png

4，LinkedList模拟栈

1）底层实现非线程安全的

image.png

头节点transient Node<E> first;
尾节点transient Node<E> last;
长度transient int size = 0;
2）添加一个元素

image.png

image.png

3）移除一个元素

image.png

final Node<E> next = x.next;
final Node<E> prev = x.prev;
prev.next = next;
next.prev = prev;
4）获取一个元素

image.png

5）模拟栈
push：

image.png

pop：

image.png

peek：

image.png