栈和队列

作者: 往sir_b2a2 | 来源:发表于2020-08-05 19:19 被阅读0次

数据结构——栈和队列
栈和队列
Algorithm小白入门 -- 队列和栈
栈和队列
Python实现栈和队列以及使用list模拟栈和队列
算法-栈和队列算法总结
算法分析 [BFS、Greedy贪心] 2019-02-18
实验四栈和队列
栈、队列和链表
算法导论基本数据结构

顺序栈的基本操作：

#include<iostream>
using namespace std;
#define maxsize 100
typedef struct
{
    int* base;//栈底指针
    int* top;//栈顶指针
    int stacksize;//栈可用最大容量
}SqStack;
void Init(SqStack& S)//构造一个空栈
{
    S.base = (int*)malloc(maxsize * sizeof(int));
    if (!S.base)//存储分配失败
        return;
    else
    {
        S.top = S.base;//栈顶指针等于栈底指针
        S.stacksize = maxsize;
    }
}
bool IsEmpty(SqStack S)
{
    if (S.top == S.base)
        return true;
    else
        return false;
}
int GetLength(SqStack S)//求顺序栈长度
{
    return S.top - S.base;
}
void Clear(SqStack &S)//清空顺序栈...多+&
{
    if (S.base)
        S.top = S.base;
}
void Destroy(SqStack& S)//销毁顺序表
{
    if (S.base)
    {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
}
void Push(SqStack& S, int e)//压栈，推入
{
    if (S.top - S.base == S.stacksize)//栈满，上溢
        return;
    else
    {
        *S.top++ = e;/*即为
                     *S.top=e;  元素e压入栈顶
                     S.top++;   栈顶指针加1
                     */
    }
}
void Pop(SqStack& S, int& e)//出栈
{
    if (S.top == S.base)//等于if(IsEmpty(S))
    {
        return;
    }
    else
    {
        e = *--S.top;/*
                     --S.top;
                     e=*S.top;*/
    }
}
void Print(SqStack &S)
{
    cout << "栈底：";
    int* p = S.base;//数据从base开始，top处没有数据
    while (p!= S.top)
    {
        cout << *p << " ";
        p++;
    }
    cout << endl;
}

int main()
{

    SqStack S;
    int e;
    Init(S);
    int i = 0;
    for (i = 0; i < 5; i++)
    {
        Push(S, i);
    }
    Print(S);
    cout << "初始化的栈长度："<<GetLength(S)<<endl;
    cout << "连续取四次栈顶元素：" << endl;
    for (i = 0; i < 4; i++)
    {
        Pop(S, e);
        Print(S);
    }
    Destroy(S);
    return 0;
}

链栈的基本操作

#include<iostream>
using namespace std;
#define maxsize 100
typedef struct node
{
    int data;
    struct node* next;
}Node, * Link;
void Init(Link& S)//构造一个空栈
{
    S = NULL;
}
bool IsEmpty(Link S)
{
    if (S == NULL)
        return true;
    else
        return false;
}
void Push(Link& S, int e)//压栈，推入
{
    Link p = new Node;
    p->data = e;
    p->next = S;//新节点插入栈顶，即p在S上面
    S = p;//修改栈顶指针

}
void Pop(Link& S, int& e)//出栈
{
    if (S == NULL)//等于if(IsEmpty(S)
    {
        return;
    }
    else
    {
        e = S->data;
        Link p = S;
        S = S->next;
        delete p;
    }
}
int GetTop(Link S)//取栈顶元素
{
    if (S)
        return S->data;
}
void Print(Link S)
{
    Link p = S;
    cout << "栈底：";
    while (p) 
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;       
}
void Destroy(Link& S)
{
    Link p = S;
    Link q;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;//此时p已经移动到q的位置，有点像继承遗产
    }
}
int main()
{
    Link S;
    int e;
    Init(S);
    for (int i = 0; i < 5; i++)
    {
        Push(S, i);
    }
    Print(S);
    cout << "连续取四次栈顶元素：" << endl;
    for (int i = 0; i < 4; i++)
    {
        Pop(S, e);
        Print(S);
    }
    Destroy(S);
    return 0;
}

