【Java数据结构的实现】之系列四栈的数组实现(使用数组实现栈)
上一节我们一起学习了:栈的实现(使用栈计算后缀表达式),上节中栈的实现,我们使用的是java.util.Stack;来实现的栈,本章使用数组来实现,顺便介绍java.util.Stack。
4.1本节学习目标
- 栈的数组实现
- java.util.Stack讲解
4.1.1栈的数组实现
前面的教程中,我们一节学习了栈的基本特性,同时还使用了栈来求解一个问题(后缀表达式),细心的读者可以发现,我们根本不知道栈是如何实现的,这节,我们将探讨栈的实现。
栈的实现有多种方式,本节将介绍上述两种实现方式。
①栈的数组实现的思路:
- 数组是一个对象引用的数组,其数据类型在栈实例化时确定,使用泛型。
- 栈底在数组的index(索引)为0处。
- 栈的元素是安顺序存储在数组中
- 有个top变量,这个top变量包含两个含义:数组元素的数目和下一个可添加元素的索引位置。
我们可以用个实例图来表示上述的这个实现:
底 0 1 2 3 4 5 6 7 8 ……
A |
B |
C |
D |
E |
|
|
|
|
|
top 5
则表示:
- 栈底为索引位置0,
- 数组的大小为5 ,
- 下一个插入栈中的元素的索引位置为 5
程序关键部分有详细的注释。
②StackADT,是我们第二接里面的栈的抽象数据类型的定义:
如下:
- public interface StackADT<T> {
- /**
- * 往栈顶添加一个元素
- * */
- public void push(T element);
- /**
- * 从栈顶移除一个元素,并返回该元素
- * */
- public T pop();
- /**
- * 返回但不移除栈顶元素
- * */
- public T peek();
- /**
- * 判断是否为空
- * */
- public boolean isEmpty();
- /**
- * 返回栈大小
- * */
- public int size();
- /**
- * 返回栈的字符串的表示 toString
- * */
- //public String toString();
- }
③ArrayStack 实现StackADT接口
程序详解:
- public class ArrayStack<T> implements StackADT<T>{
- /**标识数组默认容量的变量*/
- private final int DEFAULT_CAPACITY = 100;
- /**标识数组的元素数目及下一个可用位置(下一元素压入位置)*/
- private int top;
- /**标识栈的泛型元素数组*/
- private T[] stack;
- /**
- * 使用默认容量创建一个空栈
- * */
- public ArrayStack() {
- top = 0;
- stack = (T[]) (new Object[DEFAULT_CAPACITY]);//实例化一个Object数组,然后转化为一个泛型数组
- }
- /**
- * 使用指定容量创建一个空栈,参数initialCapacity标识的是指定的容量
- * */
- public ArrayStack(int initialCapacity) {
- top = 0;
- stack = (T[]) (new Object[initialCapacity]);
- }
- 判断栈是否为空
- public boolean isEmpty() {
- if(size()==0) {
- return true;
- }else {
- return false;
- }
- }
- 出栈操作,栈为空,则出栈失败
- public T peek() {
- if(isEmpty()){
- System.out.println("栈为空,操作失败!");
- throw new EmptyStackException();
- }
- return stack[top-1];
- }
- /**
- * 数组实现的pop操作由以下几个步骤组成
- * ①却保栈不为空
- * ②计数器top--
- * ③设置临时引用等于stack[top]的元素
- * ④设置stack[top]为空
- * ⑤返回该临时引用
- * */
- public T pop() {
- if(isEmpty()) {
- System.out.println("栈为空,出栈失败!");
- throw new EmptyStackException();
- }
- top--;
- T result = stack[top];//top为栈顶元素,数组从0开始
- stack[top] = null;
- return result;
- }
- /**
- * 对于栈的数组的实现,其push操作由以下步骤构成
- * ①确保该数组不是蛮的
- * ②把数组的top引用设置为要加入到栈中的对象
- * ③增加top和count的值
- * */
- public void push(T element) {
- if(size()==stack.length) {
- expandCapacity();
- }
- stack[top] = element;
- top++;
- }
- /**
- * 使数组的大小加倍。由于数组一旦实例化以后就不能改变其大小,
- * 因此该方法是创建一个更大的数组,并把旧数组中的内容复制到新数组中
- * 它是类的一个支持方法,因此可以实现为私有的
- * */
- private void expandCapacity() {
- T[] larger = (T[]) new Object[stack.length*2];
- for(int index = 0;index<stack.length;index++){
- larger[index] = stack[index];
- stack = larger;
- }
- } 栈的大小,由变量top控制
- public int size() {
- return top;
- }
- }
④ArrayStack.java
- /**
- * @author 幽灵柯南
- * 日期 2011.11.16
- * 功能 用数组实现栈
- * */
- package com.yaxing.stack;
- import java.util.EmptyStackException;
- public class ArrayStack<T> implements StackADT<T>{
- /**标识数组默认容量的变量*/
- private final int DEFAULT_CAPACITY = 100;
- /**标识数组的元素数目及下一个可用位置(下一元素压入位置)*/
- private int top;
- /**标识栈的泛型元素数组*/
- private T[] stack;
- /**
- * 使用默认容量创建一个空栈
- * */
- public ArrayStack() {
- top = 0;
- stack = (T[]) (new Object[DEFAULT_CAPACITY]);//实例化一个Object数组,然后转化为一个泛型数组
- }
- /**
- * 使用指定容量创建一个空栈,参数initialCapacity标识的是指定的容量
- * */
- public ArrayStack(int initialCapacity) {
- top = 0;
- stack = (T[]) (new Object[initialCapacity]);
- }
- public boolean isEmpty() {
- if(size()==0) {
- return true;
- }else {
- return false;
- }
- }
- public T peek() {
- if(isEmpty()){
- System.out.println("栈为空,操作失败!");
- throw new EmptyStackException();
- }
- return stack[top-1];
- }
- /**
- * 数组实现的pop操作由以下几个步骤组成
- * ①却保栈不为空
- * ②计数器top--
- * ③设置临时引用等于stack[top]的元素
- * ④设置stack[top]为空
- * ⑤返回该临时引用
- * */
- public T pop() {
- if(isEmpty()) {
- System.out.println("栈为空,出栈失败!");
- throw new EmptyStackException();
- }
- top--;
- T result = stack[top];//top为栈顶元素,数组从0开始
- stack[top] = null;
- return result;
- }
- /**
- * 对于栈的数组的实现,其push操作由以下步骤构成
- * ①确保该数组不是蛮的
- * ②把数组的top引用设置为要加入到栈中的对象
- * ③增加top和count的值
- * */
- public void push(T element) {
- if(size()==stack.length) {
- expandCapacity();
- }
- stack[top] = element;
- top++;
- }
- /**
- * 使数组的大小加倍。由于数组一旦实例化以后就不能改变其大小,
- * 因此该方法是创建一个更大的数组,并把旧数组中的内容复制到新数组中
- * 它是类的一个支持方法,因此可以实现为私有的
- * */
- private void expandCapacity() {
- T[] larger = (T[]) new Object[stack.length*2];
- for(int index = 0;index<stack.length;index++){
- larger[index] = stack[index];
- stack = larger;
- }
- }
- public int size() {
- return top;
- }
- }
⑤测试方法:
- ArrayStack<T> arrayStack = new ArrayStack<T>();
- arrayStack.push((T) "A");
- arrayStack.push((T) "B");
- arrayStack.push((T) "B");
- arrayStack.push((T) "C");
- arrayStack.push((T) "D");
- arrayStack.push((T) "E");
- arrayStack.push((T) "F");
- System.out.println();
- System.out.println("栈的大小:"+arrayStack.size());
⑥测试结果:
- A、B、B、C、D、E、F、
- 栈的大小:7
本文转自 w156445045 51CTO博客,原文链接:http://blog.51cto.com/enetq/716020
,如需转载请自行联系原作者