- 1.栈概念与使用
- 2.栈的实现
- 3.队列的概念与使用
- 4.队列的实现
========================================================================
1.栈概念与使用（1）栈的概念
- 栈：是一种特殊的线性表；只允许在一端进行插入删除操作；
- 栈顶、栈底：进行插入删除的一端称为栈顶；另一端成为栈底；
- 栈遵循后进先出的规则：LIFO(last in first out)；
- 压栈/入栈：向栈顶插入数据操作；
- 出栈：将栈顶元素删除的操作；
- Stack类是继承自Vector类，而不是使用Vector来实现Stack，这就产生了一个问题，Vector上可以使用的方法Stack类都可以使用，所以很容易破坏栈应有的规则，并且额外的操作对于使用Stack类的调用者来说是额外的负担。
- Vector由于是线程安全的，所以在单线程的时候效率会叫ArrayList更低。在Java 1.2 出现ArrayList之后基本上就使用起来代替Vector。在多线程中ArrayList可以使用Collectiuons.synchronized方法来保证多线程环境下的安全使用。
（2）栈方法的使用
// 标准库中栈的创建与常用方法的使用；
public static void main(String[] args) {
//使用多态的形式创建栈，方便之后的修改；
//List stack1=new Stack<>();
Stack stack=new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack);
System.out.println(stack.peek());
Integer ret1=stack.pop();
System.out.println(ret1);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.empty());
System.out.println(stack);
Integer ret=stack.peek(); //当栈为空时返回空，并会抛出空栈异常；
System.out.println(ret);
System.out.println(stack.empty());
}
2.栈的实现
栈的基本操作：入栈、出栈、返回栈顶元素、判断是否是空栈；
（1）使用顺序表实现栈：尾插-入栈；尾删-出栈；访问最后一个元素；（此处为实现泛型，只实现整型）
//使用数组（顺序表）实现栈；
public class MyStackA {
private Integer[] data=new Integer[100];
private int size=0;
//入栈
public void push(int v){
if(size==100){扩容}；
data[size]=v;
size++;
}
//出栈
public Integer pop(){
if (size==0){
return null;
}
return data[--size];
}
//返回栈顶元素
public Integer peek(){
if (size==0){
return null;
}
return data[size-1];
}
//empty判断栈是否为空
public boolean empty(){
return size==0;
}
@Override
public String toString() {
StringBuffer stringBuffer=new StringBuffer();
stringBuffer.append("[");
for (int i = 0; i < size; i++) {
stringBuffer.append(data[i]);
if (i
// 功能测试及运行结果：
（2）使用链表实现栈：头插-入栈；头删-出栈；-访问头节点元素-访问栈顶元素；
class Node{
public int val;
public Node next;
public Node(int val) {
this.val = val;
}
}
public class MyStackL {
private Node head;
//入栈操作
public void push(int v) {
Node newNode = new Node(v);
if (head==null){
head=newNode;
return;
}
newNode.next=head;
head=newNode;
}
//出栈操作
public Integer pop() {
if (head == null) {
return null;
}
int ret=head.val;
head=head.next;
return ret;
}
//访问栈顶元素
public Integer peek() {
if (head == null) {
return null;
}
return head.val;
}
//判断是否为空
public boolean empty() {
if (head == null) {
return true;
}
return false;
}
@Override
public String toString() {
StringBuffer stringBuffer = new StringBuffer();
stringBuffer.append("[");
for (Node cur = head; cur != null; cur = cur.next) {
stringBuffer.append(cur.val);
if (cur.next != null) {
stringBuffer.append("->");
}
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
3.队列的概念与使用
- 队列：是一种特殊的线性表；只允许一段插入数据元素，另一端删除数据元素；
- 队列遵循先进先出的原则；
- 入队列：进行插入操作的一端称为队尾（Tail/Rear）
- 出队列：进行删除操作的一端称为队头（Head/Front）
// Java中的队列是通过实现队列接口实现的；
- Java 标准库中队列的方法和操作：
// 使用Java标准库创建队列：
// 创建队列出错的原因是：在Java标准库中List和Queue都是实现自Collection 的接口，并列关系不是继承类的关系；从下图中可以看到linkedList 类是实现了Queue接口的实现类；故只能通过linkedList类创建队列实例；
public static void main(String[] args) {
Queue queue=new linkedList<>();
queue.offer("a");
queue.offer("b");
queue.offer("c");
queue.offer("d");
System.out.println(queue);
System.out.println(queue.poll());
System.out.println(queue);
System.out.println(queue.peek());
System.out.println(queue);
System.out.println(queue.element());
System.out.println(queue.remove());
System.out.println(queue);
}
4.队列的实现
（1）链表实现队列的基本操作：入队-尾插；出队-头删；访问队头元素-访问链表头元素；
//此处实现不支持泛型，只实现String 字符串型
public class MyQueueL {
static class Node{
private String val;
private Node next;
public Node(String val) {
this.val = val;
}
}
private Node head;
private Node tail;
//入队操作：
public boolean offer(String e){
Node newNode = new Node(e);
if (head == null) {
head=newNode;
tail=newNode;
return true;
}
tail.next=newNode;
tail=tail.next;
return true;
}
//出队操作
public String poll(){
if (head == null) {
return null;
}
String ret=head.val;
head=head.next;
return ret;
}
//访问队头元素：
public String peek(){
if (head == null) {
return null;
}
return head.val;
}
@Override
public String toString() {
StringBuilder stringBuffer = new StringBuilder();
stringBuffer.append("[");
for (Node cur = head; cur != null; cur = cur.next) {
stringBuffer.append(cur.val);
if (cur.next != null) {
stringBuffer.append("->");
}
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
（2）利用数组实现环形队列：入队-尾插；出队-头删；访问队头元素-访问下标为head的元素；
因为队列原则是先进先出；为了删除方便设置两个变量head、tail存储数组下标：
//环形队列-数组实现：
public class MyQueueA {
private String[] data = new String[3];
private int head=0;
private int tail=0;
private int size=0;
//入队
public boolean offer(String e) {
if (size == data.length) {
//需要扩容；
return false;
}
data[tail]=e;
if (tail==data.length-1){
tail=0;
}else{
tail++;
}
//tail=tail% data.length; 此处的效果同样是tail走到数组最后一个元素位置时，令其返回数组第一个元素位置；
size++;
return true;
}
//出栈
public String poll() {
if (size==0) {
return null;
}
String ret = data[head];
head++;
size--;
return ret;
}
//访问队头元素
public String peek() {
if (size ==0) {
return null;
}
return data[head];
}
@Override
public String toString() {
StringBuilder stringBuffer=new StringBuilder();
stringBuffer.append("[");
if (head");
}
}
}
if(size!=0&&head>=tail){
for (int i = head; i< data.length; i++) {
stringBuffer.append(data[i]);
if (i< data.length-1){
stringBuffer.append("->");
}
}
for (int j = 0; j < tail; j++) {
stringBuffer.append("->");
stringBuffer.append(data[j]);
}
}
stringBuffer.append("]");
return stringBuffer.toString();
}
}
