栈的介绍

6 Z' Q1 j; F; Y$ r4 X

栈（stack），是一种线性存储结构，它有以下几个特点：

• 栈中数据是按照"后进先出（LIFO, Last In First Out）"方式进出栈的。
• 向栈中添加/删除数据时，只能从栈顶进行操作。
  
  

栈通常包括的三种操作：push、peek、pop。

• push——向栈中添加元素。
• peek——返回栈顶元素。
• pop——返回并删除栈顶元素的操作。
  
  ( i  ?* ?+ V1 [. g) u2 {$ Y7 w

1. 栈的示意图

$ s0 y+ k9 @' g9 A1 |+ o4 a0 v/ b

栈中的数据依次是30→20→10。

2 _0 k( T3 a$ @1 f

2. 出栈

- R! C: j# ]; \, ^# [! t

3 l* v- {! n% X# _0 Z) ]

出栈前：栈顶元素是30。此时，栈中的元素依次是30→20→10。

出栈后：30出栈之后，栈顶元素变成20。此时，栈中的元素依次是20→10。

; z! O3 w& c( c1 Q4 g$ E6 S

3. 入栈

8 u9 r; Z3 _+ B+ ]! b6 a

入栈前：栈顶元素是20。此时，栈中的元素依次是20→10。

5 F/ a- u0 z+ `2 ]4 E4 |! r: l

入栈后：40入栈之后，栈顶元素变成40。此时，栈中的元素依次是 40→20→10。

栈的C实现
2 ?' v/ I) M$ K5 p

1数组实现的栈，并且只能存储int数据

实现代码：

9 @8 \5 E; h/ V. N$ G

运行结果：

1. 
   & I8 A# d$ C! D; T, J! [
2. tmp=30
   ( Q) Z$ b% s& u4 P0 H4 b
3. tmp=20
   % i9 d$ W; s9 c2 l4 P/ |; c. b
4. stack size()=3
   
5. 40
   
6. 20
   2 T2 q0 z6 v0 O/ _
7. 10

复制代码

结果说明：该示例中的栈，是通过"数组"来实现的！
• 
  

由于代码中已经给出了详细了注释，这里就不再对函数进行说明了。仅对主函数main的逻辑进行简单介绍：

• 在主函数main中，先将 "10, 20, 30"依次压入栈。此时，栈的数据是：30→20→10。
• 接着通过pop()返回栈顶元素；pop()操作并不会改变栈中的数据。此时，栈的数据依然是：30→20→10。
• 接着通过peek()返回并删除栈顶元素。peek操作之后，栈的数据是：20→10。接着通过push(40)将40压
• 入栈中。push(40)操作之后，栈的数据是：40→20→10。
  
  ) ~$ y2 O* |7 j1 S. K7 w

2单向链表实现的栈，并且只能存储int数据

9 i% u/ j6 ~* W4 {8 x4 ?8 d

实现代码：

代码说明："运行结果" 以及 "主函数main的逻辑"都和"C语言实现一"的一样。不同的是，该示例中的栈是通过单向链表实现的。

3双向链表实现的栈，并且只能存储int数据

实现代码：

（1）双向链表的头文件(double_link.h)

. N" T. w$ _: Y% U. T# u# L# c( W

* L5 C! P6 J0 m9 {+ C, x4 Y7 h' r

（2）双向链表的实现文件double_link.c)

0 ~7 |1 j: w% e9 Q9 n9 }% V

, A( p- i# _; G' C2 T, r* L0 S& g

（3）双向链表的测试程序(dlink_stack.c)

; M  k) D7 |! t# p

代码说明："运行结果" 以及 "主函数main的逻辑"都和前两个示例的一样。不同的是，该示例中的栈是通过双向链表实现的。

5 }5 X5 `$ y" n* G1 S

4双向链表实现的栈，能存储任意类型的数据

实现代码：

% ^3 [9 U! @" x. U1 w% i

（1）双向链表的头文件(double_link.h)

: s0 ^$ z0 G2 V% B3 V* ?4 f. q" y

（2）双向链表的实现文件(double_link.c)

（3）双向链表的测试程序(dlink_stack.c)

运行结果：

1. 
   4 C6 U  N( V- w% [$ e% i
2. id=40, name=dan
   
3. id=20, name=jody
   
4. id=10, name=sky

复制代码

结果说明：该示例中的栈是通过双向链表实现的，并且能存储任意类型的数据。示例中是以结构体类型的数据进行演示的，由于代码中已经给出了详细的注释，这里就不再介绍了。

3 T+ }/ Y' |$ V# G