数据结构第3讲栈

谁借莪１个温暖的怀抱￠ 2022-03-08 02:18 153阅读 0赞

栈又称堆栈,它是运算受限的线性表,其限制是仅允许在表的一段进行插入和删除操作,不允许在其他任何位置进行插入、删除等操作,表中进行插入、删除操作的一端称为栈顶,栈顶保存的元素称为栈顶元素,表的另一端称为栈底。

![image][]  
f方法一:数组实现的栈，能存储任意类型的数据

import java.lang.reflect.Array;
    
    //数组实现的栈，能存储任意类型的数据
    public class Stacktest<T>{
    
    	 private static final int  SIZE = 12;
    	 private T[] Arrays;
    	 private int count;
    	 
    	 public Stacktest(Class<T> type){
    		 this(type,SIZE);
    	 }
    	// 不能直接使用Arrays = new T[SIZE];
    	public Stacktest(Class<T> type,int size){
    	Arrays =(T[]) Array.newInstance(type,size);
    	count =0;
    	}
    
    	// 将t添加到栈中
    	public void push(T t){
    		Arrays[count++] = t;
    	}
    	// 返回"栈顶元素值"
       public T peek(){
       	return Arrays[count-1];
       }
    // 返回"栈顶元素值"，并删除"栈顶元素"
       public T pop(){
       	T ret = Arrays[count-1];
       	count--;
       	return ret;
       }
    // 返回"栈"的大小
       public int size(){
       	return count;
       }
       // 返回"栈"是否为空
       public boolean isEmpty() {
           return size()==0;
       }
    
       // 打印"栈"
       public void PrintArrayStack() {
           if (isEmpty()) {
               System.out.printf("stack is Empty\n");
           }
    
           System.out.printf("size()=%d\n", size());
    
           int i=size()-1;
           while (i>=0) {
               System.out.println(Arrays[i]);
               i--;
           }
       }
    
       public static void main(String[] args) {
           String string;
           // 将10, 20, 30 依次推入栈中
           Stacktest<String> stack = new Stacktest<String>(String.class);    
           stack.push("10");
           stack.push("20");
           stack.push("30");
    
           // 将"栈顶元素"赋值给stack，并删除"栈顶元素"
           string = stack.pop();
           System.out.println("stack="+string);
    
           // 只将"栈顶"赋值给stack，不删除该元素.
           string = stack.peek();
           System.out.println("stack="+string);
    
           stack.push("30");
           stack.PrintArrayStack();    // 打印栈
       }
    }

![image][image 1]  
方法二:Java的 Collection集合 中自带的"栈"(stack)的示例

import java.util.Stack;
    
    public class Test {
        public static void main(String[] args) {
       int num=0;
    // 将10, 20, 30 依次推入栈中
       Stack<Integer> test = new Stack<Integer>();
       test.push(10);
       test.push(20);
       test.push(30);
    // 将"栈顶元素"赋值给num，并删除"栈顶元素"
       num = test.pop();
    // 只将"栈顶"赋值给num，不删除该元素. 
       num = (int)test.peek();
       test.push(30);
       while (!test.empty()) {
    	num = (int)test.pop();
    	  System.out.printf("num=%d\n",num);
            }
    	}
    }

![image][image 2]

[image]: /images/20220308/bce6a451d5d64f2493636648ec9cd4c0.png
[image 1]: /images/20220308/6330020346b44232a46537d97f8c3177.png
[image 2]: /images/20220308/a52fdcc9012641158aac554cd9dcef29.png