如何加强英文网站建设,新余门户网站建设,网站seo关键字,网站建设 python内容1.理解栈的基本特征2.理解如何使用数组来构造栈3.理解如何使用链表来构造栈 1.栈的基础知识
1.1栈的特征
栈和队列是比较特殊的线性表#xff0c;又称为访问受限的线性表。栈是很多表达式、符号等运算的基础#xff0c;也是递归的底层实现#xff0c;理论上递归能做的…内容1.理解栈的基本特征2.理解如何使用数组来构造栈3.理解如何使用链表来构造栈 1.栈的基础知识
1.1栈的特征
栈和队列是比较特殊的线性表又称为访问受限的线性表。栈是很多表达式、符号等运算的基础也是递归的底层实现理论上递归能做的题目栈都可以就是有些问题用栈回非常复杂
栈底层实现仍然是链表或者顺序表栈于线性表的最大区别就是数据的存取的操作被限制了其插入删除操作只允许在线性表的一段进行一般而言把允许操作的一端称为栈顶Top)不可操作的一端称为栈底(Bottom)同时把插入元素的操作称为入栈(Push)删除元素的操作称为出栈Pop。若栈中没有任何元素则称为空栈栈的结构如下图
1.2栈的操作
栈的常用操作主要有 push(E):增加一个元素Epop():弹出元素Epeek():显示栈顶元素但是不出栈empty():判断栈是否为空
我们在设计自己的栈的时候不管用数组还是链表都要实现上面几个方法。
1.3Java中的栈 Java的util中就提供了栈Stack类使用不复杂看一个例子就够了
public class MainTest {public static void main(String[] args) {StackInteger stack new Stack();stack.push(1);stack.push(2);stack.push(3);System.out.println(栈顶元素为 stack.peek());while (!stack.empty()) {//只显示没出栈System.out.println(stack.peek());//出栈并且显示System.out.println(stack.pop());}}
}2.基于数组实现栈 在看具体内容之前 先补充一个知识点top有的地方指向栈顶元素有的地方指向栈顶再往上的一个空单位这个根据题目要求设计就好本文采用指向栈顶空位置。 如果要我们自己实现栈可以有链表、数组和java提供的LinkedList三种基本方式我们都来写一下吧。
采用顺序表实现的栈吗内部以数组为基础实现对元素的存取操作。在应用中还需要注意每次入栈之前先判断栈的容量是否够用如果不够用可以进行扩容。
入栈过程如下
出栈的过程如图所示 top先将栈顶元素取出来然后再执行top--。
完整的实现代码是
import java.util.Arrays;
class MystackT {//实现栈的数组private Object[] stack;//栈顶元素private int top;Mystack() {//初始容量为10stack new Object[10];}//判断是否为空public boolean isEmpty() {return top 0;}//返回栈顶元素public T peek() {T t null;if (top 0)t (T) stack[top - 1];return t;}public void push(T t) {expandCapacity(top 1);stack[top] t;top;}//出栈public T pop() {T t peek();if (top 0) {stack[top - 1] null;top--;}return t;}//扩大容量public void expandCapacity(int size) {int len stack.length;if (size len) {size size * 3 / 2 1;//每次扩大50%stack Arrays.copyOf(stack, size);}}public static void main(String[] args) {MystackString stack new Mystack();System.out.println(stack.peek());System.out.println(stack.isEmpty());stack.push(java);stack.push(is);stack.push(beautiful);stack.push(language);System.out.println(stack.pop());System.out.println(stack.isEmpty());System.out.println(stack.peek());}
} 3.基于链表实现栈
链表也可以实现栈插入和删除都在头结点进行就可以了。 在链表一章我们介绍过没有虚拟结点时对链表头元素进行插入和删除的操作方法而与这里基于链表实现栈是完全一致的。
package com.yugutou.charpter4_stack.level1;class ListStackT {//定义链表class NodeT {public T t;public Node next;}public NodeT head;//构造函数初始化头指针ListStack() {head null;}//入栈public void push(T t) {if (t null) {throw new NullPointerException(参数不能为空);}if (head null) {head new NodeT();head.t t;head.next null;} else {NodeT temp head;head new Node();head.t t;head.next temp;}}//出栈public T pop() {if (head null) {return null;}T t head.t;head head.next;return t;}//取栈顶元素public T peek() {if (head null) {return null;}T t head.t;return t;}//栈空public boolean isEmpty() {if (head null)return true;elsereturn false;}public static void main(String[] args) {ListStack stack new ListStack();System.out.println(stack.isEmpty());stack.push(Java);stack.push(is);stack.push(beautiful);System.out.println(stack.peek());System.out.println(stack.pop());System.out.println(stack.isEmpty());}
}
