栈: 是限定仅在表尾插入和删除操作的线性表,允许插入和删除的一段称为栈顶,另一端为栈底。 栈的特点就是:后进先出。
栈的实现非常简单,在生活中的也时常应用到,如:表达式求值、函数的调用用栈保存数据、语法的检验、函数的递归实现等都是基于栈的实现。在这里利用一张图就可以清晰的展示栈的操作。对栈的操作时间复杂度都是常数,都是对栈顶元素的操作。
下面是笔者实现的一个顺序栈,利用数组来存放元素。
package org.TT.Stack;接下来笔者又用链接存储结构实现了一个-- 链栈。通常采用 单链表实现链栈,用单链表的头部做栈顶是最方便的,因为只能栈链栈的栈顶插入删除。
/** 栈:后进先出
* 栈是一个概念上的辅助工具。这里采用数组完成栈的操作,这里利用泛型,可以参入任何参数对象。
* 栈的数据项的出栈、入栈时间复杂度为常数 O(1)。
*
*/
public class Stack<T> {
private int maxSize;
private Object[] stackArray;
private int top;
// 创建一个指定大小的新栈,并将top指向栈底。
public Stack(int length){
maxSize = length;
stackArray = new Object[maxSize];
top = -1;
}
// 入栈,将top值加1,是它指向原栈顶的上面一个位置,并将新的值存入这个位置。(插入前top先加1)
public void push(T value){
if(isFull()){
throw new RuntimeException("栈满!不能插入!"); // 入栈前先判断是否已满
}
stackArray[++top] = value;
}
// 出栈, 返回top 标识的数据,然后减一。pop有效的从栈中移除了数据项,
// 虽然数据项仍然存在数组中(新的数据项会覆盖旧的数据项),但不再能访问。
@SuppressWarnings("unchecked")
public T pop(){
if(isEmpty()){
throw new RuntimeException("栈空!没有元素可取!"); // 出栈前判断栈是否为空
}
return (T)stackArray[top--];
}
// 取得栈定数据项
@SuppressWarnings("unchecked")
public T peek(){
return (T) stackArray[top];
}
// 判断栈是否为空,top 等于-1 时为空栈
public boolean isEmpty(){
return (top == -1);
}
// 判断栈是否栈满,top 等于maxSize -1 时栈满
public boolean isFull(){
return (top == maxSize -1);
}
@SuppressWarnings("unchecked")
public T get(int index) {
return (T) stackArray[index];
}
public void display(String str) {
System.out.print(str);
System.out.print(" Stack (bottom-->top): ");
for (int i = 0; i < maxSize; i++) {
System.out.print(get(i)+" ");
}
System.out.println();
}
// 测试 栈
public static void main(String[] args) {
Stack<String> stack = new Stack<>(5);
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.push("e");
while(!stack.isEmpty()){ // 依次出栈
String value = stack.pop();
System.out.print(value + " ");
}
}
}
在这里,笔者采用前面说实现的 SingleLinkedList ,笔者可以参见前面的讲解,以下只是对链表进行了一次封装,进而实现了链栈。相信读者也能轻松理解栈的思想。
package org.TT.Stack;下面给读者带来一个应用: 单词逆序。 将输入的单词,逆序输出,入输入abcd, 得到的结果就是dcba。 这个就是应用栈的思想, 先将输入的单词分成字母,并将得到的字母分别压入栈中,在将字母分别出栈,并拼接成原来单词的逆序。
import org.TT.LinkedList.Node;
import org.TT.LinkedList.SingleLinkedList;
public class LinkStack<T> {
private SingleLinkedList<T> linkList;
public LinkStack(){
linkList = new SingleLinkedList<>();
}
public boolean isEmpty(){
return linkList.isEmpty();
}
public void push(T item){
linkList.insertFirst(item);
}
public Node<T> pop(){
return linkList.removeFirst();
}
public Node<T> peek(){
return linkList.getFirst();
}
public int stackSize(){
return linkList.getSize();
}
public void displayStack(){
linkList.printList();
}
public static void main(String[] args) {
LinkStack<String> linkStack = new LinkStack<>();
linkStack.push("A");
linkStack.push("B");
linkStack.push("C");
System.out.println("查看栈顶:" + linkStack.peek().getNodeValue());
System.out.println("栈的大小: " + linkStack.stackSize());
System.out.println("栈顶(C)出栈: " + linkStack.pop().getNodeValue());
System.out.print("C出栈后的栈:");
linkStack.displayStack();
// 进栈顺序 为 A、B、C 然后 把栈顶元素出栈(此时为:C), 所以再依次出栈为: B、 A
}
}
package org.TT.Stack;如图:
import java.util.Scanner;
/** 你用栈实现 单词逆序
*/
public class WordReversed {
private String input;
private String output;
public WordReversed(String in) {
input = in;
}
public String reversed(){
output = "";
int stackSize = input.length();
Stack<String> stack = new Stack<>(stackSize);
String str[] = input.split("");
for(int i = 0; i <input.length(); i++){
String ch = str[i];
stack.push(ch); // 将单词依次压栈,先进的单词就到了栈底,后进的在栈顶。
}
while(!stack.isEmpty()){
String ch = stack.pop(); // 将单词依次弹出栈,并保持每次弹出的数据项。
output = output + ch; // 先弹出栈顶(后进单词),所有顺序颠倒
}
return output;
}
@SuppressWarnings("resource")
public static void main(String[] args) {
String input, output;
while(true){
System.out.println("请输入字符串:");
Scanner in = new Scanner(System.in);
input = in.nextLine();
WordReversed reversed = new WordReversed(input);
output = reversed.reversed();
System.out.println("逆序为: " + output);
}
}
}
![java栈--后进先出(顺序栈、链栈、单词逆序) java栈--后进先出(顺序栈、链栈、单词逆序)](https://image.shishitao.com:8440/aHR0cHM6Ly93d3cuaXRkYWFuLmNvbS9nby9hSFIwY0RvdkwybHRaeTVpYkc5bkxtTnpaRzR1Ym1WMEx6SXdNVFl3TWpFMk1qRXdNRFF4TXprNFAzZGhkR1Z5YldGeWF5OHlMM1JsZUhRdllVaFNNR05FYjNaTU1rcHpZakpqZFZrelRtdGlhVFYxV2xoUmRpOW1iMjUwTHpWaE5rdzFUREpVTDJadmJuUnphWHBsTHpRd01DOW1hV3hzTDBrd1NrSlJhMFpEVFVFOVBTOWthWE56YjJ4MlpTODNNQzluY21GMmFYUjVMME5sYm5SbGNnPT0%3D.jpg?w=700&webp=1)
下面我们来简单说明一下,顺序栈和链栈的区别:顺序栈和链栈的操作的时间复杂度都是常数,但是顺序栈初始化时必须确认一个固定的长度,对于存储元素是有限制,并且还有可能浪费存储空间;链栈则没有栈满的情况,除非内存不足,当不确定元素个数是优先选择链栈。