栈的基本操作

曾经终败给现在 2023-09-23 16:14 166阅读 0赞

**目录**

一、什么是栈？

二、用单链表实现栈

三、用顺序表数组实现栈

--------------------

## 一、什么是栈？ ##

**·**栈（stack）是一个先进后出（FILO-First In Last Out）的有序列表。

**·**主要方法：入栈（push）、出栈（pop）

**·**允许插入和删除的一端为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）。

**·**先放入到栈的元素在栈底，后放入栈的元素为栈顶。栈顶的元素先出，栈底的元素后出。

![a3a1988f6eeb463dbf8ef4d1d2ff4a65.png][]

**·栈的应用场景：**（1）递归问题的处理（2）表达式的转换，例如括号、计算器。（3）二叉树的遍历（4）图的深度优先遍历

## 二、用单链表实现栈 ##

>     思路：用链表的方式实现栈
>     将插入的结点插入到第一个结点位置，如果插入到链表的尾部的话，虽然插入尾部可以后进先出，但每次拿到元素都要遍历到链表的尾部，效率太低了，所以将结点插入到链表头部，每次从链表头部获取结点，达到后进先出的效果。

### 代码实现： ###

package Stack;
    
    public class MyLinkedStack<T> {
    
        //定义链表结点
        public class Node{
            T item;//存储数据
            Node next;
            public Node(T item, Node node) {
                this.item = item;
                this.next = node;
            }
        }
    
        //定义头结点
        Node head;
        //定义栈的长度
        int size;
        //初始化头结点、栈的长度
    
        public MyLinkedStack() {
            head = new Node(null,null);
            size = 0;
        }
    
        //定义入栈方法
        //思路：用链表的方式实现栈
        //     将插入的结点插入到第一个结点位置，如果插入到链表的尾部的话，
        //     虽然插入尾部可以后进先出，但每次拿到元素都要遍历到链表的尾部，
        //     效率太低了，所以将结点插入到链表头部，每次从链表头部获取结点，达到后进先出的效果。
        public void push(T t){
            //获取第一个结点
            Node first = this.head.next;
            //创建插入的结点
            Node node = new Node(t,null);
            //将需要插入的结点指针指向第一个结点
            node.next = first;
            //将头结点指针指向插入的结点
            this.head.next = node;
            //链表的长度加一
            this.size++;
        }
    
        //定义出栈方法
        public T pop(){
            //获取第一个结点
            Node first = this.head.next;
            //获取第二个节点
            Node second = first.next;
            //取出第一个结点，将头结点指向第二个节点
            this.head.next = second;
            //链表的长度减一
            this.size--;
            //return获取结点
            return first.item;
        }
    }

## 三、用顺序表数组实现栈 ##

> 这里讲一下思路即可，代码实现先不贴上去哈。
> 
> 思路：数组实现的原理很简单，每次插入元素都放在数组的尾部，每次获取元素也从数组尾部获取即可。

[a3a1988f6eeb463dbf8ef4d1d2ff4a65.png]: https://img-blog.csdnimg.cn/a3a1988f6eeb463dbf8ef4d1d2ff4a65.png