栈和队列的知识总结---数据结构_栈是只能从一端插入数据,是一种 的数据结构。队列是只能从一端插入数据,从另

一、栈和队列是什么
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。
队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
二、栈和队列的特点
1.栈的特点：先进后出，后进先出。（FILO）
2.队列的特点：先进先出；以什么样的方式进来，就以什么样的方式出去。（FIFO）
3.队列的分类：队列可以分为单向队列（Queue）和双端队列（Deque）
三、常用的方法以及使用
Queue常用的方法有：
1.add（E e）
–将制定元素e插入到此队列中，如果可以立即执行此操作，而不会违反容量限制，true在成功后被返回。如果当前没有可用空间，则抛出异常。
2.remove（）
–检索并删除此队列的头，如果没有的话，会抛出异常
3.element（）
–检索，但不删除队列的头。
4.offer（E e）
–在不违反容量限制的情况下立即执行，将指定的元素插入到此队列中
5.poll()
–检索并删除此队列的头，如果队列为空，则返回null。
6.peek（）
–检索但不删除此队列的头，如果队列为空，则返回null。

注意：前三个方法是通过异常通知调用者发生错误
后三个是通过返回特殊值通知调用者发生错误。
Deque的常用方法
1.addFirst()/offerFirst()–插入指定元素到队列首部
2.removeFirst()/pollFirst()—检索并删除队列的第一个元素
3.getFirst()/peekFirst()–查看队列但不删除的第一个元素
4.addLast()/offerLast()—给队列尾部添加元素
5.removeLast()/pollLast()—删除最后的一个元素
6.getLast（）/peekLast()—查看最后一个元素，但不删除它

注意：deque接口是继承了queue接口的，所以queue里面有的方法deque也有。
stack是一个类，java自带。
在stack类里面：常用的方法是：
push(E item)—将一个项目推到堆栈的顶部。
pop（）—在这个堆栈的顶部删除对象，
peek（）—查看栈顶的元素，不删除它。

下面是对方法的简单实用：
deque:

package com.caoliduo.Queue;

import java.util.LinkedList;
import java.util.Deque;
public class DequeDemo {
    public static void main(String[] args){
        Deque <Integer> deque =new LinkedList<>();
        deque.add(1);
        deque.add(2);
        deque.add(3);
        deque.add(4);
        deque.add(5);
        deque.add(6);
        System.out.println(deque.removeLast());
        System.out.println(deque.removeFirst());
        System.out.println(deque);
        System.out.println(deque.contains(9));
        System.out.println(deque.getFirst());
        System.out.println(deque.peekLast());
        while(deque!=null){

            if(!deque.isEmpty()){
                System.out.println(deque.peekFirst());
                System.out.println(deque.removeFirst());
            }
            if(!deque.isEmpty()){
                System.out.println(deque.peekLast());
                System.out.println(deque.removeLast());
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Queue:

package com.caoliduo.Queue;

import java.util.Deque;
import java.util.LinkedList;
public class MyQueue {
    private Deque<Integer>s1;
    private Deque<Integer>s2;
    public MyQueue(){
        s1=new LinkedList<>();
        s2=new LinkedList<>();
    }
    public void push(int x){
        s2.push(x);
    }
    public int pop(){
        if(s1.isEmpty()){
            while(!s2.isEmpty()){
                Integer e=s2.pop();
                s1.push(e);
            }
        }
        return s1.pop();
    }
    public boolean empty(){//判断是否为空
        return s1.isEmpty()&&s2.isEmpty();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

stack：

package com.caoliduo.Queue;
import java.util.Deque;
import java.util.LinkedList;

public class DequeStackDemo {
    public static void main(String[] args){
        Deque<Integer> stack=new LinkedList<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19