Java中的Stack

Java中的Stack

在Java中，Stack 类是一个基于后进先出（Last In, First Out，LIFO）原则的集合类。它继承自Vector类，但主要被设计为提供栈的行为。

特点和用途

1. 后进先出： 栈是一种后进先出的数据结构，最后压入栈的元素将最先弹出。

2. 继承关系： Stack 类继承自 Vector 类，因此它包含了向量的所有方法，并且可以通过这些方法实现栈的操作。

3. 基本操作：

   • push(E item): 将元素推入栈的顶部。
   • pop(): 移除并返回栈顶的元素。
   • peek(): 返回栈顶的元素，但不移除它。
   • isEmpty(): 判断栈是否为空。
   • search(Object o): 查找元素在栈中的位置，返回距栈顶最近的索引，栈顶的位置为1。

4. 用途： 栈在很多算法和程序中有广泛应用，例如递归、表达式求值、浏览器的前进和后退功能等。

示例

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 创建一个栈
        Stack<String> stack = new Stack<>();

        // 元素入栈
        stack.push("Java");
        stack.push("C++");
        stack.push("Python");

        // 输出栈顶元素
        System.out.println("Top element: " + stack.peek());

        // 弹出栈顶元素
        String poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);

        // 判断栈是否为空
        System.out.println("Is stack empty? " + stack.empty());

        // 查找元素在栈中的位置
        int position = stack.search("Java");
        System.out.println("Position of 'Java': " + position);
    }
}

上述示例演示了Stack类的基本用法，包括元素的推入、弹出、查看栈顶元素以及其他一些常见的操作。在实际应用中，Deque接口的实现类ArrayDeque也可以用作栈的替代品，因为它提供了更好的性能。

利用数组来模拟栈

package stackDemo;

import java.util.Arrays;
import java.util.Scanner;

import javax.sound.midi.Synthesizer;

import org.omg.Messaging.SyncScopeHelper;

public class ShuzuStack {

	public static void main(String[] args) {
		ArrayStack arrayStack = new ArrayStack(4);
		String key = "";
		boolean loop = true;
		Scanner scanner = new Scanner(System.in);
		
		while(loop){
			System.out.println("show:表示显示栈");
			System.out.println("exit：退出程序");
			System.out.println("push:表示添加数据到栈");
			System.out.println("pop:表示从栈取出数据");
			System.out.println("请输入");
			key = scanner.next();
			
			switch(key){
			case"show":
				arrayStack.list();
				break;
			case"push":
				System.out.println("请输入一个数");
				int value = scanner.nextInt();
				arrayStack.push(value);
				break;
			case"pop":
				try {
					int res = arrayStack.pop();
					System.out.println("出栈的数据是"+res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case"exit":
				scanner.close();
				System.out.println("拜拜");
				loop = false;
				break;
			default:
				break;
			}
		}
		

	}

}

class ArrayStack{
	private int maxSize;
	private int[] stack;
	private int top = -1;
	
	public ArrayStack(int maxSize){
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	
	//栈满
	public boolean isFull(){
		return top == maxSize-1;
	}
	
	//栈空
	public boolean isEmpty(){
		return top == -1;
	}
	
	//入栈
	public void push(int value){
		if(isFull()){
			System.out.println("栈满");
			return;
		}
		top++;
		stack[top] = value;
	}
	
	//出栈
	public int pop(){
		if(isEmpty()){
			throw new RuntimeException("栈空，没有数据");
		}
		int value = stack[top];
		top--;
		return value;
	}
	
	public void list(){
		if(isEmpty()){
			System.out.println("栈空");
		}else{
			//System.out.println(Arrays.asList(stack));
			for(int i = 0;i<maxSize;i++){
				System.out.println(stack[i]+" ");
			}
		}
	}
}

用链表创建栈

采用的是单链表，头插法。设置节点top，采用第一种方法，使得top始终在最顶端，非常巧妙。

package stackDemo;

import org.omg.Messaging.SyncScopeHelper;

public class LinkStack {
	public static void main(String[] args){
		Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        SingleLinkedListStack singleLinkedListStack = new SingleLinkedListStack();
        singleLinkedListStack.push(node1);
        singleLinkedListStack.push(node2);
        singleLinkedListStack.push(node3);
        singleLinkedListStack.push(node4);
        singleLinkedListStack.pop();
        singleLinkedListStack.show();
	}
}
class SingleLinkedListStack{
	private Node top = new Node(0);
	
	//判断栈是否为空
	public boolean isEmpty(){
		return top.next == null;	
	}
	
	//入栈
	public void push(Node node){
		if(isEmpty()){
			top.next = node;
			return;
		}
		//定义辅助变量。
		//一：将nodet给top的next
		//二：将temp的值给node的next域
		Node temp = top.next;
		top.next = node;
		node.next = temp;
	}
	
	//出栈
	public void pop(){
		if(isEmpty()){
			System.out.println("栈空");
			return;
		}
		System.out.println("出栈节点为："+top.next.value);
		top = top.next;
	}
	
	//遍历
	public void show(){
		if(isEmpty()){
			System.out.println("栈为空");
			return;
		}
		Node temp = top;
		while(temp.next  != null){
			System.out.println("节点为"+temp.next.value);
			temp = temp.next;
		}
	}
}

class Node{
	public int value;
	public Node next;
	
	public Node(int value){
		this.value = value;
	}
	
}