栈是基本的数据结构,它遵循后进先出原则(LIFO,即Last In Frist Out),一次只许访问一个元素,即栈顶的元素。在实现生活中,就像一串糖葫芦,只能吃最上面的糖葫芦,吃完第一个后,才能吃第二个。同时,插葫芦也只能从上往下,一个个的插。
在JDK中,util包中有一个用Vector实现的栈,这里我们用数组实现一个简单的栈。它应该包括入栈、出栈、判空、判满、查看栈顶元素等方法,其代码如下:
- public class Stack
- {
- //数据项、大小、栈顶标志
- private Object[] items;
- private int size;
- private int top;
- public Stack(int size)
- {
- items = new Object[size];
- this.size = size;
- top = 0;
- }
- //判满
- public boolean isFull()
- {
- return top == size;
- }
- //判空
- public boolean isEmpty()
- {
- return top == 0;
- }
- //查看栈顶元素
- public Object peek()
- {
- if(!isEmpty()){
- return items[top-1];
- }
- else
- throw new IndexOutOfBoundsException("the stack is empty");
- }
- //入栈
- public void push(Object item)
- {
- if(!isFull())
- items[top++] = item;
- else
- throw new IndexOutOfBoundsException("the stack is full");
- }
- //出栈
- public Object pop()
- {
- if(!isEmpty()){
- return items[--top];
- }
- else
- throw new IndexOutOfBoundsException("the stack is empty");
- }
- }
有了栈,我们要实现单词逆序就相当简单了,其代码如下:
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- public class ReverseWord
- {
- //原始字符串、栈
- private String str;
- private Stack xStack;
- public ReverseWord(String str)
- {
- this.str = str;
- init();
- }
- //初始化栈
- private void init()
- {
- this.xStack = new Stack(str.length());
- for (int i = 0; i < str.length(); i++) {
- xStack.push(str.charAt(i));
- }
- }
- //反转字符串
- public String reverse()
- {
- String out="";
- for (int i = 0; i < str.length(); i++) {
- out =out + xStack.pop();
- }
- return out;
- }
- public static void main(String[] args) throws IOException {
- System.out.println("输入镜子里的字:");
- InputStreamReader isr = new InputStreamReader(System.in);
- BufferedReader br = new BufferedReader(isr);
- String str = br.readLine();
- ReverseWord rw = new ReverseWord(str);
- System.out.println("我想说的是:");
- System.out.println(rw.reverse());
- }
- }
运行程序,提示我们“输入镜子里的字”时,输入uoyevol I,回车,显示“我想说的是:I love you”。
- 输入镜子里的字:
- uoy evol I
- 我想的是说:
- I love you