数据结构（栈）_数据结构栈

目录

栈的定义

 形象比喻

栈的相关术语 

 栈的抽象数据类型（栈Stack的ADT）

顺序栈 

顺序栈类的声明

 顺序栈类成员函数的实现

基本效率分析

顺序栈的应用（小测试）

 main.cpp

共享栈

双共享栈 

链式栈 

 链式栈基本操作分析

链式栈类的声明

链式栈基本操作的实现

小结

---

栈的定义

如果元素到达线性结构的时间越晚，离开的时间就越早，这种线性结构称为栈（Stack）或堆栈；

因为元素之间的关系是由到达、离开的时间决定的，因此栈通常被称为时间有序表。

而到达和离开的含义就是插入和删除操作，因此栈可以看作是插入和删除操作位置受限的线性表。

 形象比喻

 乒乓球盒的进球和出球，它遵循了最后进盒的球反而最先出盒，即所谓的后进先出(LIFO, Last In First Out)或先进后出(FILO, First In Last Out)结构。

 

栈的相关术语 

栈的首部(元素最早到达的部分)称为栈底(bottom) ，栈结构的尾部(元素最晚到达的部分)称为栈顶（top） 。

为了保证栈的先进后出或后进先出的特点，元素的插入和删除操作都必须在栈顶进行。元素从栈顶删除的行为，称为出栈或者弹栈操作（pop）; 元素在栈顶位置插入的行为，称为进栈或者压栈操作（push）。

读取栈顶元素数据值的操作，称为取栈顶内容操作(top)。

当栈中元素个数为零时，称为空栈。

 栈的抽象数据类型（栈Stack的ADT）

Data: { xi | xiÎ ElemSet, i=1,2,3,……n, n > 0} 或 Φ; ElemSet为元素集合。

Relation: {<xi,xi+1>|xi,xi+1ÎElemSet, i=1,2,3,……n-1}, x1为栈底，xn为栈顶。

Operations:

顺序栈 

 栈的顺序存储即使用连续的空间存储栈中的元素。可以将栈底放在数组的0下标位置，进栈和出栈总是在栈的同一端（栈顶）进行，顺序方式存储的栈称为顺序栈。

 

栈空标志：top=-1

栈满标志：top=maxSize-1

bottom对应的永远是0，而top对应的是可变的。

顺序栈类的声明

 顺序栈的描述：数组指针array，数组大小maxSize，栈顶下标Top。

class illegalSize{};
class outOfBound{};
 
template <class elemType>
class seqStack
{  private:
        elemType *array;    //栈存储数组，存放实际的数据元素。
        int Top;            //栈顶下标。
        int maxSize;	    //栈中最多能存放的元素个数。
        void doubleSpace();
 public:
        seqStack(int initSize = 100); //初始化顺序栈
        bool isEmpty () { return ( Top == -1 ); } ; //栈空返回true,否则返回false。
        bool isFull () { return (Top == maxSize-1); };//栈满返回true,否则返回false。
        elemType top ();// 返回栈顶元素的值，不改变栈顶
        void push (const elemType &e );//将元素e压入栈顶，使其成为新的栈顶。
        void pop (); //将栈顶元素弹栈。
        ~seqStack(){ delete []array;}; //释放栈占用的动态数组
};

 顺序栈类成员函数的实现

template <class elemType>
seqStack<elemType>::seqStack(int initSize)//初始化顺序栈
{	array = new elemType[initSize];
	if (!array) throw illegalSize();
	Top=-1;    maxSize=initSize;
}
 
template <class elemType>
elemType seqStack<elemType>::top ()// 返回栈顶元素的值，不改变栈顶
{   if (isEmpty()) throw outOfBound();
    return array[Top];
}
template <class elemType>
void seqStack<elemType>::push(const elemType &e )
//将元素e压入栈顶，使其成为新的栈顶元素。
{     if  (isFull()) doubleSpace();
      //栈满时从新分配2倍的空间，并将原空间内容拷入
     array[++Top] = e;      	// 新结点放入新的栈顶位置。
}
template <class elemType>
void seqStack<elemType>::pop()//将栈顶元素弹栈。
{   if (Top==-1) throw outOfBound();
    Top--;
}

基本效率分析

函数initialize(seqStack)、isEmpty、isFull、top、pop、destroy（~seqStack）的时间复杂度均为O(1)。

push因某时可能扩大空间，造成O(n)时间消耗，但按照“分期付款式”法，分摊到单次的插入操作，时间复杂度仍为O(1)。

