堆栈和队列

堆栈

基本概念

限定只能在固定一端进行插入或删除操作的线性表
特点：先进后出

允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。

堆栈抽象数据类型

数据集合：{a0,a1,……,an}ai的数据类型为Datatype

操作集合：

1. Initiate(S)初始化栈堆S
2. Push (S,x)入栈
3. Pop(S,d)出栈
4. GetTop(S)取栈顶数据元素
5. NotEmpty(S)堆栈S非空否

顺序堆栈类

顺序堆栈：顺序存储结构的堆栈
顺序栈的存储结构：它是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，结构如下表所示：

an:顺序堆栈中已存储的数据元素
stack: 存放数据元素的数组
MaxStackSize - 1:最大存储单元个数
top :栈顶指针，指向下一个存储位置（下标）

类的定义：

class SeqStack
{
private:
	DataType data[MaxStackSize];
    int top;
public:
    SeqStack(void){top = 0;}//构造函数
    ~SeqStack(void);//析构函数
    void Push(const DataType item);//入栈
    DataType Pop(void);//出栈
    DataType GetTop(void)const;//取栈顶数据元素
    int NotEmpty(void)const{return(top!=0);}//堆栈非空否，返回1表示非空
}

顺序栈类的操作实现

1. 入栈

   void SeqStack::Push(const DataType item)
   {
       if(top == MaxStackSize){
           cout << "堆栈已满" << endl;
           exit(0);
       }
       data[top] == item;
       top ++;
   }
   

2. 出栈

   DataType SeqStack::Pop()
   {
       if(top == 0){
           cout << "堆栈已空" << endl;
           exit(0);
       }
       top--
       return data[top];//返回被弹出的数据元素
   }
   

3. 取栈顶数据元素

   DataType SeqStack::GetTop(void)const
   {
       if(top == 0){
           cout << "堆栈已空" << endl;
           exit(0);
   	}
       return data[top - 1];
   }
   

4. 测试主程序

   #include<iostream>
   #include<stdlib>
   const int MaxStackSize = 100;
   typedef int DataType;
   
   void main(void)
   {
       SeqStack myStack;//构建函数无参数
       DataType test[] = {1, 3, 5, 7, 9};
       int n = 5;
       for(int i = 0; i < n; i++){
           myStack.Push(test[i]);
       }
       while(myStack.NotEmpty()){
           cout << myStack.Pop() << " ";
       }
       return 0;
   }
   
   //输出结构应为：9 7 5 3 1
   

链式堆栈类

链式堆栈：链式存储结构的堆栈
链式栈的存储结构：是以头指针为栈顶，在头指针处插入或删除

结点类定义和实现

template<claas T> class LinStack;//前视定义
template<class T>
class StackNode
{
friend class LinStack<T>
private:
    T data;//数据元素
    StackNode<T> *next;//指针
  
public:
    //构造函数1
    StackNode(StackNode<T> *ptrNext = NULL){
        next = ptrNext;
    }
    //构造函数2,默认指针为null
    StackNode(const T& item, StackNode<T> *ptrNext = NULL){
        data = item;
        next = ptrNext;
    }
     ~StackNode(){}
}

链式堆栈类的定义

template<class T>
class LinStack
{
private:
	StackNode<T> *head;//头指针
    int size;//数据元素个数
public:
    LinStack(void);
    ~LinStack(void);
    void Push(const T& item);
    T Pop(void);
    T GetTop(void) const;
    int NotEmpty(void) const;
}

链式栈类的操作实现

1. 构造函数

   LinStack<T>::LinStack()
   {
   	head = new StackNode<T>;//头指针指向头节点
   	size = 0;//size初始值为0
   }
   

2. 析构函数

   LinStack<T>::~LinStack(void)
   {
   	StackNode<T> *p, *q;
   	p = head;//p指向头节点
   
   	while(p != NULL){
   		q = p;
   		p = p->next;
   		delete q;
   	}
   }
   

3. 堆栈非空否

   int LinStack <T>::NotEmpty(void) const
   {
       if(size != 0) return 1;
       else return 0;
   }
   

4. 入栈

   void LinStack<T>::Push(const T& item)
   {
       //新结点newNode的data值域为item,next值域为head->next
       StackNode<T> *newNode = new StackNode<T>(item, head->next);
       head->next = newNode;//新结点插入栈顶
       size++;//元素个数+1
   }
   

5. 出栈

   T LinStack<T>::Pop(void)
   {
       if(size == 0)
       {
           cout << "堆栈已空！" << endl;
           exit(0);
       }
       StackNode<T> *p = head->next;//p指向栈顶元素结点
       T data = p->data;
       head->next = head->next->next;//原栈顶元素结点脱链
   
       delete p;
       size--;
       return data;
   }
   

6. 取栈顶元素

   T LinStack<T>::GetTop(void) const;//取栈顶元素
   {
       return head->next->data;
   }