|
目录
1.栈
1.1栈的概念
2.栈的实现
2.1顺序表实现栈
2.2链表实现栈
3.队列
3.1队列的概念
3.2队列的实现
1.栈
1.1栈的概念
? ? ? ? 栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守先进后出。
2.栈的实现
2.1顺序表实现栈
顺序表底层是个数组
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack(){
this.elem = new int[5];
}
/*
入栈
*/
public void push(int val){
if(isFull()){
//空间如果满了，要扩容，默认2倍扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize] = val;
usedSize++;
}
/*
出栈，后入先出
*/
public int pop(){
if(isEmpty()){
throw new UnsupportedOperationException();
}
int oldval = this.elem[usedSize-1];
this.usedSize--;
return oldval;
}
/*
返回栈顶元素，但不删除
*/
public int peek(){
if(isEmpty()){
throw new UnsupportedOperationException();
}
int oldval = this.elem[usedSize-1];
return oldval;
}
public boolean isEmpty(){
return this.usedSize == 0;
}
public boolean isFull(){
return this.usedSize == this.elem.length;
}
}
2.2链表实现栈
? ? ? ? 如果用单链表来实现栈，入栈和出栈时间复杂度总有一个不是O(1)，因此我们采用双向链表来实现。即定义一个头部指针和尾部指针，利用头插法入栈，即删除头部节点，尾插法出栈，即删除尾部节点。
3.队列
3.1队列的概念
? ? ? ? ?只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 。
入队列：进行插入操作的一端称为队尾?
出队列：进行删除操作的一端称为队头
3.2队列的实现
我们这里用链表来实现队列，因为链表实现队列比顺序表实现更优，效率更高
class Node {
private int val;
private Node next;
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(int val){
this.val = val;
}
}
public class MyQueue {
private Node first;//队头指针
private Node last;//队尾指针
//入队
public void offer(int val){
//尾插法，需要判断是不是第一次插入
Node node = new Node(val);
if(this.first == null){
this.first = node;
this.last = node;
}else {
this.last.setNext(node);//相当于last.next = node;
this.last = node;
}
}
//出队
public int poll(){
//1.判断是否为空
if(isEmpty()){
throw new UnsupportedOperationException("队列为空！");
}
int ret = this.first.getVal();
this.first = this.first.getNext();//相当于this.first = this.first.next;
return ret;
}
//得到队头元素但不删除
public int peek(){
//不要移动first
if(isEmpty()){
throw new UnsupportedOperationException("队列为空！");
}
return this.first.getVal();
}
//判断队列是否为空
public boolean isEmpty(){
return this.first == null;
}
}
3.3循环队列
public class MyCircularQueue {
public int[] elem;
public int front;
public int rear;
public int len;
public MyCircularQueue(int k) {
this.elem = new int[k];
this.len = elem.length;
}
/*
入队
*/
public boolean enQueue(int val) {
if(isFull()){
throw new UnsupportedOperationException("队列满了");
}
rear = (rear + 1) % len;
this.elem[rear] = val;
return true;
}
/*
出队
*/
public boolean deQueue(){
if(isEmpty()){
throw new UnsupportedOperationException("队列为空");
}
front = (this.front + 1) % len;
return true;
}
/*
得到队头元素
*/
public int Front(){
if(isEmpty()){
return -1;
}
return elem[front];
}
/*
得到队尾元素
*/
public int rear(){
if(isEmpty()){
return -1;
}
int index = -1;
if(rear == 0){
index = len - 1;
}else {
index = (rear + 1) % len;
}
return elem[index];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull() {
//rear的下一个是front
if ((this.rear + 1) % len == this.front){
return true;
}
return false;
}
}
|