顺序栈的应用（小测试）

编写程序从键盘上依次输入一串字符（以回车键结束）。要求将该串字符按照输入顺序的逆序在屏幕上输出。

在程序中可以建立一个顺序栈，将输入的字符依次入栈，最后再依次出栈，便能得到逆序结果。 

 main.cpp

#include <iostream>
#include "seqStack.h"
using namespace std;
 int main()
{    // 声明一个栈。
     seqStack<char> s;
     char ctemp;
     //从键盘输入若干字符（结束用回车），
     //依照输入次序分别进栈
     cout<<"Input the elements，" <<press enter to an end: ";
     ctemp = cin.get(); 
     while ( ctemp!='\n')
     { 	s.push(ctemp);  ctemp = cin.get();   }
          //将栈中的结点逐个出栈，并输出到屏幕上。
	 cout<<"output the elements in the stack one by one:";
	 while (!s.isEmpty()) 
     {
		ctemp = s.top();
        s.pop();
		cout<<ctemp;
     } 	
          cout<<endl;
	return 0;  
}

共享栈

在实际应用中，有时需要同时使用多个数据类型相同的栈。

栈中的元素个数因进栈、出栈操作动态地变化，所有栈不一定同时达到栈满，有时一些栈满而另一些栈尚余空间。

为了提高空间使用率，可以在同一块连续的空间中设置多个栈。

多个栈间共享空间，这些栈称为“共享栈”。

共享栈的特点是每个栈拥有一个连续的小空间, 所有共享栈拥有一个大的连续空间。

 

 top指向实际栈顶的后一个位置

假设有m个栈，第i个栈空的条件：top[i]=bottom[i]；

第i个栈栈满条件为:    当i<m-1时，top[i]=bottom[i+1]；

                                   当i=m-1时，top[i]=maxSize。

双共享栈 

 可以将两个栈相向设置，即两个栈的栈底分别设置在连续空间的两个端点。

栈空的条件top[i]=bottom[i], i=0或1，两个栈不一定同时为空；

栈满的条件top[0]=top[1]，即两个栈当中只剩下一个空位置的时候栈满，两个栈必定同时栈满。

链式栈 

 用不连续的空间和附加指针来存储元素及元素间的关系。

栈顶指针top指向处于栈顶的结点，即单链表中的首结点。

 

 链式栈基本操作分析

进栈操作push的实现，按照以下操作顺序：

1）申请新的结点空间，data字段为进栈元素值，next字段指向首结点。

2）栈顶指向新结点。

出栈操作pop的实现，按照以下操作顺序：

1)   记住栈顶结点的地址。

2）将原栈顶的直接后继设为新的栈顶。

3）释放原来栈顶结点空间。

链式栈类的声明

class outOfBound{};
template <class elemType>
class linkStack;
template <class elemType>
class Node
{  friend class linkStack<elemType>;
    private:
        elemType data;
        Node *next;
    public:
        Node(){next = NULL;}
        Node(const elemType &x, Node *p=NULL)
        { data = x; next = p; }
};
template <class elemType>
class linkStack
{
    private:
        Node<elemType> *Top;
    public:
        linkStack(){ Top = NULL; }; //初始化栈，使其为空栈
        bool isEmpty(){ return (Top==NULL); }; //栈为空返回true,否则返回false。
        bool isFull(){ return false; }; //栈满true，否则false。结点空间不连续，故总能满足
        elemType top();
        void push(const elemType &e);
        void pop();
        ~linkStack();
};

链式栈基本操作的实现

template <class elemType>
elemType linkStack<elemType>::top()
{
    if (!Top) throw outOfBound();//栈空
    return Top->data;
}
 
template <class elemType>
void linkStack<elemType>::push(const elemType &e)
{  Top = new Node<elemType>(e, Top);  }
template <class elemType>
void linkStack<elemType>::pop()
{
    Node<elemType> *tmp;
    if (!Top) throw outOfBound();//栈空
 
    tmp = Top; //用tmp记住原栈顶结点空间，用于弹栈后的空间释放
    Top = Top->next; //实际将栈顶结点弹出栈
 
    delete tmp;//释放原栈顶结点空间
}
template <class elemType>
linkStack<elemType>::~linkStack()
{
    Node<elemType> *tmp;
    while (Top)
    {
        tmp = Top;
        Top=Top->next;
        delete tmp;
    }
}

小结