一.栈
?
自主实现：
public class MyStack {
public int[] elem;
public int usedSize;
public MyStack() {
this.elem = new int[10];
}
public boolean isFull() {
//数据个数 == 长度了
if(this.usedSize == this.elem.length) {
return true;
}
return false;
}
public void push(int item) {
if(isFull()) {
//扩容
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//存放到数组的最后位置
this.elem[this.usedSize] = item;
this.usedSize++;
}
public boolean empty() {
//数据个数 == 0的时候
return this.usedSize == 0;
}
public int pop() throws RuntimeException{
if(empty()) {
throw new RuntimeException("栈空了！");
}
int val = this.elem[this.usedSize-1];
this.usedSize--;
return val;
}
public int peek() {
if(empty()) {
throw new RuntimeException("栈空了！");
}
return this.elem[this.usedSize-1];
}
}?不可能的出栈顺序：
?中缀表达式转后缀表达式及计算机怎样用栈进行运算：
?
?用单链表实现栈：
?二.队列
?
?
自我实现：?
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
public class MyQueueLinked {
private Node front;
private Node rear;
private int usedSize;
/**
* 入队列
* @param val 值
*/
public void offer(int val) {
Node node = new Node(val);
if(this.front == null) {
this.front = node;
this.rear = node;
}else {
this.rear.next = node;
this.rear = node;
}
this.usedSize++;
}
/**
* 出队头元素
* @return
*/
public int poll() {
if(isEmpty()) {
throw new RuntimeException("队列为空！");
}
int val = this.front.data;
if(this.front.next == null) {
//只有1个节点
this.front = null;
this.rear = null;
}else {
this.front = this.front.next;
}
this.usedSize--;
return val;
}
/**
* 得到队头元素 但是不删除
*/
public int peek() {
if(isEmpty()) {
throw new RuntimeException("队列为空！");
}
return this.front.data;
}
public boolean isEmpty() {
return this.usedSize == 0;
}
public int size() {
return this.usedSize;
}
}?java集合类对应的队列是linkedlist
队列offer与add的区别？
三.用数组实现环形队列：
问题一：如何区分空和满
满：rear+1=front?
空：rear=front
问题二：如何后移或前移元素
1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
2.下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
代码：
public class MyCircularQueue {
private int[] elem;
private int usedSize;
private int front;
private int rear;
public MyCircularQueue(int k) {
this.elem = new int[k];
}
/**
* 入队
* @param value
* @return
*/
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
this.elem[this.rear] = value;
this.rear = (this.rear+1) % this.elem.length;
return true;
}
public boolean isFull() {
if( (this.rear+1) % this.elem.length == this.front) {
return true;
}
return false;
}
/**
* 出队
* @return
*/
public boolean deQueue() {
if(isEmpty()) {
return false;
}
this.front = (this.front+1) % this.elem.length;
return true;
}
public boolean isEmpty() {
if(this.front == this.rear){
return true;
}
return false;
}
/**
* 得到队头元素 相当于 peek()
* @return
*/
public int Front() {
if(isEmpty()) {
return -1;
}
int val = this.elem[this.front];
//this.front = (this.front+1) % this.elem.length; 不能删除的
return val;
}
/**
* 得到队尾元素
* @return
*/
public int Rear() {
if(isEmpty()) {
return -1;
}
if(this.rear == 0) {
return this.elem[this.elem.length-1];
}
return this.elem[this.rear-1];
}
}四.双端队列
既能从队头入从队头出 也可以从队尾出队尾入
五.练习
括号匹配问题：
public boolean isValid(String s) {
if(s == null) {
return false;
}
if(s.length() == 0) {
return true;
}
Stack<Character> stack = new Stack<>();
for(int i = 0;i < s.length();i++) {
char ch = s.charAt(i);
if(ch == '{' || ch == '(' || ch == '[') {
stack.push(ch);
}else{
//遇到右括号了
if(stack.empty()) {
System.out.println("右括号多！");
return false;
}
//栈不为空：获取栈顶元素，查看是否匹配
char tmp = stack.peek();//[
if(tmp == '{' && ch == '}' || tmp == '[' && ch == ']' || tmp == '(' && ch == ')' ) {
stack.pop();
}else{
System.out.println("左右括号顺序不匹配！");
return false;
}
}
}
if(!stack.empty()) {
System.out.println("左括号多！");
return false;
}
return true;
}
public static void main(String[] args) {
}用队列实现栈?
class MyStack {
private Queue<Integer> qu1 = new LinkedList<>();
private Queue<Integer> qu2 = new LinkedList<>();
public MyStack() {
}
/**
入栈
*/
public void push(int x) {
if(!qu1.isEmpty()){
qu1.offer(x);
}else if(!qu2.isEmpty()){
qu2.offer(x);
}else{
qu1.offer(x);
}
}
/**
出栈
*/
public int pop() {
if(empty()) {
return -1;
}
int e = -1;
if(!qu1.isEmpty()) {
int size = qu1.size();
for(int i = 0;i < size-1;i++){
e = qu1.poll();
qu2.offer(e);
}
e = qu1.poll();
}else{
int size = qu2.size();
for(int i = 0;i < size-1;i++){
e = qu2.poll();
qu1.offer(e);
}
e = qu2.poll();
}
return e;
}
/**
得到栈顶元素，不删除
*/
public int top() {
if(empty()) {
return -1;
}
int e = -1;
if(!qu1.isEmpty()) {
int size = qu1.size();
for(int i = 0;i < size;i++){
e = qu1.poll();
qu2.offer(e);
}
}else{
int size = qu2.size();
for(int i = 0;i < size;i++){
e = qu2.poll();
qu1.offer(e);
}
}
return e;
}
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}用栈实现队列
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);//指定push到第一个栈里面
}
public int pop() {
if(empty()) return -1;
if(s2.empty()) {
while(!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if(empty()) return -1;
if(s2.empty()) {
while(!s1.empty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.empty() && s2.empty();
}
}实现一个最小栈
public MinStack() {
}
public void push(int val) {
stack.push(val);
if(minStack.empty()) {
minStack.push(val);
}else{
int x = minStack.peek();
if(val <= x) {
minStack.push(val);
}
}
}
public void pop() {
int x = stack.pop();
if(x == minStack.peek()){
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}设计循环队列：
见前页