栈是一种线性的逻辑结构，是一种稍加限制的只能在一端进行插入或删除操作的线性表。栈由栈顶和栈底组成，其栈顶进行插入和删除操作。

栈具有后进先出的特点，比如在生活中，我们用浏览器上网时一连窜点击了好几个链接，这个时候想回到前一页，点击后退按钮就能实现了，这就运用了栈的特点。

栈按存储结构（物理结构）分为：顺序栈和链式栈，其对应的是顺序表和链表。

下面是顺序栈的进栈和出栈算法实现及图解。

一、顺序栈进栈（push）图解

二、顺序栈进栈（push）算法

int push(SqStack &st,int x)
{
	if(st.top==maxsize-1)
	return 0;
	++(st.top);//先移动指针，再进栈
	st.data[st.top]=x;
	return 1;
}

三、顺序栈出栈（pop）图解

四、顺序栈出栈（pop）算法

int pop(SqStack &st,int &x)
{
	if(st.top==-1)
	return 0;
	x=st.data[st.top];//先取出元素，再移动指针
	- -(st.top);
	return 1;
}

注：以上代码用到了自增和自减运算符，++top和- -top这两个运算的效率要比对应的top++和top- -高。++top是自增1后再进行赋值运算，top++是赋值运算后，再自增1，其它两个同理。

Tags：pushd popd