文章目录

• • 栈
  • • 1.定义：
    • 2.用数组模拟栈
    • • 2.1思路
      • 2.2代码实现
    • 3.用链表模拟栈
    • • 3.1思路
      • 3.2代码实现

栈

1.定义：

• 栈是一个先入后出（FILO-First In Last Out）的有序列表
• 栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。
• 允许插入和删除的一端为变化的一端，称之为栈顶，另一端为固定的一端，称之为栈底。
• 根据栈的定义可知，最后放入栈中的元素在栈底，最后放入的在栈顶。而删除元素恰好相反，最后放入的元素最先删除，最先放入的元素最后删除。

2.用数组模拟栈

2.1思路

• 定义一个数组stack[ ]来存储数据
• 定义一个变量top来表示栈顶
• 入栈：当有数据data加入栈时 stack[top++] = data
• 出栈：返回stack[top–] 数据
• 

2.2代码实现

/**
 * 用数组模拟栈
 */
class ArrayStack
{
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }

    public int getMaxSize() {
        return maxSize;
    }

    public boolean isFull()
    {
        return top == maxSize - 1;
    }

    public boolean isEmpty()
    {
        return top == -1;
    }

    /**
 	 * 从栈顶添加数据
     */
    public void push(int value)
    {
        if (isFull())
        {
            throw new RuntimeException("栈满无法添加数据....");
        }
        top++;
        stack[top] = value;
    }

    /**
 	 * 从栈顶弹出数据
     */
    public int pop()
    {
        if (isEmpty())
        {
            throw new RuntimeException("栈空无法返回数据....");
        }
        return stack[top--];
    }

    /**
     * 从栈顶开始展示数据
     */
    public void list()
    {
        if (isEmpty())
        {
            System.out.println("栈空无法展示数据....");
            return;
        }
        //从数组末开始输出数据
        for (int i = top;i >= 0; i--)
        {
            System.out.printf("stack[%d] = %d\n",i,stack[i]);
        }
    }
}

3.用链表模拟栈

3.1思路

• 创建一个带头节点的双向链表
• 链表尾部表示栈顶
• 入栈：从链表头添加节点
• 出栈：返回链表头的节点

3.2代码实现

• 存储数据的节点

  class DataNode
  {
      //存储数据
      public int data;
      public DataNode next;
      public DataNode pre;
  }
  

• 用于模拟栈的双向链表

  class LinkedListStack
  {
      /**
       * 初始化双向链表的头节点,不存储任何数据
       */
      private DataNode headNode = new DataNode(-1);
  
      /**
       * 当前链表模拟的栈中存储数据的数量
       */
      private static int size = 0;
  
      /**
       * 在链表头添加数据模拟数据入栈
       * @param num 添加的数据
       */
      public void push(int num)
      {
          //定义一个辅助指针指向头节点的下一个节点
          DataNode temp = headNode.getNext();
          //将要添加的数据封装成节点
          DataNode dataNode = new DataNode(num);
          //头节点指向新的节点
          headNode.setNext(dataNode);
          //新节点pre域指向头节点
          dataNode.setPre(headNode);
          //防止出现空指针
         	//新的节点与temp指向的节点建立双向逻辑关系
          if (temp != null)
          {
              temp.setPre(dataNode);
          }
          dataNode.setNext(temp);
          size++;
      }
  
      /**
       *  从表头取出数据模拟出栈
       * @return 
       * @throws Exception
       */
      public int pop() throws Exception
      {
          if (isEmpty())
          {
              throw new Exception("栈空无法返回数据....");
          }
          //next不为空
          DataNode next = headNode.getNext();
          DataNode temp = next.next;
          int data = next.getData();
          headNode.setNext(temp);
          if(temp != null)
          {
              temp.pre = headNode;
          }
          size--;
          return data;
      }
  
      public void list() throws Exception {
          if (isEmpty())
          {
              throw new Exception("栈空无法展示数据....");
          }
          DataNode temp = headNode.next;
          int index = size - 1;
          while (true)
          {
              if (temp == null)
              {
                  break;
              }
              System.out.printf("stack[%d] = %d\n",index--,temp.getData());
              temp = temp.getNext();
          }
      }
  
      public boolean isEmpty()
      {
          return headNode.getNext() == null;
      }
  }
  
  
  

如有错误或不足欢迎评论指正。