数据结构（二）基础-栈和队列
一 栈
1 简介
栈（stack），是一种线性存储结构。属于线性表，可分为顺序栈和链栈。
2 特点
（1）栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
（2）向栈中添加/删除数据时，只能从栈顶进行操作。
（3）栈只能从表的一端存取数据，另一端是封闭的。
栈通常包括的三种操作：push、peek、pop。
- push -- 向栈中添加元素。
- peek -- 返回栈顶元素。
- pop -- 返回并删除栈顶元素的操作。
3 出入栈
3.1 出栈
出栈示意图：
3.2 入栈
入栈示意图：
4 栈的Java实现
java提供了栈的java实现：java.util#Stack.java
下面一个顺序栈简单java实现：
/**
* Description: 实现简单顺序栈
* created by H on 2020/5/14
*
* @author H
*/
public class GeneralArrayStack<T> {
private static final int DEFAULT_SIZE = 12;
private T[] elementData;
private int elementCount;
public GeneralArrayStack(Class<T> type) {
this(type, DEFAULT_SIZE);
}
@SuppressWarnings("unchecked")
public GeneralArrayStack(Class<T> type, int size) {
// elementData = new T[size]; // error
elementData = (T[]) Array.newInstance(type, size);
elementCount = 0;
}
/**
* Push {@link T} data to stack
*
* @param item T data
* @return T data
*/
public T push(T item) {
addElement(item);
return item;
}
/**
* Add object to the array
*
* @param element the object to be added
*/
public synchronized void addElement(T element) {
elementData[elementCount++] = element;
}
/**
* Get top of stack element value
*
* @return the object at the top of stack
* @throws EmptyStackException if this stack is empty.
*/
public synchronized T peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementData[len - 1];
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return the object at the top of stack
* @throws EmptyStackException if this stack is empty.
*/
public synchronized T pop() {
int len = size();
T ret = peek();
removeElement(len - 1);
return ret;
}
/**
* Remove object to the array
*
* @param index the index of the object to remove
*/
public synchronized void removeElement(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + ">=" + elementCount);
} else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index + "< 0");
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null;
}
/**
* Gets the size of the stack
*
* @return stack size
*/
public int size() {
return elementCount;
}
/**
* Is the stack empty
*
* @return is the stack empty state
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* print all the stack element value
*/
public void printStack() {
if (isEmpty()) {
System.out.println("Stack is Empty");
return;
}
System.out.println("Stack size is " + size());
int i = size() - 1;
while (i >= 0) {
System.out.println(elementData[i]);
i--;
}
}
}二 队列
1 简介
队列（Queue），是一种线性存储结构。属于线性表，可分为顺序队列和链队列。
2 特点
(1) 队列中数据是按照"先进先出（FIFO, First-In-First-Out）"方式进出队列的。
(2) 队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。
队列通常包括的两种操作：入队列和出队列
3 出入队列
3.1 出队列
出队列示意图：
3.2 入队列
入队列示意图：
4 队列的java实现
在java提供了Queue接口，它是实现类都是队列。
下面是简单实现顺序队列（Java），删除操作直接遍历数组前移一位，而不是使用queueHeaderIndex和queueTailIndex来控制：
/**
* Description: 实现简单顺序队列
* created by H on 2020/5/14
*
* @author H
*/
public class GeneralArrayQueue<E> {
private static final int DEFAULT_SIZE = 12;
private Object[] elementData;
private int elementCount;
public GeneralArrayQueue() {
this(DEFAULT_SIZE);
}
public GeneralArrayQueue(int size) {
elementData = new Object[size];
elementCount = 0;
}
/**
* Appends the specified element to the end of this array
*
* @param item element to be appended to this array
* @return {@code true}
*/
public boolean add(E item) {
elementData[elementCount++] = item;
return true;
}
/**
* Appends the specified element to the end of this array
*
* @param e element to be appended to this array
* @return {@code true}
*/
public boolean offer(E e) {
return add(e);
}
/**
* Retrieves, but does not remove, the head (first element) of this array.
*
* @return the head of this array, or {@code null} if this array is empty
*/
public E peek() {
return elementAt(0);
}
/**
* Retrieves, but does not remove, the head (first element) of this array.
*
* @return the head of this array
* @throws NoSuchElementException if this array is empty
*/
public E element() {
return getFirst();
}
/**
* Retrieves and removes the head (first element) of this array.
*
* @return the head of this array, or {@code null} if this array is empty
*/
public E poll() {
final E f = elementAt(0);
return (f == null) ? null : removeFirst(f);
}
/**
* Retrieves and removes the head (first element) of this array.
*
* @return the head of this array
* @throws NoSuchElementException if this array is empty
*/
public E remove() {
return removeFirst();
}
/**
* Returns the number of elements in this array
*
* @return the number of elements in this array
*/
public int size() {
return elementCount;
}
/**
* Is the array empty
*
* @return is the array empty
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Returns the first element in this array.
*
* @return the first element in this array
* @throws NoSuchElementException if this array is empty
*/
public E getFirst() {
final E f = elementAt(0);
if (f == null) {
throw new NoSuchElementException();
}
return f;
}
/**
* Removes and returns the first element from this array.
*
* @return the first element from this array
* @throws NoSuchElementException if this array is empty
*/
public E removeFirst() {
final E f = elementAt(0);
if (f == null) {
throw new NoSuchElementException();
}
return removeFirst(f);
}
/**
* Removes and returns the first element from this array.
*
* @param f the first element from this array
* @return the first element from this array
*/
public E removeFirst(E f) {
if (size() - 1 >= 0) System.arraycopy(elementData, 1, elementData, 0, size() - 1);
elementCount--;
return f;
}
/**
* Returns the element at the specified index.
*
* @param index an index into this array
* @return the element at the specified index
*/
public E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
// Positional Access Operations
@SuppressWarnings("unchecked")
private E elementData(int index) {
return (E) elementData[index];
}
}三 最后
推荐一篇：栈和队列 ，个人感觉不错。
参考引用：字节跳动Android面试指南
提取码：
管理员设置 回复 可见隐藏内容
