数据结构（三）栈和队列
栈
栈是一种线性结构，相比数组，栈对应的操作是数组的子集，栈只能从一端添加元素，也只能从一端取出元素，这一端称为栈顶。栈是一种后进先出的数据结构，从下图我们可以看出，先入栈的元素在栈底，得等到它之后的所有元素都出去，它才能出栈，反而最后入栈的元素可以先出栈。
栈的应用：
-
撤销操作
-
程序调用的系统栈
栈的实现：
栈的实现很简单，我们需要实现5个操作即可，void push(E)-入栈操作、E pop()-出栈操作、E peek()-查看栈顶元素、int getSize()-查看栈里一共有多少元素、boolean isEmpty()-判断栈是否为空; 下面栈代码的实现用了上篇文章中写的数组，为了获取栈顶元素，我们需要在上篇数组的代码中添加两个方法，获取数组最后一个元素（即栈顶）和第一个元素（栈底），具体方法如下：
//获取数组最后一个元素
public E getLast(){
return get(size -1);
}
//获取数组第一个元素
public E getFirst(){
return get(0);
}
我们先来一个栈的接口，最后实现栈：
Stack.java：
package com.wjy329;
/**
* @Author wjy329
* @Time 2018/10/19:27 PM
* @description
*/
public interface Stack<E> {
//获取栈中元素个数
int getSize();
//判断栈是否为空
boolean isEmpty();
//入栈
void push(E e);
//出栈
E pop();
//查看栈顶元素
E peek();
}
ArrayStack.java:
package com.wjy329;
/**
* @Author wjy329
* @Time 2018/10/19:30 PM
* @description
*/
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();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.delLast();
}
@Override
public E peek() {
return array.getLast();
}
public int getCapacity(){
return array.getCapacity();
}
@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.getSize()-1){
res.append(",");
}
}
res.append("] top");
return res.toString();
}
}
文章一开始就说了两个栈的应用，在我们面试中，经常用到的栈的应有就有一个是括号的匹配，下面给出代码：
package com.wjy329;
import java.util.Stack;
/**
* @Author wjy329
* @Time 2018/10/110:07 PM
* @description
*/
public 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);
if(c == '(' || c == '[' || c == '{'){
stack.push(c);
}else {
if(stack.isEmpty()){
return false;
}
char topChar = stack.pop();
if(c == ')' && topChar != '('){
return false;
}
if(c == ']' && topChar != '['){
return false;
}
if(c == '}' && topChar != '{'){
return false;
}
}
}
return stack.isEmpty();
}
}
括号匹配的思路也很简单：就是将给定的字符串依次取出如果是左括号则入栈，右括号则对括号进行匹配。
队列
队列也是一种线性结构，相比数组，栈对应的操作是数组的子集，只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。队列是一种先进先出的数据结构。
队列的实现：
和栈的实现类似，同样我们需要5个方法，void enqueue(E)-入队、E dequeue()-出队、E getFront()-查看队首元素、int getSize()-查看队列中的元素个数、boolean isEmpty()-判断队列是否为空；
package com.wjy329;
/**
* @Author wjy329
* @Time 2018/10/110:44 PM
* @description
*/
public class ArrayQueue<E> implements Queue<E>{
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();
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue() {
return array.delFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue:");
res.append("[");
for(int i=0;i < array.getSize();i++){
res.append(array.get(i));
if(i != array.getSize()-1){
res.append(",");
}
}
res.append("] tail");
return res.toString();
}
}
循环队列：
上述数组队列当进行删除队首元素时，其后面的元素需要往前移，时间复杂度为O(n),循环队列不需要往前移动，当后面空间满时，可以往前在寻找空间，循环队列可以通过(tail+1)%c == front 来判断队列是否已满。tail-队尾、c-队列容量、front-队首；
package com.wjy329;
/**
* @Author wjy329
* @Time 2018/10/29:12 AM
* @description
*/
public class LoopQueue<E> implements Queue<E>{
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(10);
}
public int getCapacity(){
return data.length - 1;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return front == tail;
}
@Override
public void enqueue(E e) {
if((tail + 1) % data.length == front){
resize(getCapacity() * 2);
}
data[tail] = e;
tail = (tail+1)%data.length;
size++;
}
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;
}
@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("队列为空，不能出队");
}
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("队列为空");
}
return data[front];
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue:");
res.append("[");
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();
}
}
[…] 数据结构（三）栈和队列 […]