什么是栈

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈概念

进栈

进栈也叫入栈或压栈,也就是将元素放入到栈这个数据结构中去。

出栈

出栈也叫退栈或者叫弹栈,也就是将栈定元素从栈中删除。

栈特点

栈特点就是一个先进后出的结构。

栈的概念是弹压,就像子弹壳装弹,一粒一粒压进去,但是打出来的时候是从上面打出来的,最先压进去的最后弹出来,如果进去顺序是 A、B、C,打出来顺序是 C、B、A,这就是后进先出。

栈与队列区别

概念

队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表;栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。

规则不同

  1. 队列:先进先出(First In First Out)FIFO。
  2. 栈:先进后出(First In Last Out )FILO。

操作限定不同

  1. 队列:只能在表的一端进行插入,并在表的另一端进行删除。
  2. 栈:只能在表的一端插入和删除。

遍历数据速度不同

  1. 队列:基于地址指针进行遍历,而且可以从头部或者尾部进行遍历,但不能同时遍历,无需开辟空间,因为在遍历的过程中不影响数据结构,所以遍历速度要快;
  2. 栈:只能从顶部取数据,也就是说最先进入栈底的,需要遍历整个栈才能取出来,而且在遍历数据的同时需要为数据开辟临时空间,保持数据在遍历前的一致性。

图解栈

栈的结构如下图所示:

01_栈详解.png

我们看到,栈的结构最上面的一个元素叫栈顶,最下面的叫栈底,入栈和出栈操作只能在栈顶进行操作,而不能在栈底进行操作。

栈结构

栈的结构定义如下:

typedef struct Node{ int data; struct Node *pNext; }NODE, *PNODE; typedef struct Stack{ PNODE pTop; PNODE pBottom; }STACK, PSTACK;

我们在定义栈结构之前,首先定义了一个 Node 结点,其结构是一个链表的结构,保存了结点元素的值和下一个元素的指针。

栈结构的定义其实就是一个包含栈顶 pTop 和栈底 pBottom 的元素的结构。