顺序队的基本操作

#include<iostream>
using namespace std;
#define maxsize 100
typedef struct
{
    int* base;//初始化的动态分配存储空间
    int front;//头指针，若队列不空，指向队列头元素
    int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置/
}SqQueue;
void Init(SqQueue& Q)
{
    Q.base = (int*)malloc(maxsize * sizeof(int));
    if (!Q.base)
        return;
    else
        Q.front = Q.rear = 0;//头尾指针置为0.队列为空
}
int GetLength(SqQueue &Q)
{
    return ((Q.rear - Q.front + maxsize) % maxsize);
}
void EnQueue(SqQueue& Q, int e)
{
    if ((Q.rear + 1) % maxsize == Q.front)//队满
        return;
    else
    {
        Q.base[Q.rear] = e;//新元素加入队尾
        Q.rear = (Q.rear + 1) % maxsize;//队尾指针+1
    }
}
void DeQueue(SqQueue& Q, int& e)
{
    if (Q.front == Q.rear)//队空
        return;
    e = Q.base[Q.front];//保存队头元素
    Q.front = (Q.front + 1) % maxsize;//队头指针+1
}
int GetHead(SqQueue &Q)
{
    if (Q.front != Q.rear)//队列不为空
    {
        return Q.base[Q.front];//返回队头指针元素的值，队头指针不变
    }
    else
        return -1;
}
void Destroy(SqQueue& Q)
{
    if (Q.base)
        free(Q.base);
    Q.base = NULL;
    Q.front = Q.rear = 0;
}
void Clear(SqQueue& Q)
{
    Q.front = Q.rear = 0;
}
void Print(SqQueue& Q)
{
    int i = Q.front;//front处有数据
    cout << "队列有：";
    while (i != Q.rear)
    {
        cout << Q.base[i] << " ";
        i = (i + 1) % maxsize;
    }
    cout << endl;
}
int main()
{
    SqQueue Q;
    Init(Q);
    for (int i = 0; i < 5; i++)
    {
        EnQueue(Q, i);
    }
    Print(Q);
    cout << "连续出队4次：" << endl;
    for (int i = 0; i < 4; i++)
    {
        DeQueue(Q, i);
        Print(Q);
    }
    Destroy(Q);
    return 0;
}

链队的基本操作

#include<iostream>
using namespace std;
#define maxsize 100
typedef struct node
{
    int data;
    struct node* next;
}Node, * Ptr;
typedef struct
{
    Ptr front;//队头指针
    Ptr rear;//队尾指针
}Link;
void Init(Link& Q)
{
    Q.front = Q.rear = (Ptr)malloc(sizeof(Node));
    if (!Q.front)//front有点像头节点，不存数据的
        return;
    Q.front->next = NULL;
}
void Destroy(Link& Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
}
void EnQueue(Link& Q, int e)
{
    Ptr p = (Ptr)malloc(sizeof(Node));
    if (!p)
        return;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}
void DeQueue(Link& Q, int& e)
{
    if (Q.front == Q.rear)
        return;
    Ptr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
}
void GetHead(Link Q, int& e)
{
    if (Q.front == Q.rear)
        return;
    e = Q.front->next->data;
}
void Print(Link Q)
{
    cout << "队列有：" << endl;
    while (Q.front->next)
    {
        cout << Q.front->next->data << " ";
        Q.front = Q.front->next;
    }
    cout << endl;
}
int main()
{
    Link Q;
    Init(Q);
    for (int i = 0; i < 5; i++)
    {
        EnQueue(Q, i);
    }
    Print(Q);
    cout << "出队操作进行4次：";
    for (int i = 0; i < 4; i++)
    {
        DeQueue(Q, i);
        Print(Q);
    }
    Destroy(Q);
    return 0;
}