Evalsry blog | 详情

栈

定义：

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

实现：

用单链表实现栈：

/**
结点存储值
*/
public class Node<V>{
    public V value ;
    public Node<V> next;
    
    public Node<V v> {
        value = v;
        next = null;
    }
}

public class MyStack<V> {
    private Node<V> head;
    private int size;
    
    public MyStack(){
        head = null;
        size = 0;
    }
    
    public boolean isEmpty() {
		return size == 0;        
    }
    
    public int size(){
        return size;
    }
    
    public void push(V value){
        Node<V> cur = new Node<>(value);
        if(head == null){
            head = cur;
        } else {
            cur.next = head;
            head = cur;
        }
        size++;
    }
    
    public void pop(){
        V ans = null;
        if(head != null){
            ans = head.value;
            head = head.next;
            size--;
        }
        return ans;
    }
    
    public V peek(){
        return head != null? head.value : null;
    }
}

最小栈：

题目：实现一个特殊的栈,在实现栈的基础功能的基础上,再实现返回栈中最小元素的操作

思路：

1. 实现两个栈，一个栈-stackData存放数据，另外一个栈-stackMin存放当前每一个元素对应的最小元素
 	1. 有两种放法：
     	1. 第一种：只存放当前栈中两个相邻范围内的最小值--stackData存放6，7，8，9，5，7，8，9这八个元素，则对应的stackMin则存放6，5这两个元素，减少空间
     	2. 第二种：每次存放当前元素对应的最小元素 ,--stackData存放6，7，8，9，5，7，8，9这八个元素，则对应的stackMin则存放6,6,6,6,5,5,5,5这8个元素

//放法一：
public class MyStack1{
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    
    public MyStack1(){
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    
    //获取当前栈中最小值
    public int getMin(){
        if(this.stackMin.isEmpty()){
            throw new RunTimeException("Your stack is empty");
        }
        return this.stackMin.peek();
    }
    
    public void push(int val){
        this.stackData.push(val);
        if(this.stackMin.isEmpty()){
            this.stackMin.push(val);
        } else if (val <= this.getMin()) {
            this.stackMin.push(val);
        }
    }
    
    public int pop(){
        if(this.stackData.isEmpty()){
            throw new RunTimeException("Your stack is empty");
        }
        int val = this.stackData.pop();
        if(val == this.getMin()){
            this.stackMin.pop();
        }
        return val;
    }
}

//放法二
public class MyStack2{
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    
    public MyStack1(){
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    
    //获取当前栈中最小值
    public int getMin(){
        if(this.stackMin.isEmpty()){
            throw new RunTimeException("Your stack is empty");
        }
        return this.stackMin.peek();
    }
    
    public void push(int val){
        this.stackData.push(val);
        if(this.stackMin.isEmpty()){
            this.stackMin.push(val);
        } else if (val <= this.getMin()) {
            this.stackMin.push(val);
        } else {
            this.stackMin.push(this.getMin());
        }
    }
    
    public int pop(){
        if(this.stackData.isEmpty()){
            throw new RunTimeException("Your stack is empty");
        }
        int val = this.stackData.pop();
        this.stackMin.pop();
        return val;
    }
}

队列

定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

实现

一：用单向链表实现队列

public class MyQueue<V> {
    private Node<V> head;
    private NOde<V> tail;
    private int size;
    
    public MyQueue {
        head = null;
        tail = null;
        size = 0;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
    public int siez(){
        return size;
    }
    
    public void offer(V value) {
        NOde<V> cur = new NOde<V>(value);
        if(tail == null){
            head = cur;
            tail = cur;
        } else {
            tail.next =cur;
            tail = cur;
        }
        size++;
    }
    
    public V poll(){
        V ans = null;
        if(head != null){
            ans = head.value;
            head = head.next;
            size--;
        }
        if(head == null){
            tail = null;
        }
        return ans;
    }
    
    public V peek(){
        V ans = null;
        if(head != null){
            ans = head.value;
        }
        return ans;
    }
}

二：数组实现队列

思路：

声明两个指针，分别存储当前数组中pushi和popi的位置，声明一个变量size，存储当前队列的元素总个数
pushi存放当前可以插入元素的存储位置，通过size判断，size = limit(arr.length),数组满了，则不能插入
1. 插入完成后，pushi++,如果pushi再arr.length-1位置，则回到0位置
popi存放当前可以弹出元素的位置，通过size判断，size=0，没有元素，则不能弹出

public class MyQueue{
    private int[] arr;
    private int size;
    private int pushi;
    private int popi;
    private final int limit;
    
    public MyQueue(int limit){
        arr[] = new int[limit];
        pushi = 0;
        popi = 0;
        size = 0;
        this.limit = limit;
    }
    
    //返回当前下标的下一个位置，数组末尾则直接到arr[0]的位置
    public nextIndex(int i){
        return i < limit - 1? i+1 : 0;
    }
    
    public void push(int val){
        if(size == limit){
            throw new RuntimeException("队列满了，不能再加了");
        }
        size++;
        arr[pushi] = val;
        pushi = nextIndex(pushi);
    }
    
