一．介紹
堆棧是一種數(shù)據(jù)結(jié)構(gòu)，是只能在某一端插入和刪除的特殊線性表。它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)（最后一個(gè)數(shù)據(jù)被第一個(gè)讀出來）。
堆棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為先進(jìn)后出表（Last In First Out , 簡(jiǎn)稱LIFO）。
比如：堆棧就是一個(gè)桶，后放進(jìn)去的先拿出來，它下面本來有的東西要等它出來之后才能出來。
二．知識(shí)點(diǎn)介紹
1、堆棧原理
2、Stack使用
三．上課對(duì)應(yīng)視頻的說明文檔
1、堆棧原理
(1) 一圖：當(dāng)棧里面沒有任何元素的時(shí)候，為空棧，棧頂和棧底在同一個(gè)位置
(2) 二圖：當(dāng)A元素進(jìn)入我們的棧里面后，他所進(jìn)入的過程叫入棧，棧底不變，棧頂為A元素的上部
(3) 三圖：在棧中加入B，C,D三個(gè)元素后，棧底不變，棧頂為D元素上部
(4) 四圖：D元素被移出，這個(gè)過程叫出棧，棧底不變，棧頂發(fā)生變化，棧頂為C元素的上部
2、Stack使用
public push(item) 把項(xiàng)壓入棧頂。其作用與 addElement (item ) 相同。
參數(shù) item 壓入棧頂?shù)捻?xiàng) 。 返回： item 參數(shù)
public pop () 移除棧頂對(duì)象，并作為函數(shù)的值 返回該對(duì)象。
返回：棧頂對(duì)象（Vector 對(duì)象的中的最后一項(xiàng)）。
拋出異常 ： EmptyStackException 如果堆棧式空的 。。。
public peek() 查看棧頂對(duì)象而不移除它。。
返回：棧頂對(duì)象（Vector 對(duì)象的中的最后一項(xiàng)）。
拋出異常 ： EmptyStackException 如果堆棧式空的 。。。
public boolean empty （測(cè)試堆棧是否為空。）? 當(dāng)且僅當(dāng)堆棧中不含任何項(xiàng)時(shí) 返回 true，否則 返回 false.
public int search? (object o)? 返回對(duì)象在堆棧中位置， 以 1 為基數(shù)， 如果對(duì)象 ｏ是棧中的一項(xiàng)，該方法返回距離 棧頂最近的出現(xiàn)位置到棧頂?shù)木嚯x； 棧中最上端項(xiàng)的距離為?。薄 ！∈褂胑quals 方法比較 o 與 堆棧中的項(xiàng)。。。?
案例：
import java.util.*;
public class StackTest{
public static void main(String args[]){
Stack s=new Stack();//產(chǎn)生一個(gè)空棧
s.push("A");
s.push("B");//入棧
s.push("C");
System.out.println(s.peek());//顯示棧頂?shù)脑?/p>
//System.out.println(s.pop());//顯示棧頂?shù)脑?，并移出?/p>
System.out.println(s);
System.out.println(s.search("A"));
Iterator i=s.iterator();
while(i.hasNext()){
System.out.println(i.next());
}
/*
while(!s.empty()){
System.out.println(s.peek());
}
System.out.println(s);
*/
}
}
案例：數(shù)組實(shí)現(xiàn)堆棧
public class ArrayOfStack {
private Object[] stack = null;
private int size;
private int top;
//默認(rèn)初始化一個(gè)棧堆,大小為100
public ArrayOfStack(){
this.size = 100;
this.top = -1;
this.stack = new Object[size];
}
//初始化一個(gè)自定義大小的棧堆
public ArrayOfStack(int size){
this.size = size;
this.top = -1;
this.stack = new Object[size];
}
//判斷堆棧是否為空
public boolean isEmpty(){
if(top == -1){
return true;
}else
return false;
}
//判斷棧堆是否已滿
public boolean isFull(){
if(top == (size-1)){
return true;
}else
return true;
}
//入棧操作
public void push(String data){
if(isFull()){
System.out.println("堆棧已滿");
return;
}
//入棧開始，top相當(dāng)于數(shù)組下標(biāo)
top++;
stack[top] = data;
}
//出棧
public Object pop(){
//定義一個(gè)臨時(shí)對(duì)象
Object val = null;
//堆棧為空時(shí)報(bào)錯(cuò)
if(isEmpty()){
System.out.println("堆棧為空");
return val;
}
//獲取堆棧值
val = stack[top];
top--;
return val;
}
//獲取棧頂元素
public Object peek(){
Object topVal = null;
if(isEmpty()){
System.out.println("棧堆為空!");
return topVal;
}
//取出棧頂元素
topVal = stack[top];
return topVal;
}
//獲取堆棧元素
public int size(){
return top+1;
}
//獲取棧堆容量
public int capcity(){
return size;
}
}
案例：鏈表實(shí)現(xiàn)堆棧
public class Node {
//鏈表數(shù)據(jù)域
Object data;
//鏈域
Node next;
//構(gòu)造頭結(jié)點(diǎn)
public Node(){
this.data = null;
this.next = null;
}
//構(gòu)造節(jié)點(diǎn)
public Node(Object data){
this.data = data;
this.next = null;
}
}
案例：堆棧類
public class LinkOfStack {
//定義一個(gè)頭結(jié)點(diǎn)
private Node head;
//構(gòu)造頭結(jié)點(diǎn)
public LinkOfStack(){
head = new Node();
}
//判斷是否為空
public boolean empty(){
if(head.next == null)
return true;
else
return false;
}
//堆棧入棧
public void push(Object data){
Node item = new Node(data);
item.next = head.next;
head.next = item;
}
//出棧
public Object pop(){
Object item = null;
if(empty()){
System.out.println("堆棧為空");
}
item = head.next.data;
head.next = head.next.next;
return item;
}
//堆棧大小
public int size(){
int len = 0;
Node p = head;
while(p.next != null){
len++;
p = p.next;
}
return len;
}
//獲取棧頂元素
public Object peek(){
if(empty()){
System.out.println("堆棧為空");
}
return head.next.data;
}
public static void main(String[] args){
LinkOfStack stack = new LinkOfStack();
stack.push("測(cè)試鏈表堆棧節(jié)點(diǎn)一");
System.out.println(stack.size());
System.out.println(stack.peek());
while(!stack.empty()){
System.out.print(stack.pop()+"-->");
}
}
}
