Stack

Posted on Edited on Views:

栈(stack)

1栈是一个先入后出(FILO-First In Last Out)的有序列表。

2栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

3.根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

1
2
3
4
5
6
           ───────────────────────────────┐
  (\(\       (\(\    (\(\    (\(\    (\(\ │
 (='.') <─> (='.')  (='.')  (='.')  (='.')│
O(_")")    O(_")") O(_")") O(_")") O(_")")│
           ───────────────────────────────┘
           stack

和队列区别开

1
2
3
4
5
6
          ────────────────────────
  (\(\      (\(\    (\(\    (\(\      (\(\
 (='.') ─> (='.')  (='.')  (='.') ─> (='.')
O(_")")   O(_")") O(_")") O(_")")   O(_")")
          ────────────────────────
           Queue
栈的结构
1
2
3
4
5
6
7
8
 ───────────────────────────────┐
   (\(\    (\(\    (\(\    (\(\ │
  (='.')  (='.')  (='.')  (='.')│
 O(_")") O(_")") O(_")") O(_")")│
 ───────────────────────────────┘
   ↑                        ↑
 Top栈顶                 Bottom栈底
初始化为-1
入栈
1
2
3
4
5
6
7
8
           ───────────────────────────────┐
  (\(\               (\(\    (\(\    (\(\ │
 (='.')  ─>         (='.')  (='.')  (='.')│
O(_")")            O(_")") O(_")") O(_")")│
  data     ───────────────────────────────┘
           push入栈
           top++;
           stack[top]=data
出栈
1
2
3
4
5
6
7
8
9
       ───────────────────────────────┐
     (\(\        (\(\    (\(\    (\(\ │
<─  (='.')      (='.')  (='.')  (='.')│
   O(_")")     O(_")") O(_")") O(_")")│
       ───────────────────────────────┘
       pop出栈
      int value = stack[top];
      top--;
      return value;