栈和队列

栈和队列都是通过动态集合来存储数据，在栈和队列中添加和删除数据都是预先设定的。

在栈（Stack）中，被删除的元素是最近添加的元素，所以栈的实现方式是后进先出（Last-in， First-out）；

在队列中，被删除的元素是最开始添加的的元素，也就是在动态集合中存放时间最长的那个元素，所以队列的实现方式是先进先出（First-in，First-out）。

栈

在栈的数据结构中，添加元素的操作被称之为入栈（PUSH），删除元素的操作被称之为出栈，也可以称为弹出（POP）。如果栈中不存在任何一个元素，那么这个栈被称为空栈。

链栈Code：

#include<bits/stdc++.h>
struct Node
{
    int data;
    Node *next;
};

template<class T>
class LinkStack
{
public:
    LinkStack()
    {
        top=NULL;
    }
    ~LinkStack();
    void Push(T x);
    T Pop();
    T GetTop()
    {
        if(top!=NULL)
            return top->data;
    }
    int Empty()
    {
        if(top==NULL)
            return 1;
        else
            return 0;
    }
private:
    Node *top;
};

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

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

队列

在队列中，添加元素的操作被称之为入队（enqueue），而删除元素的操作被称之为出队（dequeue）。在队列中，会有队头（head）和队尾（tail）。当一个元素入队时，该元素就被放入到队尾的位置，而出队的元素就是队头的元素。

队列Code：

struct Node
{
    int n;
    Node *next;
};
class linsta
{
    Node *first,*last;
public:
    linsta();
    void pushd(int x);
    void popd();
    void print()
    {
        for(Node *i=first->next; i; i=i->next)
        {
            cout<<i->n<<' ';
        }
        cout<<endl;
    }
};
linsta::linsta()
{
    first=new Node;
    first->next=NULL;
    last=first;
}
void linsta::pushd(int x)
{
    Node *s=new Node;
    s->n=x;
    last->next=s;
    last=s;
    last->next=NULL;
}
void linsta::popd()
{
    Node *j;
    if(first->next!=NULL)
    {
        j=first->next;
        first->next=j->next;
        delete j;
    }
}