时间戳

首页 > 技术文章 > 数据结构与算法(4)-栈,队列,优先级队列

数据结构与算法(4)-栈,队列,优先级队列

guan-li 2018-11-06 16:40 原文

1.栈

先进后出,头进头出.
一般基于数组实现.
出栈操作一般不删除数据,只是指针的移动.
入栈,入栈的时间复杂度都为O(1).

栈结构主要应用:
校验表达式语法是否正确,jvm中方法的执行调用等.

  • 代码:用数组模拟栈结构
public class StackDemo {
	private int maxSize;	//最大尺寸
	private long[] longArray;	//数组
	private int top;	//指针
	
	public StackDemo(int maxSize){
		this.maxSize = maxSize;
		this.longArray = new long[maxSize];
		this.top = -1;
	}
	
	//入栈操作
	public void push(long data){
		if(top > this.maxSize-1){	//栈已满
			System.out.println("栈已满,无法进行入栈操作!!!");
		}else{
			longArray[++top] = data;
			System.out.println(data+"被压入栈顶!!!");
		}
	}
	
	//出栈操作
	public long pop(){
		if(this.isEmpty()){
			try {
				throw new Exception();
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		//出栈只是移动指针的位置,并非删除
		return longArray[top--];
	}
	
	//读取栈顶
	public long peek(){
		return longArray[top];
	}
	
	//是否为空
	public boolean isEmpty(){
		return -1==top;
	}
	
	//是否满栈
	public boolean isFull(){
		return (maxSize-1)==top;
	}
	
	public static void main(String[] args) {
		StackDemo stack = new StackDemo(10);
		stack.push(10);
		stack.push(10);
		stack.push(20);
		stack.push(30);
		
		while(!stack.isEmpty()){
			System.out.println(stack.pop());
		}
	}
}

输出:

10被压入栈顶!!!
10被压入栈顶!!!
20被压入栈顶!!!
30被压入栈顶!!!
30
20
10
10
  • 代码:校验文本中的左右括号是否匹配
public class CheckCharStack {
	private int maxSize;
	private char[] charArray;
	private int top;

	public CheckCharStack(int maxSize) {
		this.maxSize = maxSize;
		this.charArray = new char[maxSize];
		this.top = -1;
	}

	// 判断满栈
	public boolean isFull() {
		return (maxSize - 1) == top;
	}

	// 判断空栈
	public boolean isEmpty() {
		return -1 == top;
	}

	// 入栈操作
	public void push(char c) {
		if (!this.isFull()) {
			charArray[++top] = c;
			System.out.println(c+" 入栈!!!");
		} else {
			System.out.println("栈已满!!!");
		}
	}

	// 出栈操作
	public char pop() throws Exception {
		if (this.isEmpty()) {
			throw new Exception();
		} else {
			System.out.println(charArray[top]+" 出栈!!!");
			return charArray[top--];
		}
	}

	// 获取但不出栈
	public char peek() throws Exception {
		if (this.isEmpty()) {
			throw new Exception();
		} else {
			return charArray[top];
		}
	}
}

public class CharChecker {
	private String input;

	public CharChecker(String input) {
		this.input = input;
	}

	// 字符串括号语法校验
	public void check() {
		int maxSize = this.input.length();
		CheckCharStack stack = new CheckCharStack(maxSize);

		for (int i = 0; i < maxSize; i++) {
			char c = input.charAt(i);
			switch (c) {
			// 如果为左括号,入栈
			case '(':
			case '[':
			case '{':
				stack.push(c);
				break;
			// 如果为右括号,出栈一个用来比较
			case ')':
			case ']':
			case '}':
				char ch = 0;
				System.out.println("当前右括号为 "+c);
				if (!stack.isEmpty()) {
					try {
						ch = stack.pop();
					} catch (Exception e) {
						e.printStackTrace();
					}
					// 如果取出的左括号与当前的右括号不对应,则报错
					if (('(' == ch && ')' != c) || ('[' == ch && ']' != c) || ('{' == ch && '}' != c)) {
						System.out.println("Error:" + c + " at " + i + "!!!");
						return;
					}
				} else {
					// 如果栈已空,则报错
					System.out.println("Error:" + c + " at " + i + "!!!");
					return;
				}
				break;
			default:
				break;
			}
		}
		
	}
	
	//运行
	public static void main(String[] args) {
		new CharChecker("a{b[c])d}").check();
		new CharChecker("a{b[c]d}").check();
	}
}

输出:

{ 入栈!!!
[ 入栈!!!
当前右括号为 ]
[ 出栈!!!
当前右括号为 )
{ 出栈!!!
Error:) at 6!!!
{ 入栈!!!
[ 入栈!!!
当前右括号为 ]
[ 出栈!!!
当前右括号为 }
{ 出栈!!!

2.队列

后进后出.
数组和链表常用来实现队列.
插入和取出时间复杂度为O(1).

以数组模拟队列为例,插入时,先移动再赋值,尾部向右移动,当尾部位置为maxSize-1时,需要将尾部位置赋值-1,而下一次则在0的位置插入.
删除时,头部向右移动,先取值再移动,如果移动后的值为maxSize,需要将头部赋值为0,下一次取0的位置的值.
同时需要记录当前元素的数目.(其实队列可以理解为一个环形结构)

  • 代码:用数组模拟队列结构
public class QueueDemo {
	private int maxSize;	//队列长度
	private int curNum;	//当前元素个数
	private int front;	//队列头部
	private int rear;	//队列尾部
	private long[] queue;
	
	public QueueDemo(int maxSize){
		this.maxSize = maxSize;
		this.curNum = 0;
		//取出时,头部右移,先取后移,头部初始置于0
		this.front = 0;
		//插入时,尾部右移,先移后插,尾部置于-1
		this.rear = -1;
		this.queue = new long[maxSize];
	}
	
	//插入
	public void insert(long data){
		if(this.isFull()){
			System.out.println("队列已满!!!");
			return;
		}
		//如果尾部已经在最后一个,将尾部置为-1
		if(this.rear == maxSize-1){
			this.rear = -1;
		}
		queue[++rear] = data;
		this.curNum++;
		System.out.println("数据"+data+"被插入队列,位置为"+this.rear);
	}
	
	//取出(删除)
	public long remove() throws Exception{
		//如果队列为空,抛出异常
		if(this.isEmpty()){
			throw new Exception("队列为空!!!");
		}
		long result = queue[front++];
		this.curNum--;
		System.out.println("数据"+result+"被取出,从位置"+(this.front-1));
		if(maxSize == front){
			front = 0;
		}
		return result;
	}
	
	//只获取不删除
	public long peek(){
		return queue[front];
	}
	
	//判断是否为空
	public boolean isEmpty(){
		return 0 == curNum;
	}
	
	//判断是否已满
	public boolean isFull(){
		return curNum == maxSize;
	}
	
	//获取当前元素个数
	public int size(){
		return curNum;
	}
	
	public static void main(String[] args) throws Exception {
		QueueDemo queue = new QueueDemo(5);
		queue.insert(10);
		queue.insert(20);
		queue.insert(30);
		queue.insert(40);
		
		queue.remove();
		queue.remove();
		queue.remove();
		
		queue.insert(10);
		queue.insert(20);
		queue.insert(30);
		queue.insert(40);
		queue.insert(50);
		
		queue.remove();
		queue.remove();
		queue.remove();
		queue.remove();
		queue.remove();
		queue.remove();
	}
}

输出:

数据10被插入队列,位置为0
数据20被插入队列,位置为1
数据30被插入队列,位置为2
数据40被插入队列,位置为3
数据10被取出,从位置0
数据20被取出,从位置1
数据30被取出,从位置2
数据10被插入队列,位置为4
数据20被插入队列,位置为0
数据30被插入队列,位置为1
数据40被插入队列,位置为2
队列已满!!!
数据40被取出,从位置3
数据10被取出,从位置4
数据20被取出,从位置0
数据30被取出,从位置1
数据40被取出,从位置2
Exception in thread "main" java.lang.Exception: 队列为空!!!
	at queue.QueueDemo.remove(QueueDemo.java:39)
	at queue.QueueDemo.main(QueueDemo.java:92)
  • 双端队列简介

一种多用途的数据机构,左右两边都可以进行插入和取出操作,需要定义以下四种方法.
insertLeft()
insertRight()
removeLeft()
removeRight()

双端队列可以通过禁用部分功能,同时做栈和队列使用.
禁用insertLeft(),removeLeft()可以作栈使用.
禁用insertLeft(),removeRight()可以作一般队列使用.

3.优先级队列

插入队列的数据有优先级的高低,优先级高的将被先取出.通常使用堆来实现优先级队列,此处暂时用数组模拟.如果将数据的值作为优先级,值越大则越先被取出.
通常将值最小的固定数组角标的0的位置,后续插入的数将进行排序和移动,取出始终取值最大的.
优先级队列的时间复杂度:插入O(N),删除O(1).

  • 代码:数组模拟优先级队列
public class PriorityQueueDemo {
	private int curIndex;
	private long[] queueArray;
	private int maxSize;

	public PriorityQueueDemo(int maxSize) {
		this.maxSize = maxSize;
		this.queueArray = new long[maxSize];
		this.curIndex = -1;
	}

	// 插入,每次插入需要查找遍历应该插入的位置
	public void push(long data) {
		if (this.curIndex == this.maxSize - 1) {
			System.out.println("队列已满!!!");
			return;
		}
		System.out.println("元素" + data + "被插入!!!");
		if (this.curIndex == -1) {
			queueArray[++this.curIndex] = data;
		} else {
			// 从数组尾部开始比较,如果data<=queue[i],将queue[i]右移一位
			for (int i = this.curIndex; i >= 0; i--) {
				if (data <= queueArray[i]) {
					queueArray[i + 1] = queueArray[i];
					if(i == 0){
						queueArray[0] = data;
					}
				} else { // 如果data>queue[i],将data填入queue[i+1]
					queueArray[i + 1] = data;
					break;
				}
			}
			++this.curIndex;
		}
	}

	// 取出元素
	public long pop() throws Exception {
		if (curIndex == -1) {
			throw new Exception("队列为空!!!");
		} else {
			System.out.println("元素" + this.queueArray[this.curIndex] + "被取出");
			return this.queueArray[this.curIndex--];
		}
	}

	// 获取元素值
	public long peek() throws Exception {
		if (curIndex == -1) {
			throw new Exception("队列为空");
		} else {
			return this.queueArray[this.curIndex];
		}
	}

	// 是否已满
	public boolean isFull() {
		return (maxSize - 1) == this.curIndex;
	}

	// 是否为空
	public boolean isEmpty() {
		return -1 == this.curIndex;
	}

	public static void main(String[] args) throws Exception {
		PriorityQueueDemo queue = new PriorityQueueDemo(5);
		queue.push(20);
		queue.push(30);
		queue.push(10);
		queue.push(35);
		queue.push(5);

		while (!queue.isEmpty()) {
			queue.pop();
		}
	}
}

输出:

元素20被插入!!!
元素30被插入!!!
元素10被插入!!!
元素35被插入!!!
元素5被插入!!!
元素35被取出
元素30被取出
元素20被取出
元素10被取出
元素5被取出

推荐阅读