算法：（golang、java）实现数组栈

冷不防 2023-07-09 09:30 1阅读 0赞

# 使用数组实现栈 #

[https://www.cs.usfca.edu/~galles/visualization/StackArray.html][https_www.cs.usfca.edu_galles_visualization_StackArray.html]

## golang版本 ##

package main
    
    import "fmt"
    
    // 先进先出
    type myInterface interface {
        
    	Push(data interface{
        }) (error)
    	Pop() (interface{
        }, error)
    	Peek() (interface{
        }, error)
    	Clear()
    	Print()
    	Empty() bool
    	Size() int
    	Full() bool
    }
    
    type ArrayStack struct {
        
    	top int  // 下一个要存放的元素索引
    	buf [30]interface{
        }
    }
    
    func New() *ArrayStack  {
        
    	return &ArrayStack{
        
    		top:  0,
    	}
    }
    func (s *ArrayStack)Empty() bool{
        
    	return s.top == 0;
    }
    func (s *ArrayStack)Size() int{
        
    	return s.top;
    }
    func (s *ArrayStack)Full() bool{
        
    	return s.top == len(s.buf)
    }
    func (s *ArrayStack)Push(data interface{
        }) (error){
        
    	if data == nil {
        
    		return fmt.Errorf("data is nil")
    	}
    
    	if s.Full() {
        
    		return fmt.Errorf("stack is full")
    	}
    
    	s.buf[s.top] = data;
    	s.top++
    	return nil;
    }
    func (s *ArrayStack)Pop() (interface{
        }, error){
        
    	if s.Empty() {
        
    		return nil, fmt.Errorf("stack is empty")
    	}
    
    	s.top--
    	data := s.buf[s.top]
    	return data, nil
    }
    
    func (s *ArrayStack)Peek() (interface{
        }, error){
        
    	if s.Empty() {
        
    		return nil, fmt.Errorf("stack is empty")
    	}
    
    	return s.buf[s.top - 1], nil
    }
    func (s *ArrayStack)Clear(){
        
    	s.top = 0
    }
    func (s *ArrayStack)Print(){
        
    	for i := 0; i < s.top; i++{
        
    		fmt.Print(s.buf[i], "\t")
    	}
    	fmt.Println()
    }
    
    
    
    
    func main(){
        
    	stack := New();
    
    	for i := 0; i < 10; i++{
        
    		_ = stack.Push(i)
    	}
    
    
    	fmt.Println(stack.Full(), stack.Size(), stack.Empty())
    	stack.Print()
    
    	for !stack.Empty(){
        
    		_, _ = stack.Pop()
    		stack.Print()
    	}
    }

## java版本 ##

package com.company;
    
    
    public class Stack_ArreyImplemention {
        
        private int top;
        private Object[] array;
    
    
        // 在构造函数中初始化
        public Stack_ArreyImplemention() {
        
            this.top = 0;  // 刚开始时什么都没有存储
            this.array = new Object[20]; //初始化一个数组用来存储数据
        }
    
        //可以指定数组函数
        public Stack_ArreyImplemention(int cap){
        
            if (cap <= 0){
        
                System.out.println("Stack的长度必须大于0");
                return;
            }
    
            this.array = new Object[cap];
        }
    
    
        // 入栈：0表示入栈成功，-1表示操作失败
        /*
         * top = 0， 表示当前什么数据都没有存储。 下一个要存储的索引时 index[0]
         * top = 1, 表示当前栈已经有一个元素了，下一个要存的索引时index[1]
         *
         * 数组的长度是array.length， 数组最大的索引是array.length - 1
         * 所以当top == array.length-1时，表示当前还有一个元素可以入栈
         * 当top == array.length时，因为索引不可能为index[array.length]，表示当前已经没有位置放置元素了
         * */
        public int Push(Object value){
        
            // 先要判断栈是否满了
            if (top == array.length){
        
                System.out.println("已满栈");
                return -1;
            }
    
            array[top] = value;
            top++;
            return  0;
        }
    
        // 出栈：如果出栈成功返回出栈的元素，如果返回出栈失败，打印消息提示，并且返回-1
        public Object pop(){
        
            // 要出栈：先判断当前栈是否是空栈。如果是空的，那么返回-1
            if (top == 0){
        
                System.out.println("空栈，没有元素可以出");
                return  -1;
            }
    
            // top - 1 ，就是要本次要出栈的元素的索引
            top--;
            return array[top];
        }
    
        // 查看栈里面放置了什么
        public void getStack(){
        
            // 如果top = 0； 表示没有元素入栈
            // top = 1， 表示有一个元素入栈，索引为0
            for (int i = 0; i < top; i++){
        
                System.out.print(array[i] + "\t");
            }
        }
    
    
        // 是否是空栈
        public boolean isEmpty(){
        
            if (top == 0){
        
                return true;
            }
            return false;
        }
    
        // 是否是满栈
        public  boolean isFull(){
        
            if (top == this.array.length){
        
                return true;
            }
            return false;
        }
    
    }

*  测试

package com.company;
    
    public class Test_stack {
        
        public static void main(String[] args) {
        
            Stack_ArreyImplemention stack_arreyImplemention = new Stack_ArreyImplemention(3);
    
            stack_arreyImplemention.Push(1);
            stack_arreyImplemention.Push(2);
            stack_arreyImplemention.Push(3);
            stack_arreyImplemention.getStack();
            System.out.println("是否是满栈：" + stack_arreyImplemention.isFull());
    
    
            stack_arreyImplemention.pop();
            stack_arreyImplemention.getStack();
            System.out.println("是否是满栈：" + stack_arreyImplemention.isFull());
    
            stack_arreyImplemention.pop();
            stack_arreyImplemention.getStack();
        }
    }

[https_www.cs.usfca.edu_galles_visualization_StackArray.html]: https://www.cs.usfca.edu/~galles/visualization/StackArray.html