栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
进栈也叫入栈或压栈,也就是将元素放入到栈这个数据结构中去。
出栈也叫退栈或者叫弹栈,也就是将栈定元素从栈中删除。
栈特点就是一个先进后出的结构。
栈的概念是弹压,就像子弹壳装弹,一粒一粒压进去,但是打出来的时候是从上面打出来的,最先压进去的最后弹出来,如果进去顺序是 A、B、C,打出来顺序是 C、B、A,这就是后进先出。
队列(Queue)是限定只能在表的一端进行插入和在另一端进行删除操作的线性表;栈(Stack)是限定只能在表的一端进行插入和删除操作的线性表。
栈的结构如下图所示:
我们看到,栈的结构最上面的一个元素叫栈顶,最下面的叫栈底,入栈和出栈操作只能在栈顶进行操作,而不能在栈底进行操作。
栈的结构定义如下:
typedef struct Node{
int data;
struct Node *pNext;
}NODE, *PNODE;
typedef struct Stack{
PNODE pTop;
PNODE pBottom;
}STACK, PSTACK;
我们在定义栈结构之前,首先定义了一个 Node 结点,其结构是一个链表的结构,保存了结点元素的值和下一个元素的指针。
栈结构的定义其实就是一个包含栈顶 pTop 和栈底 pBottom 的元素的结构。