数据结构与算法学习之（四）：栈与队列（上）

栈是一种运用广泛的特殊线性表，在网页的后退操作，Word等界面的撤销操作都用到了栈的结构。

其定义如下：

栈是一个 后进先出（Last In First Out, LIFO）的线性表，只要求在表尾进行删除和插入操作。并把表尾称作栈顶（top），对应高地址；表头称作栈底（bottom），对应低地址。

栈的插入操作（push）叫做进栈，类似于压子弹入弹夹。

栈的删除操作（pop），叫做出栈，类似于从弹夹中取出子弹。整体结构如下图。

1.栈的顺序存储结构

程序设计中，栈的应用一般以数组的形式表现出来，由于插入和删除均在数组的末尾， 时间复杂度不高。因此重点了解顺序存储结构。栈的基本运算有三种：出栈、入栈和读取操作，用一个类来实现整体操作。基本类的定义与构造函数如下。

class sq_stack
{
private:
       int mm;        //容量
       int top;      //栈顶指针
       T* s;         //存储空间首地址
public:
       sq_stack(int);
       void ins_stack(T);
       T del_stack();
       void prt_stack();
};
template <class T>
sq_stack<T>::sq_stack(int m) 
{  mm=m;          //存储空间容量
   s=new T[mm];   //动态申请存储空间
  top=0;          //栈顶指针为0，即建立空栈
  return;
}

1.1入栈

入栈算法分为以下三步：

判断栈顶指针是否指向存储空间的最后一个位置，若是，则产生“上溢”错误。
新元素插入栈顶指针的位置。
栈顶指针加一。

类的基础定义以及入栈的代码实现如下：

template<class T>
void sq_stack<T>::ins_stack(T x)
{
       if(top==mm)
       {cout<<"overflow"<<endl;return;}
       s[top]=x;
       top=top+1;
       return;
}

1.2出栈

出栈算法分为以下三步：

判断栈顶指针是否为0（指向表头），若是，则产生“下溢错误”。
栈顶指针的位置插入新元素。
栈顶指针减一。

代码实现如下：

template<class T>
T sq_stack<T>::del_stack()
{
       T y;
       if(top ==0)
       {cout<<"underflow"<<endl;return 0;}
       y=s[top];
       top-=1;
       return y;
}

1.3读取

读取元素的操作较简单，判断栈顶指针是否为0，不是的话循环遍历输出即可。代码如下。

template<class T>
void sq_stack<T>::prt_stack()
{
       if(top==0)
       {cout<<"error"<<endl;return;}
       int i;
       for(i=top-1;i>=0;i--)
              cout<<s[i]<<endl;
       return;
}

2.栈的链式存储结构

实际应用中，带链的栈可以用来搜集所有空闲存储结点中的数据。关于它的具体操作，也用一个类作为示例。类的基本代码和构造函数如下。

template <class T>
struct node
{
       T d;    //数据域
       node *next;    //指针域
};
template<class T>
class linked_Stack
{
private:
       node<T> * top;    //栈顶指针
public:
       linked_Stack();
       void ins_linked_Stack(T);    //插入
       T del_linked_Stack();    //删除
       void prt_linked_Stack();    //输出
};
template<class T>
linked_Stack<T>::linked_Stack()
{
       top=NULL;
       return;
}

2.1入栈操作

入栈操作的算法流程和代码实现如下。

void linked_Stack<T>::ins_linked_Stack(T x)
{
       node<T> *p=new node<T>;    //申请新结点
       p->d=x;        //数据存入p的数据域
       p->next=top;    //指针域指向原先top的位置，如上图
        top=p;       //栈顶指针top指向新结点p
       return;    
}

2.2出栈操作

出栈操作需要借助一个临时指针保存数据与地址，待栈顶指针更新完后释放临时指针，代码如下。

template<class T>
T linked_Stack<T>::del_linked_Stack()
{
       T y;
       if(top==NULL){cout<<"empty stack!"<<endl;return 0;}
       node<T> *q=new node<T>;
       q=top; //指针q指向栈顶
       y=q->d;       //去除栈顶元素
       top=q->next;  //栈顶指针top指向下一个结点
       delete q;     //释放结点空间
       return y;
}

2.3查询操作

查询操作较为简单。判断栈非空后即可输出，代码如下。

template<class T>
void linked_Stack<T>::prt_linked_Stack()
{
       if(top==NULL){cout<<"empty stack!"<<endl;return;}
       node<T>*r=new node<T>;
       r=top; 
       while(r!=NULL)       //r从top开始遍历并输出
       {
              cout<<r->d<<endl;
              r=r->next;
       }
        return;
}

秒客网

数据结构与算法学习之（四）：栈与队列（上）

相关文章