在各种应试中经常问到的一个问题,请将字符串反转
八戒:这还不简单,利用StringBuffer/StringBuilder的reverse()函数,1秒钟搞定
StringBuilder sb = new StringBuilder("abc");
System.out.println(sb.reverse());
问题是题目往往明确要求不使用这些类,出题人期望的是考察应试者的数据结构本领
八戒:恩,那就用for循环取xxx.charAt(i)好了
GOOD JOB!原理是这样的没错
但我们可以通过模拟栈的数据结构,使得自己看似更专业些(主因),同时对栈有一个更好的认识(辅因)
度娘百科:栈,是硬件。主要作用表现为一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
栈其实是一种硬件,所以我们只是模拟其数据操作的结构。
例如计算机是如何识别1+2操作的?我们都知道后缀表达式为12+,计算机无外乎将1入栈,将2入栈,发现+号,依次出栈tmp2=2,tmp1=1,进行tmp1+tmp2
Java提供了我们一个Stack类,现在我们就用其来实现一下逆序
package com.cn;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class TestReverseByStack {
public static String readInput() throws IOException{
InputStreamReader read = new InputStreamReader(System.in);
BufferedReader buffer = new BufferedReader(read);
return buffer.readLine();
}
public static void main(String[] args) throws IOException{
System.out.println("plz input a string:");
String str = readInput();
String result = "";
Stack s = new Stack();
for(int i=0;i<str.length();i++){
s.push(str.charAt(i));
}
for(int i=0;i<str.length();i++){
result += s.pop();
}
System.out.println("after reversing:"+result);
}
}
我们简单的瞅瞅java.util.Stack类的源代码
public class Stack<E> extends Vector<E> {
public Stack() {
}
public E push(E item) {
addElement(item);
return item;
}
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
}
Stack类是Vector的子类,实际上是使用Object数组来模拟一个栈的过程
Stack类又提供了同步的push pop peek等方法来达到模拟先进后出的结构
分享到:
相关推荐
《数据结构与算法》注重理论与实践相结合,内容深入浅出,可以作为高等院校计算机学科相关专业的教材或参考书,同时对计算机科技工作者也有参考价值。 序言 前言 第1章 java与面向对象程序设计 第2章 数据结构...
Java数据结构和算法介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、...
MySql的主从实时备份同步的配置,以及原理(从库读主库的binlog),读写分离 Mysql主从同步的实现原理 MySQL索引背后的数据结构及算法原理 摘要数据结构及算法基础 索引的本质 B-Tree和B+Tree B-Tree B+Tree 带有顺序...
MySql的主从实时备份同步的配置,以及原理(从库读主库的binlog),读写分离 Mysql主从同步的实现原理 MySQL索引背后的数据结构及算法原理 摘要数据结构及算法基础 索引的本质 B-Tree和B+Tree B-Tree B+Tree 带有顺序...
数据结构与程序设计,C#语言表述。 编者在写这本书时遇到了两个问题。第一个问题是关于数据结构教材。应该说关于数 据结构的教材已经很多了。自从美国唐.欧.克努特教授用汇编语言写的《计算机程序设计 技巧》第一...
2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...
2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...
2012-05-27 11:08 180,401 Java基础复习笔记05数据结构-栈.pdf 2012-05-27 11:05 834,613 jqueryui-API(最完整).pdf 2012-05-27 10:58 31,758,963 Linux程序设计(原书第2版).pdf 2012-05-27 11:03 2,023,736 ...
MySql的主从实时备份同步的配置,以及原理(从库读主库的binlog),读写分离 Mysql主从同步的实现原理 MySQL索引背后的数据结构及算法原理 摘要数据结构及算法基础 索引的本质 B-Tree和B+Tree B-Tree B+Tree 带有顺序...
本书深入浅出地介绍了Java线程和并发,是一本完美的Java并发参考手册。书中从并发性和线程安全性的基本概念出发,介绍了如何使用类库提供的基本并发构建块,用于避免并发危险、构造线程安全的类及验证线程安全的规则...
实例110 Java对象的浅克隆 135 实例111 Java对象的深克隆 137 实例112 序列化与对象克隆 139 实例113 深克隆效率的比较 141 实例114 transient关键字的应用 143 5.7 接口和内部类 145 实例115 使用sort()方法排序 ...
MySql的主从实时备份同步的配置,以及原理(从库读主库的binlog),读写分离 Mysql主从同步的实现原理 MySQL索引背后的数据结构及算法原理 摘要数据结构及算法基础 索引的本质 B-Tree和B+Tree B-Tree B+Tree 带有顺序...
2012-06-11 21:09 1,553,768 数据结构算法Visual.C.6.0程序集_源码.rar 2012-06-11 21:42 87,040 时域卷积定理的证明.ppt 2012-06-11 21:10 4,371 更改网关IP.rar 2012-06-11 20:57 1,419 栈的实现.txt 2012-06-11 ...
25 JAVA8 与元数据.................................................................................................................................25 2.4. 垃圾回收与算法 .................................
第48节:Android 4.x重要内核数据结构.zip 第49节:Android 4.x字符设备驱动程序示例.zip 第50节:另一种简单的字符设备驱动框架.zip 第51节:用Android NDK测试LED驱动.zip 第52节:Android的蜂鸣器驱动.zip 第53节...
《HotSpot实战》深入浅出地讲解了HotSpot虚拟机的工作原理,将隐藏在它内部的本质内容逐一呈现在读者面前,包括OpenJDK与HotSpot项目、编译和调试HotSpot的方法、HotSpot内核结构、Launcher、OOP-Klass对象表示系统...