数据结构之栈和队列

栈 Stack

• 栈是一种后进先出的数据结构
• Last In First Out(LIFO)

栈的实现

• void push(E) O（1）
• E pop() O（1）
• E peek() O（1）
• int getSize() O（1）
• boolean isEmpty() O（1）

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

public class ArrayStack<E> implements Stack<E>
{
	Array<E> array;
	public ArrayStack(int capacity)
	{
		array = new Array<>(capacity);
	}
	public ArrayStack()
	{
		array = new Array<>();
	}
	@Override
	public int getSize()
	{
		return array.getSize();
	}
	@Override
	public boolean isEmpty()
	{
		return array.isEmpty();
	}
	public int getCapacity()
	{
		return array.getCapacity();
	}
	@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 String toString()
	{
		StringBuilder res = new StringBuilder();
		res.append("Stack: ");
		res.append('[');
		for(int i=0;i<array.getSize();i++)
		{
			res.append(array.get(i));
			if(i!=array.size()-1)
				res.append(",");
		}
		res.append("] top");
		return res.toString();
	}
}

栈的应用（20.Valid Parentheses leecode）

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

思路：利用栈的后进先出特性，如果全是左括号，压入栈中，和外面右括号进行匹配。

import java.util.Stack;
class Solution
{
    public boolean isValid(String s)
    {
        Stack<Character> stack = new Stack<>();//创建栈
        for(int i=0;i<s.length();i++)//建立循环
        {
            char c = s.charAt(i);	//将下标为i的赋值到字符c
            if(c == '(' || c =='[' || c =='{')//判断，如果c是（ [ {，则push进栈
            {
                stack.push(c);
            }
            else//否则，这时c不是( [ {
            {
                if(stack.isEmpty())//如果为null，返回false
                    return false;

                char topChar = stack.pop();//另栈顶元素赋值给topChar
                if(c == ')'&&topChar != '(')//如果c是),栈顶不是(,不匹配，返回false
                    return false;
                if(c == ']'&&topChar != '[')//如果c是],栈顶不是[,不匹配，返回false
                    return false;
                if(c == '}'&&topChar != '{')//如果c是},栈顶不是{,不匹配，返回false
                    return false;
            }
        }
        //如果栈里面的元素没有可匹配，只有isEmpty为true时匹配成功
        return stack.isEmpty();
    }
}

队列 Queue

• 队列也是一种线性结构
• 相比数组，队列对应的操作是数组的子集
• 只能从一段（队尾）添加元素，只能从另一端（对首）取出元素
• 队列是一种先进先出的数据结构
• First In First Out(FIFO)

队列的实现

• void enqueue(E) O(1)
• E dequeue() O(n)
• E getFront() O(1)
• int getSize() O(1)
• boolean isEmpty() O(1)

public interface Queue<E>
{
	int getSize();
	boolean isEmpty();
	void enqueue(E e);
	E dequeue();
	E getFront();
}

public class ArrayQueue<E> implements Queue<E>
{
	private Array<E> array;
	public ArrayQueue(int capacity)
	{
		array = new Array<>(capacity);	
	}
	public ArrayQueue()
	{
		array = new Array<>();
	}
	@Override
	public int getSize()
	{
		return array.getSize();
	}
	@Override
	public boolean isEmpty()
	{
		return array.isEmpty();
	}
	public int getCapacity()
	{
		return array.getCapacity();
	}
	@Override
	public void enqueue(E e)
	{
		array.addLast(e);
	}
	@Override
	public void dequeue()
	{
		array.removeFirst();
	}
	@Override
	public E getFront()
	{
		return array.getFirst();
	}
	@Override
	public String toString()
	{
		StringBuilder res = new StringBuilder();
		res.append("Queue: ");
		res.append('front [');
		for(int i=0; i<arr.getSize();i++)
		{
			res.append(array.get(i));
			if(i != array.getSize() -1)
				res.append(",");
		}
		res.append("] tail");
		return res.toString();
	}
}

循环队列的实现

public  class LoopQueue<E> implements Queue<E>
{
	private E[] data;
	private int front,detail;
	private int size;
	
	public LoopQueue(int capacity)
	{
		data = new Object[capacity + 1];
		front = 0;
		tail = 0;
		size = 0;
	}
	public LoopQueue()
	{
		this(10);
	}
	public int getCapacity()
	{
		return data.length-1;
	}
	@Override
	public boolean isEmpty()
	{
		return front == tail;
	}
	@Override
	public int getSize()
	{
		return size;
	}
	@Override
	public void enqueue(E e)
	{
		if((tail + 1) % data.length == front)
		resize(getCapacity() * 2);
		data[tail]=e;
		tail=(tail+1)%data.length;
		size++;
	}
	
	@Override
	public E dequeue()
	{
		if(isEmpty)
		{
			throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
		}
		E ret = data[front];
		data[front] = null;
		front=(front+1)%data.length;
		size--;
		if(size == getCapacity()/4&&getCapacity()/2 != 0)
		{
			resize(getCapacity()/2);
		}
		return ret;
	}
	
	@Override
	public E getFront()
	{
		if(isEmpty())
        	throw new IllegalArgumentException("Queue is empty.")
        	return data[front];
	} 
	@Override
	public String toString()
	{
		StringBuilder res = new StringBuilder();
		res.append(String.format("Queue: size=%d,capacity=%d\n",size,getCapacity()));
		res.append("front [");
		for(int i=front;i!=tail;i=(i+1)%data.length)
		{
			res.append(data[i]);
			if(i+1%data.length != tail)
			res.append(",");
		}
		res.append("] tail");
		return res.toString();
	}
	
	private void resize(int newCapacity)
	{
		E[] newData = (E[])new Object[newCapacity + 1];
		for(int i=0;i<size;i++)
		{
			newData[i]=data[(i+front)%data.length];
		}
		data=newData;
		front=0;
		tail=size;
	}
}