（一）
栈，后进先出，只允许访问一个数据项：即最后插入的数据项。栈操作：
push入栈:第一步指针上移一个单位，第二步将数据插入到这个存储单元；
pop出栈：第一步移除指针指向的数据项，第二步指针下移一个单位，指向新的栈顶元素；
peek查看：不操作元素，只是查看栈顶元素的值；
结果：
上面的实现是用数组实现的，有个最大缺点是一旦数组创建，大小不可变。下面介绍另一种存储结构-链表。
首先，在链表中，每个数据项都包含在“链结点”中，这个链结点包括存储的数据本身和一个对下一个链结点引用的字段，链表本身有一个字段指向对第一个链结点的引用。用图形标识大致是这样子的：（其实first也是一个链结点）
链结点类：
package stack;
//链结点
public class Link {
public int data;
public Link next;
Link(int data){
this.data = data;
next = null;
}
public void show(){
System.out.print(" data:"+this.data);
}
}
单链表类：
package stack;
//单链表
public class LinkedList {
private Link first;
//构造函数
LinkedList(){
this.first = null;
}
public Link getFirst() {
return first;
}
//在前端插入
public void insertFirst(int data){
Link newLink = new Link(data);
newLink.next = first;
first = newLink;
}
//在前段删除
public void deleteFirst(){
if(!this.isEmpty()){
Link deleteLink = first;
first = deleteLink.next;
//或者 first = first.next;
}
}
//判断是否为空
public boolean isEmpty(){
return first == null;
}
//遍历
public void showLinkedList(){
Link current = first;
while(current != null){
current.show();
current = current.next;
}
System.out.println();
}
}
栈类：
package stack;
public class Stack {
private LinkedList linkedList;
//默认构造方法
public Stack(){
linkedList = new LinkedList();
}
//进栈
public void push(int newNum){
linkedList.insertFirst(newNum);
}
//出栈
public void pop(){
linkedList.deleteFirst();
}
//查看
public int peek(){
return linkedList.getFirst().data;
}
//遍历栈
public void showStack() {
linkedList.showLinkedList();
}
}
测试类：
package stack;
public class Test {
public static void main(String[] args) {
Stack stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(5);
stack.showStack();
stack.pop();
stack.showStack();
}
}
结果：
这里着重说明一下，单链表的前端插入，由于我学过c++,指针与引用作用虽然差不多，但是总用法与直观感觉不一样。
插入之前
此时 first = oldLink
插入之后
此时newLink.nest = oldLink, first = newLink
ps：画的有点粗糙！
（二）
以下主要来源于java数据结构和算法。
队列用到了双端链表， 双端链表与单链表类似，但是它新增了一个特性：即对最后一个链结点的引用。
链结点类：
//链结点
public class Link {
public int data;
public Link next;
Link(int data){
this.data = data;
next = null;
}
public void show(){
System.out.print(" data:"+this.data);
}
}
双端链表类：
//双端链表
public class FirstAndLastLinkedList {
private Link first;
private Link last;
//构造器
FirstAndLastLinkedList(){
this.first = null;
this.last = null;
}
//判断为空
public boolean isEmpty(){
return this.first == null;
}
//在前段插入
public void insertFirst(int data){
Link newLink = new Link(data);
if(isEmpty()){
first = newLink;
last = newLink;
}else{
newLink.next = first;
first = newLink;
}
}
//在后端插入
public void insertLast(int data){
Link newLink = new Link(data);
if(isEmpty()){
first = newLink;
last = newLink;
}
last.next = newLink;
last = newLink;
}
//在前段删除
public int deleteFirst(){
if(isEmpty()){
return -1;
}else{
int data = first.data;
first = first.next;
if(first == null)
last = null;
return data;
}
}
//遍历输出
public void show(){
System.out.print("FirstAndLastLinkedList: ");
Link current = first;
while(current != null){
System.out.print(current.data + " ");
current = current.next;
}
System.out.println("");
}
}
队列类：
//队列，双端列表实现
public class Queue {
private FirstAndLastLinkedList list;
//构造函数
Queue(){
list = new FirstAndLastLinkedList();
}
//进队列
public void insert(int data){
this.list.insertLast(data);
}
//出队列
public int remove(){
return this.list.deleteFirst();
}
//遍历队列
public void show(){
this.list.show();
}
}
测试类：
public class Test {
public static void main(String[] args) {
Queue queue = new Queue();
queue.insert(1);
queue.insert(2);
queue.insert(3);
queue.show();
queue.remove();
queue.remove();
queue.show();
}
}
结果：
