数据结构与算法——队列的实现（链表实现和两个栈实现）-蒲公英云

数据结构与算法——队列的实现（链表实现和两个栈实现）

队列（queue）是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。
允许插入的一端称为队尾（rear）,允许删除的是队头（front）
在这里插入图片描述
//链表实现队列
//（1）添加的时候就添加链表的最后
//（2）弹出的时候就弹出头指针后一个位置的元素
//两个栈实现队列
//s2为空,先将s1全部装入s2再弹出

//链表实现队列

#include <iostream>
using namespace std;
typedef struct Node
{ 
    Node *next;
    int data;
}Node;
static Node *pHead = NULL;//头指针不包含数据
Node * creat_node(int elem)
{ 
    Node *p = (Node *)malloc(sizeof(Node));
    if (p == NULL)
    {     
        return NULL;
    }
    p->next = NULL;
    p->data = elem;
    return p;
}
void push(int elem)
{ 
    if (pHead == NULL)
    { 
        return;
    }    
    Node *p = creat_node(elem);
    //zy 找到尾部
    Node *q = pHead;
    while (q->next != NULL)
    { 
        q = q->next;
    }
    q->next = p;
    p = NULL;
    q = NULL;
}
int front()
{ 
    if (pHead->next == NULL)
    { 
        return 0;
    }
    return pHead->next->data;
}
void pop()
{ 
    if (pHead->next == NULL)
    { 
        return;
    }
    Node *p = pHead->next;
    pHead->next = p->next;
    free(p);
    p = NULL;
}
int isEmpty()
{ 
    if (pHead == NULL || pHead->next == NULL)
    { 
        return true;
    }
    else
    { 
        return false;
    }
}
int main()
{ 
    //创建无数据的头结点
    pHead = (Node *)malloc(sizeof(Node));
    if (pHead == NULL)
        return NULL;
    pHead->next = NULL;
    push(10);
    push(20);
    push(30);
    pop();
    push(40);
    while (!isEmpty())
    { 
        cout << front() << " ";
        pop();
    }
    cout << endl;
    return 0;
}

//两个栈实现队列

#include <iostream>
#include <stack>
using namespace std;
stack<int> s1,s2;
int length = 0;
void push(int elem)
{ 
    s1.push(elem);
    length ++;
}
int pop()
{ 
    if(s2.empty()) //s2为空,先将s1全部装入s2再弹出
    { 
        while (!s1.empty())
        { 
            s2.push(s1.top());
            s1.pop();
        }
    }
    int temp = s2.top();
    s2.pop();
    --length;
    return temp;
}
int main()
{ 
    push(10);
    push(20);
    push(30);
    pop(); pop();
    push(40);
    push(50);
    while (length)
    { 
        cout << pop()  << " ";
    }
    cout << endl;
    return 0;
}