【数据结构】堆栈和队列

前端之家收集整理的这篇文章主要介绍了【数据结构】堆栈和队列前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

堆栈又叫栈(堆栈和堆是两种不同的数据结构),和队列是两种极为常见的数据结构。这两种数据结构多少有点相对立的意思,一个是先进后出,一个是先进先出。概念上虽然很简单,很好理解,但其实其中有非常大的学问。在高并发系统的请求处理,操作系统消息机制中这两种数据结构有极大的应用,是两种应用很广的数据结构。

堆栈:



队列:


堆栈

堆栈的有进栈和出栈两种基本操作。进栈过程是数据由栈顶推入栈,由栈底开始逐一放置直到数据装满整个栈。出栈过程是数据由处于最上层的数据推出栈,直到栈底数据被推出,后进栈的数据在出栈过程中优先。堆栈的实现可以基于数组,链表等形式。堆栈对象中一般保存有栈顶对象引用,栈的深度和进栈出栈成员函数。如下给出一个基本堆栈的JAVA代码,基于数组的实现。

public class Stack {
	private int capacity = 10;
	private int[] stackArray = new int[capacity];
	private int top;
	
	public boolean push(int value){
		if(top == stackArray.length) return false;
		stackArray[top++] = value;
		return true;
	}
	
	public int pop() throws NoSuchElementException{
		if(top == 0) throw new NoSuchElementException();
		return stackArray[--top];
	}
	
	public int getTop() throws NoSuchElementException{
		if(top == 0) throw new NoSuchElementException();
		return stackArray[top - 1];
	}
}
在java.util容器库中提供的Stack是基于Vector容器实现的队列,所以其容量上限为内存上限,所以存储容量很大。

队列

其实队列的概念也很简单,所谓先进先出。数据从尾部进入,从头部推出。队列对象中一般保存有头部引用和尾部两个引用。这里给出一个基于数组实现的队列JAVA代码

public class Queue {
	int capacity = 10;
	int[] queueArray = new int[capacity];
	int top = 0;
	
	public boolean push(int value){
		if(top == queueArray.length) return false;
		queueArray[top++] = value;
		return true;
	}
	
	public int pop() throws NoSuchElementException{
		if(top == 0) throw new NoSuchElementException();
		int value = queueArray[0];
		int i = 0; 
		int j = i + 1;
		while(j < top){
			queueArray[i] = queueArray[j];
			i++;
			j++;
		}
		top--;
		return value;
	}
	
	public int getFirst() throws NoSuchElementException{
		if(top == 0) throw new NoSuchElementException();
		return queueArray[0];
	}
	
	public int getLast() throws NoSuchElementException{
		if(top == 0) throw new NoSuchElementException();
		return queueArray[top - 1];
	}
}


队列常常也有首尾相连的情况,称为循环队列(如下图)。


循环队列需要注意头指针和位置的操作,明确当前尾指针是否越界等。这里给出一个循环队列的实现。

class QueueNode{
	int value;
	QueueNode prevIoUs;
	QueueNode next;
	
	public QueueNode(QueueNode pre){
		this.prevIoUs = pre;
	}
}

public class CircleQueue {
	int capacity = 10;
	QueueNode head = null;
	QueueNode tail = null;
	
	public CircleQueue(){
		QueueNode cur = tail = head = new QueueNode(null);
		for(int i = 0; i < capacity; i++){
			cur.next = new QueueNode(cur);
			cur = cur.next;
		}
		cur.next = head;
		head.prevIoUs = cur;
	}
	
	public void push(int value){
		if(tail.next == head) throw new IndexOutOfBoundsException();
		tail.next.value = value;
		tail = tail.next;
	}
	
	public int pop() throws NoSuchElementException{
		if(tail == head) throw new NoSuchElementException();
		int value = tail.value;
		tail = tail.prevIoUs;
		return value;
	}
}

建议大家可以看一下java.util.Stack和java.util.Queue的源代码,可以帮助了解这两种数据结构的实现和使用。参考博文《【源代码】java.util.Stack & Queue》


面试常见问题

1.堆栈和队列的异同

相同点:首先堆栈和队列都可以使用链表或者数组实现。

不同点:首先是对象进出操作的不同,堆栈是先进后出,队列是先进先出。


2.涉及一种堆栈包含一个获取最大值的成员方法getMaximum(),要求时间复杂度为O(1)。

这里只需要在堆栈对象中加入另外一个栈stack_max,用来记录当前最大数值。假设新入栈元素n的值大于stack_max[n-1]的最大值,则stack_max[n] = n,否则stack_max[n] =stack_max[n - 1]。出栈时将stack_max的栈顶元素同时推出即可。这里提供改进后的JAVA代码


这里还有另外一个升级版问题,如果把堆栈改成队列,如何设计一个getmaximum(),让操作的时间复杂度越小越好。


3.使用堆栈来实现一个队列。

首先明确差异,堆栈是先进后出,需要用它来实现一个先进先出的结构,可以考虑使用两个堆栈。此时入栈操作与之前相同,只是出栈操作需要对原堆栈推入另一个堆栈,这样栈底对象就成为了栈顶对象,然后做一个出栈操作就可以推出栈顶对象,最后将剩下的对象再推回原堆栈即可(如下图)。

猜你在找的数据结构相关文章