数据结构—栈

数据结构—栈 简介：

只允许在一端进行插入或删除 *** 作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除 *** 作。

示意图：

①用数组模拟栈 思路分析：

1. 使用数组来模拟栈
2. 定义一个 top 来表示栈顶，初始化 为 -1
3. 入栈的 *** 作，当有数据加入到栈时， top++; stack[top] = data;
4. 出栈的 *** 作， int value = stack[top]; top–, return value

实现代码：

package com.xawl.stack;

import java.util.Scanner;

public class ArrayStackDemo {

	public static void main(String[] args) {
		
		ArrayStack stack = new ArrayStack(4);
		int key;
		boolean loop = true;
		Scanner scanner = new Scanner( System.in);
		
		while (loop) {
			System.out.println("1:显示栈");
			System.out.println("2:入栈");
			System.out.println("3:出栈");
			System.out.println("0:退出栈");
			System.out.println("请输入你的选择：");
			
			key = scanner.nextInt();
			switch (key) {
			case 1:
				stack.list();
				break;
			case 2:
				System.out.println("请输入一个数");
				int value = scanner.nextInt();
				stack.push(value);
				break;
			case 3:
				
				try {
					int res = stack.pop();
					System.out.println("出栈的数据是："+res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				
				break;
			case 0:
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}
		System.out.println("退出");
		
	}
	
	//使用数组模拟一个栈
static	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;
		}
		
		//栈空
		private 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("栈空");
				return;
			}
			
			for (int i = top; i >= 0 ; i--) {
				System.out.println("stack[" + i +"]=" +stack[i] );
			}
		}
	}
}

②用链表模拟栈 思路分析：

1. 利用链表的头结点作为栈顶的元素。
2. 入栈，相当于新new一个头结点，然后让新节点指向单链表的头结点。以新节点作为单链表的头节点即可。
3. 出栈，只要将链表的头指针后移到它的next，将next作为新的头结点即可
4. 当要遍历的时候，只要返回头结点的值就好了。

代码实现：

package com.xawl.stack;

import java.util.Scanner;

import javax.swing.text.TabStop;
import javax.tools.ToolProvider;

public class linkedListStackDemo {

	public static void main(String[] args) {
		
		linkedListStack stack = new linkedListStack();
		
		int key;
		boolean loop = true;
		Scanner scanner = new Scanner( System.in);
		
		while (loop) {
			System.out.println("1:显示栈");
			System.out.println("2:入栈");
			System.out.println("3:出栈");
			System.out.println("0:退出栈");
			System.out.println("请输入你的选择：");
			
			key = scanner.nextInt();
			switch (key) {
			case 1: 
					stack.list();	
				break;
			case 2:
				System.out.println("请输入一个数");
				int value = scanner.nextInt();
				stack.push(value);
				break;
			case 3:
				
				try {
					int res = stack.pop();
					System.out.println("出栈的数据是："+res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				
				break;
			case 0:
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}

	}
}
		
//节点类
class Node{
	
		public int val;
		public Node next = null;
		
		public  Node(int val) {
			this.val = val;
		}
	
		@Override
		public String toString() {
			return "Node [val=" + val + "]";
		}	
}

class linkedListStack{	
	
	private Node top =  new Node(-1);
	
	//栈空
	private boolean isEmpty() {
		
		return top.next == null;

	}
	
	//入栈
	public void push(int value) {		
		Node node = new Node(value);
		node.next = top.next;
		top.next = node;
	}
	
	//出栈
	public int pop() {
		if (isEmpty()) {
			throw new RuntimeException("栈空");
		}
		
		int value = top.next.val;
		top.next = top.next.next;
		return value;		
	}
	
	//遍历栈
		public void list() {
			if (isEmpty()) {
				System.out.println("栈空");
				return;
			}
			 Node cur = top.next;			 
			 while (cur != null) {
				System.out.println("val=" + cur.val);
				cur =cur.next;
				
			}
		}
}