栈、队列、链表

简介: 栈 特性: LIFO public class StackApp { public static void main(String[] args) { Stack stack = new Stack(10); stack.push(10); stack.push(20); stack.push(40); stack.push(80); stack.

特性: LIFO

public class StackApp {

	public static void main(String[] args) {
		Stack stack = new Stack(10);
		
		stack.push(10);
		stack.push(20);
		stack.push(40);
		stack.push(80);
		stack.push(100);
		
		while (!stack.isEmpty()){
			System.out.println(stack.pop()+" ");
		}
	}
}

class Stack{
	private int maxSize;
	private long[] stackArray;
	private int top;
	
	public Stack(int size){
		stackArray = new long[size];
		maxSize = size;
		top = -1;
	}
	
	public void push(long value){
		stackArray[++top] = value;
	}
	
	public long pop(){
		return stackArray[top--];
	}
	
	public boolean isEmpty(){
		return top == -1;
	}
	
	public boolean isFull(){
		return top == maxSize-1;
	}
	
}


应用场景:

1. 程序运行时的栈空间,用来顺序存储局部变量和参数,每当函数被调用时,局部变量和方法参数会被“pushed into” stack,当方法returns,these locals and parameters are "popped".

2. Expression evaluation and syntax parsing

参考: http://en.wikipedia.org/wiki/Stack_(abstract_data_type)


队列

特点:FIFO

public class QueueApp {

	public static void main(String[] args) {
		Queue queue = new Queue(3);
		queue.insert(43);
		queue.insert(24);
		
		queue.remove();
		
		queue.insert(36);
		queue.insert(48);
		queue.insert(78);
	
		while(!queue.isEmpty()){
			System.out.println(queue.remove());
		}
	}
}

//循环队列
class Queue {
	private int head;
	private int rear;
	private long[] queueArray;
	private int maxSize;
	private int size;//当前队列size
	
	public Queue(int size){
		queueArray = new long[size];
		maxSize = size;
		head = 0;
		rear = 0;
		this.size = 0;
	}
	
	public void insert(long value){
		if (isFull()){
			System.out.println("Queue is already full");
			return;
		}
		queueArray[rear++] = value;
		if (rear == maxSize){
			rear = 0;
		}
		size++;
	}
	
	public long remove(){
		long temp = queueArray[head++];
		if (head == maxSize){
			head = 0;
		}
		size--;
		return temp;
	}
	
	
	public boolean isFull(){
		return size == maxSize;
	}
	
	public boolean isEmpty(){
		return size == 0;
	}
	
	public int size(){
		return size;
	}
}

参考: http://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29


链表

特点:插入、删除需要O(1),查询需要O(N)

基于Java的双向链表:
public class LinkedListApp {

	public static void main(String[] args) {
		DoubleLinkedList<String> list = new DoubleLinkedList<String>();
		list.add("one");
		list.add("two");
		list.add("three");
		
		list.removeFirst();
		
		list.display();
	}

}


class DoubleLinkedList<E>{
	private int size = 0;
	private Entry<E> header = new Entry<E>(null, null, null);
	
	public DoubleLinkedList(){
		header.next = header.previous = header;
	}
	
	public void add(E element){
		addBefore(element, header);
	}
	
	private void addBefore(E element, Entry<E> entry){
		Entry<E> newEntry = new Entry<E>(element, entry, entry.previous);
		newEntry.next.previous = newEntry;
		newEntry.previous.next = newEntry;	
		size++;
	}
	
	public E removeFirst(){
		return remove(header.next);
	}
	
	public E removeLast(){
		return remove(header.previous);
	}
	
	public E remove(Entry<E> e){
		if (e.next == header) {
			throw new RuntimeException("List is empty");
		}
		
		e.previous.next = e.next ;
		e.next.previous = e.previous;
		
		e.next = e.previous = null;
		e.element = null;
		
		size--;
		
		return e.element;
	}
	
	public void display(){
		Entry<E> e = header.next;
		while (e.element != null){
			System.out.println(e.element);
			e = e.next;
		}
	}
	
	private static class Entry<E> {
		private E element;
		private Entry<E> next;
		private Entry<E> previous;
		
		private Entry(E element, Entry<E> next, Entry<E> previous){
			this.element = element;
			this.next = next;
			this.previous = previous;
		}	
	}	
}


目录
相关文章
|
4月前
|
数据安全/隐私保护
第2章 栈、队列、链表
第2章 栈、队列、链表
|
5月前
|
算法 测试技术
【数据结构与算法 | 基础篇】单向循环链表实现队列
【数据结构与算法 | 基础篇】单向循环链表实现队列
|
4月前
栈和链表的区分
栈和链表的区分
19 0
|
5月前
|
存储
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
32 1
|
5月前
|
存储 调度 C语言
链表,栈,队列的区别及其应用
链表,栈,队列的区别及其应用
|
5月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
31 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
45 1