图解数据结构和算法——栈和队列

栈

什么是栈进栈和出栈栈的操作代码实现 队列

什么是队列队列的实现

同顺序表和链表一样，栈也是用来存储逻辑关系为“一对一”数据的线性存储结构

栈是一种只能从表的一端存取数据且遵循“先进后出”（后进先出）的原则的线性存储结构
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿上图来说，栈顶元素为4，同理，栈底元素为1

基于栈结构的特点，在实际应用中，通常只会执行以下两种操作：

向栈中添加元素，此过程叫进栈或入栈（压栈)向栈中取出元素，此过程叫出栈或弹栈 栈的操作

栈的具体实现有两种方式：顺序栈（采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构）；链栈（采用链式存储结构实现栈结构）面向接口编程，用户关心所需要的调用方法即可底层有多重实现方式，在这里用Array（顺序栈）的方法来实现一个栈

		public interface Stack {
				void push(E e);
				E pop();
				E peek();
				int getSize();
				boolean isEmpty();
			}

顺序栈元素“入栈”

模拟存储123过程

首先定义一个空栈，即Array数组为空，top指向栈底，初始值为-1
向栈中添加1元素，这个时候top++，即指向数组的0位置
接下来依次将2元素，3元素放进去，top值变为2

顺序栈元素“出栈”

将栈顶的元素拿出，top–
只有先将2，3元素全部出栈后，1才能出栈 代码实现

Array数组封装见数组篇：https://blog.csdn.net/weixin_47383392/article/details/123501217

public class ArrayStack implements Stack {

    private Array array;
    public ArrayStack(){
        array = new Array();
    }
    public ArrayStack(int capacity){
        array = new Array(capacity);
    }

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append("Stack: [");
        for(int i=0;i 
测试代码：
 
public class Main {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack<>();
        for(int i=0;i<5;i++){
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }

}
 
队列 
什么是队列 
队列：和栈一样，也是一种对数据的"存"和"取"有严格要求的线性存储结构。
 与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出。如图所示。
 
 
 
 
通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。
 
 
队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。
 
队列存储结构的实现有以下两种方式：
 
顺序队列：在顺序表的基础上实现的队列结构；链队列：在链表的基础上实现的队列结构 
实际生活中，队列的应用随处可见，比如排队买 XXX、医院的挂号系统等，采用的都是队列的结构。
 
队列的实现 
接口 
public interface Queue {

    void enqueue(E e);
    E dequeue();
    E getFront();
    boolean isEmpty();
    int getSize();
}
 
接口实现 
public class ArrayQueue implements Queue{

    private Array array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }
    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append("Queue: front [");
        for(int i=0;i 
主方法测试 
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue<>();
        for(int i=0;i<8;i++){
            queue.enqueue(i);
            System.out.println(queue);
            if(i%3==0){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }