【数据结构】栈与对列

·队列也是一种线性结构
·相比数组，队列对应的操作是数组的子集
·只能从一端（队尾）添加元素，只能从另一端（队首）取出元素Interface Queue
 dequeue() getFront() getSize() isEmpty()

public class ArrarQueuesE> implements Queue
｛
private Array array;
public ArrayQueue(int capacity){
array = new Array>(capacity);
｝
public ArrayQueue(){
array= new Arrayo();
｝
@Override
public int getSize(){
return array.getSize();
｝
@override
public boolean isEmpty(){
return array.isEmpty();
｝
public int getCapacity(){
return array.getCapacity(:
｝
@override
public E dequeue( ){
return array.removeFirst();
｝
@Override
public E getFront(){
return array.getFirst();
｝
eoverride
public String toString(){
StringBuilder res = new StringBuilder();
res. append('"');
res.append('[*);
for(int i=0; i < size ;i ++){
res.append(data[i]);
if(i!=size-1)
res. append(", ");
｝
res.append(']'）；
return res.toString();
｝
｝

    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueueo();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.print Ln (queue);
            if (i % .3 = 2) {
                queue.dequeue();
            }
        }
    }

删除操作

public class LoopQueue implements Queues {
private E[] data;
private int front, tail;
private int size;
public LoopQueue(int capacity){
data =(E[])new Object[capacity +1];
front=0;
tail =0;
size=0;
｝
public LoopQueue(){
this(capacity:10);
｝
public int getCapacity(){
return data.Length-1;
｝
@Override
public boolean isEmpty(){
return front==tail;
｝
｝

@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty.");
return data[front];
private void resize(int newCapacity){
E[] newData = (Ell)new Object [newCapacity + 1];
for(int 1=0;1 
 
 
栈是一种 后进先出（last in - first out， LIFO）的数据结构
 
栈内元素从顶端压入（push），从栈：LIFO（后进先出），自己实现一个栈，要求这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()这些基本的方法。顶端弹出（pop）。
 
入栈
 
public void push(T t) {
        if (t == null) {
            throw new NullPointerException("参数不能为空");
        }
        if (head == null) {
            head = new Node();
            head.t = t;
            head.next = null;
        } else {
            Node temp = head;
            head = new Node<>();
            head.t = t;
            head.next = temp;
        }
    }

 
返回栈顶元素
 
    public T peek() {
        T t = null;
        if (size > 0)
            t = (T) stack[size - 1];
        return t;
    }
 
出栈
 
    public T pop() {
        T t = peek();
        if (size > 0) {
            stack[size - 1] = null;
            size--;
        }
        return t;
    }

 
扩大容量
 
public void expandCapacity(int size) {
        int len = stack.length;
        if (size > len) {
            size = size * 3 / 2 + 1;//每次扩大50%
            stack = Arrays.copyOf(stack, size);
        }
    }
}

 
力扣例题
 
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 
有效字符串需满足：
 
左括号必须用相同类型的右括号闭合。
 左括号必须以正确的顺序闭合。
 
class Solution {
    public boolean isValid(String s) {
Stackstack=new Stack<>();
for(int i=0;i