栈(stack)

是限定仅在表尾进行插入与删除的线性表,栈中允许插入和删除的一端叫做栈顶(top),另一端叫做栈底(bottom)。不含任何数据元素的栈称为空栈。栈中元素的个数称为栈的高度或长度。

将元素插入到栈的操作称为入栈(或进栈)操作,元素入栈后就变成新的栈顶。将元素从栈中删除的操作称为出栈(或退栈)操作,出栈时被删除的总是原来的栈顶元素。因此每次出栈的元素总是当前栈中“最新”的元素,即最后入栈的元素,而最先插入的元素被放到了栈底,待其他元素都已经出栈,栈底元素才能被删除。

栈的操作是按照先进先出(LIFO,Last In First Out)原则进行的。

定义

给出栈类的定义(基本方法一致):

const int StackSize = 1024;
template<class T>
class SeqStack {
    public:
        SeqStack() { top = -1; } // 构造函数
        void Push(T); // 压栈
        T Pop(); // 出栈
        T GetTop() ; // 获取栈顶元素
        bool Empty(); // 判断空栈
        int Size() { // 栈大小
            return top+1;
        }
    private:
        T data[StackSize];
        int top;
};

顺序栈

栈的顺序储存结构称作顺序栈,类似于顺序表,顺序栈也可以用数组来实现,由于栈底位置固定不变,因此可以将栈底设置在数组两端的任一端,通常把下标为0的一端作为栈底。同时设置top顶指针作为栈顶位置。当进行入栈操作时,top++,当出栈时,top–。当栈为空时,top=-1。设置数组大小为StackSize,当栈满时,top=StackSize-1。

下面是顺序栈程序:

/*************************************************************************
    > File Name: SeqStack.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Thu 23 Apr 2015 22:18:19 CST
 ************************************************************************/

#include<iostream>
using namespace std;

const int StackSize = 1024;
template<class T>
class SeqStack {
    public:
        SeqStack() { top = -1; }
        void Push(T);
        T Pop();
        T GetTop() ;
        bool Empty();
        int Size() {
            return top+1;
        }
    private:
        T data[StackSize];
        int top;
};

template<class T>
void SeqStack<T>::Push(T x) {
    if(++top >= StackSize) throw "上溢";
    data[top] = x;
}

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

template<class T>
T SeqStack<T>::Pop() {
    if(Empty()) throw "下溢";
    return data[top--];
}

template<class T>
T SeqStack<T>::GetTop() {
    if(Empty()) throw "下溢";
    return data[top];
}

int main() {
    SeqStack<int> stack;
    for(int i=1; i<=10; ++i)
        stack.Push(i);
    for(int i=1; i<=10; ++i) {
        cout << "stack顶元素:" << stack.GetTop() << " 大小:" << stack.Size() << endl;
        stack.Pop();
    }
    return 0;
}

链栈

栈的链式储存结构称为链栈,其实现原理类似于单链表,结点结构和单链表相同。由于插入和删除操作都在表头进行,因此链栈在实现时直接采用栈顶指针指向栈顶元素,无需像单链表一样增加表头结点。

下面给出链栈实现。

/*************************************************************************
    > File Name: LinkStack.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Thu 23 Apr 2015 22:51:37 CST
 ************************************************************************/

#include<iostream>
using namespace std;

template <class T>
struct Node {
    T data;
    Node * next;
};

template <class T>
class LinkStack {
    public:
        LinkStack() {top = NULL;}
        ~LinkStack();
        void Push(T x);
        T Pop();
        T GetTop() const;
        int Size() const;
        bool Empty() const{ return (NULL == top)?true:false;}
    private:
        struct Node<T> * top;
};

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

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

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

template<class T>
T LinkStack<T>::GetTop() const {
    if(Empty()) throw "下溢!";
    return top->data;
}

template<class T>
int LinkStack<T>::Size() const {
    Node<T> * p = top;
    int count=0;
    while(p) {
        ++count;
        p = p->next;
    }
    return count;
}

int main() {
    LinkStack<int> stack;
    for(int i=1; i<=10; ++i)
        stack.Push(i);
    for(int i=1; i<=10; ++i) {
        cout << "stack顶元素:" << stack.GetTop() << " 大小:" << stack.Size() << endl;
        stack.Pop();
    }
    return 0;
}

运行结果如下:

stack顶元素:10 大小:10
stack顶元素:9 大小:9
stack顶元素:8 大小:8
stack顶元素:7 大小:7
stack顶元素:6 大小:6
stack顶元素:5 大小:5
stack顶元素:4 大小:4
stack顶元素:3 大小:3
stack顶元素:2 大小:2
stack顶元素:1 大小:1