[数据结构笔记] 栈

一、栈的逻辑结构

栈：限定仅在表尾进行插入和删除操作的线性表。

空栈：不含任何数据元素的栈。

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

示意图：

二、顺序栈的存储结构及实现

其中top为顺序栈栈顶指针。

进栈操作：top++;

出栈操作：top--;

判断栈空：top==-1;

栈满：top==MAXSIZE-1;

 

顺序栈：

const int MAX_SIZE=100; template <class T> class seqStack { public: seqStack ( ) ; ~seqStack ( ); void Push ( T x ); T Pop ( ); T GetTop ( ); bool Empty ( ); private: T data[MAX_SIZE]; int top; } 入栈    void Push(T x) template <class T> void seqStack<T>::Push ( T x) { if (top==MAX_SIZE-1) throw “溢出”; top++; data[top]=x; } 时间复杂度为O(1)

判断栈空    bool Empty()

template <class T> bool seqStack<T>::Empty () { if (top==-1) return true; return false; }

时间复杂度O(1)

取栈顶    T GetTop()

template <class T> T seqStack<T>::GetTop ( ) { if (Empty()) throw ”空栈” ； return data[top]; }

时间复杂度O(1)

出栈    T pop()

template <class T> T seqStack<T>:: Pop ( ) { if (top==-1) throw “溢出”; x=data[top]; top--; return x; }

时间复杂度O(1)

链栈：栈的链式存储

链栈的类声明：

template <class T> class LinkStack { public: LinkStack( ) {top=NULL;}; ~LinkStack( ); void Push(T x); T Pop( ); T GetTop( ); bool Empty( ); private: Node<T> *top; }

1.入栈

template <class T> void LinkStack<T>::Push(T x) { s=new Node<T>; s->data=x; s->next=top; top=s; }

2.出栈

template <class T> T LinkStack<T>::Pop( ) { if (top==NULL) throw "下溢"; x=top->data; p=top; top=top->next; delete p; return x; }

3.链栈的析构

template <class T> LinkStack<T>::~LinkStack( ){ while (top){ Node<T> *p; p=top->next; delete top; top=p; } }