    public int pop(){
        if(size == 0){
            throw new RuntimeException("队列满了，不能再加了");
        }
        size--;
        int val = arr[popi];
        popi = nextIndex(popi);
        return popi;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }
}

双端队列

定义

双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可（也只能）在线性表的两端进行插入和删除。

实现

思路

1. 用双向链表实现双端队列，声明头指针-head和尾指针-tail，分别指向双向链表的头和尾节点
2. 两端插入数据，则是先根据head==null,判断当前队列有没有值
 	1. 没有，则直接将head和tail指向当前数据
 	2. 有数据，就在头节点的head节点之前插入一个节点cur，并将head指向cur
3. 两端删除数据，则是先根据head == null，判断当前队列有没有值
 	1. 没有，则返回null
 	2. 有，则将头节点的值返回，同时将head -> head.next,并将涉及到的节点的地址信息删除

public class Node<T>{
    public T value;
    public Node<T> next;
    public Node<T> last;
    
    public Node（T value){
        this.value = value
    };
}

public class DoubleEndsQueue<T>{
    private Node<T> head;
    private Node<T> tail;
    
    /**
    1.生成一个节点cur，如果当前队列只有一个节点，头尾两个节点都指向他
    2.cur.next -> head，head.last -> cur,head -> cur
    */
    public void addFromHead(T val){
        Node<T> cur = new Node<>(val);
        if(head == null){
            head = cur;
            tail = cur;
        } else {
            cur.next = head;
            head.last = cur;
            head = cur;
        }
    }
    
    public void addFromBottom(T val){
        Node<T> cur = new Node<>(val);
        if(tail == null){
            head = cur;
            tail = cur;
        } else {
            cur.last = tail;
            tail.next = cur;
            tail = cur;
        }
    }
    
    public T popFromHead(){
        if(head == null){
            return null;
        }
        Node<T> cur = head;
        if(head == tail){
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.last = null;
            cur.next = null;
        }
        return cur.value;
    }
    
    public T popFromBottom(){
        if(head == null){
            return null;
        }
        Node<T> cur = tail;
        if(head == tail){
            head = null;
            tail = null;
        } else {
            tail = tail.last;
            cur.last = null;
            tail.next = null;
        }
        return cur.value;
    }
    
    public boolean isEmpty(){
        return head == null;
    }
}

双端队列实现栈和队列

栈：

思路：

栈因为后进先出的特性，只需要调用队列的addFromBottom和popFromBottom就可以完成相关功能

public class MyStack<T>{
    private DoubleEndsQueue<T> queue;
    
    public MyStack(){
        this.queue = new DoubleEndsQueue<T>();
    }
    
    public void push(T val){
        this.queue.addFromBottom(val);
    }
    
    public T pop(){
        return this.queue.popFromBottom();
    }
    
    public boolean isEmpty(){
        return this.queue.isEmpty();
    }
}

队列

思路：

直接用addFromBottom和popFromHead完成功能

public class MyQueue<T>{
	private DoubleEndsQueue<T> queue;
    
    public MyQueue(){
        this.queue = new DoubleEndsQueue<T>();
    }
    
    public void push(T val){
        this.queue.addFromHead(val);
    }
    
    public T pop(){
        return this.queue.popFromBottom();
    }
    
    public boolean isEmpty(){
        return this.queue.isEmpty();
    }
}

栈实现队列

思路：

栈是后进先出，队列是先进先出，可以先声明两个栈，一个栈-stackPush，一个栈-stackPop，
将stackPush中的元素全部倒入stackPop中，原本push栈中bottom中的元素就在pop栈中head的位置，就可以像队列一样弹出数据

public class MyQueue{
    private Stack<Integer> stackPush;
    private Stack<Integer> stackPop;
    
    //把push栈中的元素倒入pop栈中,将这个方法抽取出来，以后其他方法调用该方法后，都能确保stackPop有值，且不会叠加
    private void pushToPop(){
        if(stackPop.isEmpty()){
            while(!stackPush.isEmpty){
                stackPop.push(stackPush.pop());
            }
        }
    }
    
    public void add(int val){
        this.stackPush.push(val);
        this.pushToPop();
    }
    
    public int pop(){
        if(this.stackPush.isEmpty() && this.stackPop.isEmpty()){
            throw new RunTimeException("Your Queue is Empty");
        }
        this.pushToPop();
        return stackPop.pop();
    }
    
    public int peek(){
        if(this.stackPush.isEmpty() && this.stackPop.isEmpty()){
            throw new RunTimeException("Your Queue is Empty");
        }
        this.pushToPop();
        return stackPop.peek();
    }
}

队列实现栈

思路：

声明两个队列，一个队列-queue，一个队列-help
队列queue存放当前元素
返回当前栈的head元素，则将queue的size-1个元素全部导入到help，然后将queue的最后一个元素弹出，并将help和size互换

public class TwoQueueStack<T>{
    public Queue<T> queue;
    public Queue<T> help;
    
    public TwoQueueStack(){
        this.queue = new LinkedList();
        this.help = new LinkedList();
    }
    
    public void push(T val){
        queue.offer(val);
    }
    
    public T poll(){
        while(queue.size() > 1){
            help.offer(queue.poll());
        }
        T ans = queue.poll();
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return ans;
    }
    
    public T peek(){
        while(queue.size() > 1){
            help.offer(queue.poll());
        }
        T ans = queue.poll();
        help.offer(ans);
        Queue<T> tmp = queue;
        queue = help;
        help = tmp;
        return ans;
    }
}