数据结构和算法-4-栈和队列

末蓝、 2022-01-21 23:51 217阅读 0赞

这篇来学习什么栈和队列，以及栈和队列的基本特征，然后代码实现栈的实现

**1.栈**

栈（stack）也有叫堆栈，是一种容器，可存入数据元素，访问元素，删除元素，它的特点在于只能允许容器的一端（称为栈顶端，top）进行加入数据（push）和输出数据（pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认访问顺序。  
由于栈数据结构只允许一端进行操作，因而按照后进先出（LIFO, last in first out）的原因运作。

![20190604154437822.png][]

**2.队列**

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。  
队列是一种先进先出（First in First Out）的线性表。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=(a1,a2,a3,...an)，那么a1就是队头元素，an是队尾元素，这样我们就可以删除时，总是从a1开始，而插入时，总时在队列最后。这也比较符合我们生活中的习惯，排在第一个优先出列，最后来的当然排队伍最后。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

**3.栈结构的实现**

栈可以用顺序表实现，也可以用链表实现，链表后面来学。在python中,list是顺序表实现的，我们用list来实现栈。

栈的操作  
stack() 创建一个新的空栈  
push(item) 添加一个新的元素item到栈顶  
pop() 弹出栈顶元素  
peek() 返回栈顶元素  
is\_empty() 判断栈是否为空  
size() 返回栈的元素个数

**Python的实现方式**

# coding:utf-8
    
    
    class Stack(object):
        """定义一个栈"""
    
        def __init__(self):
            self.__list = []
    
        def push(self, item):
            """添加一个新的元素item到栈顶"""
            self.__list.append(item)  # append是尾部添加元素，这里选择尾部操作添加和删除
    
        def pop(self):
            """弹出栈顶元素"""
            return self.__list.pop()
    
        def peek(self):
            """返回栈顶元素"""
            if self.__list:
                return self.__list[-1]
            else:
                return None  # 如果为空返回null
    
        def is_empty(self):
            """判断栈是否为空"""
            return self.__list == []  # 判断是否为空列表
    
        def size(self):
            """返回栈内元素个数"""
            return len(self.__list)
    
    
    if __name__ == "__main__":
        s = Stack()
        s.push(1)
        s.push(2)
        s.push(3)
        s.push(4)
        print(s.size())
        print("===========")
        print(s.pop())
        print(s.pop())
        print(s.pop())
        print(s.pop())
    
        print(s.is_empty())

运行测试下

4
    ===========
    4
    3
    2
    1
    True

**Java的实现方式**

Java这边用数组来实现下栈的结构

package stack;
     
    public class MyStack {
    	//栈的底层是一个数组，由于一些特征，我们取名叫做栈
    	private long[] arr;
    	private int top; //元素索引
    	
    	/**
    	 * 默认无参构造
    	 */
        public MyStack() {
        	arr = new long[10];
        	top = -1; // 表示当前栈内没有元素，top等于0表示有一个元素
        }
        
        /**
         * 带参数的构造
         */
        public MyStack(int maxsize) {
        	arr = new long[maxsize];
        	top = -1;
        }
        
        /**
         * 添加数据
         */
        public void push(int value) {
        	// 由于top默认等于-1，所以没压栈一个元素，top就自增
        	arr[++top] = value;
        }
        
        /**
         * 移除数据
         */
        public long pop() {
        	// 由于栈特点，移除元素每次都是移除最上面的那一个
        	return arr[top--];
        }
        
        /**
         * 查看数据：查看数据和pop不同
         */
        public long peek() {
        	//只能查看最上面那个元素
        	return arr[top];
        }
        
        /**
         * 判断是否为空
         */
        public boolean isEmpty() {
        	return top == -1; // 为-1说明没有元素就为空
        }
        
        /**
         * 判断栈是否满了
         */
        public boolean isFull() {
        	return top == arr.length - 1;
        }
    }

Java的测试类

package stack;
     
    public class TestMyStack {
     
    	public static void main(String[] args) {
    		MyStack ms = new MyStack(4);
    		
    		ms.push(2);
    		ms.push(23);
    		ms.push(51);
    		ms.push(39);
            
    		System.out.println(ms.isEmpty());
    		System.out.println(ms.isFull());
    		
    		//弹栈两个元素
    		ms.pop();
    		ms.pop();
    		//查找当前top元素是多少
    		System.out.println(ms.peek());
    		System.out.println(ms.isFull());
    	}
    }

运行结果

false
    true
    23
    false

[20190604154437822.png]: /images/20220122/0271cf4ed720476280ee00873c6d141f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220122/45ff2af9c36d4899ab820b331fd874f5.png