数据结构（java）栈与队列

栈：（先进后出）

        入栈:
1.普通栈一定要放、最小栈放的原则是:

    *如果最小栈是空的，那么放
    *如果最小栈的栈顶元素没有当前的元素小，则放
2.如果要放的的元素小于等于最小栈栈顶元素可以放吗?放
       出栈:
   需要判断 出栈的元素 和 栈顶元素是否相同，相同则最小栈也要出栈

队列：（先进先出）

      单链表实现队列：

public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first = null;public ListNode last = null;public int usedSize = 0;public void offer(int val) {ListNode node = new ListNode(val);if(isEmpty()) {first = last = node;}else {last.next = node;node.prev = last;last = last.next;}usedSize++;}public int poll() {if(isEmpty()) {return -1;}int val = first.val;first = first.next;if(first != null) {first.prev = null;}usedSize--;return val;}public int peek() {if(isEmpty()) {return -1;}return first.val;}public boolean isEmpty() {return usedSize == 0;}}

设置循环队列：

class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem = new int[k+1];}//入队列 public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}//出队列 public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;return true;}//得到队头元素 public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1)%elem.length == front;}
}

用队列实现栈：

import java.util.LinkedList;
import java.util.Queue;class MyStack {private Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {// 每次push时，将新元素加入队列，然后将前面的元素依次出队再入队// 这样新元素就在队列前端，模拟了栈的后进先出特性queue.offer(x);int size = queue.size();for (int i = 0; i < size - 1; i++) {queue.offer(queue.poll());}}public int pop() {if (empty()) {throw new RuntimeException("Stack is empty");}return queue.poll();}public int top() {if (empty()) {throw new RuntimeException("Stack is empty");}return queue.peek();}public boolean empty() {return queue.isEmpty();}}

用栈实现队列：、

import java.util.ArrayDeque;
class MyQueueUseStack {public ArrayDeque<Integer> stack1;public ArrayDeque<Integer> stack2;public MyQueueUseStack() {stack1 = new  ArrayDeque<>();stack2 = new  ArrayDeque<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}}