从零开始数据结构的生活(三)

栈和队列

一、栈

1.什么是栈

栈(Stack)是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表,但限定只能在某一端进行插入和删除操作。

2. 简单栈的实现

(1) 顺序栈的实现
/**
 * 顺序栈的实现
 * @author wangx
 * @date 2020/08/10
 */
#include <iostream>
using namespace std;
#define MaxSize 50 // 定义栈中元素的个数
typedef int ElemType; // 定义栈中元素的类型
typedef struct {
    ElemType data[MaxSize]; //存放栈中元素
    int top;
} SqStack;
//初始化栈
void init(SqStack &S) {
    S.top = -1;
}

//判断栈空
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true; // 栈空
    } else {
        return false; // 栈不空
    }
}

//入栈

bool Push(SqStack &S,ElemType x) {
    if(S.top == MaxSize - 1){
        return false; // 栈满,入栈失败
    } else {
        S.data[++S.top]=x; // 指针先加一,然后入栈,因为top=-1
        return true; //入栈成功
    }
}

// 出栈
bool Pop(SqStack &S,ElemType &x) {
    if (S.top == -1) {
        return false; // 栈空,报错
    } else {
        x = S.data[S.top--]; // 先出栈,然后再把指针减一
        return true;
    }
}

// 读取栈顶元素
bool getTop(SqStack S, ElemType &x) {
    if (S.top == -1){
        return false; // 栈空报错
    } else {
        x = S.data[S.top];
        return true;
    }
}
int main() {
    cout << "Hello, World!" << endl;
    return 0;
}
(2) 栈的链式存储结构的实现
#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LinkNode{
    ElemType data; // 数据域
    struct LinkNode *next; // 指针域
} StackNode;
typedef struct LINKSTACK{
    StackNode top;
    int size;
} LinkStack;

LinkStack* Init(){
    LinkStack* stack = (LinkStack*) malloc(sizeof(LinkStack));
    stack->size = 0;
    stack->top.next = NULL; 
    return stack;
}

void Push(LinkStack* S, LinkNode* data) {
    if (S == NULL) return; // 栈未初始化
    if (data == NULL) return; //传入的数据无效
    data->next = S->top.next;
    S->top.next = data;
    S->size++;
}

LinkNode* Pop(LinkStack* S) {
    if (S == NULL) return NULL; // 栈未初始化
    if (S->size == 0) return NULL;// 栈空

    LinkNode* pNext = S->top.next; // 第一个有效节点
    S->top.next = pNext->next;
    S->size--;
    return pNext;
}

LinkNode* getTop(LinkStack* S) {
    if (S == NULL) return NULL; // 栈未初始化
    if (S->size == 0) return NULL;// 栈空
    return S->top.next;
}

//返回栈中元素的个数
int getSize(LinkStack* S) {
    if (S == NULL) {
        return -1;
    }
    return S->size;
}

//清空栈
void cleanStack(LinkStack* S) {
    if(S == NULL) return;
    S->top.next = NULL;
    S->size = 0;
}

//销毁栈
void destoryStack(LinkStack* S) {
    if (S == NULL) return;
    free(S);
}

int main() {
    LinkStack* S = Init();
}

二、队列

1、什么是队列

​ 队列(Queue)简称队,也是一种操作受限的线性表,只允许在表的一端进行插入而在表的另一端进行删除。向队列插入元素称为入队或进队;删除元素称为出队或离队,这和我们日常生活中的排队是一致的,最早排队的最早离开,其操作的特性是先进先出(First In First Out FIFO)

2、队列的顺序存储结构的实现

(1)、简单的栈的顺序实现
#include<iostream>
using namespace std;
#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize]; // 存放队列元素
    int front,rear; //队头和队尾指针
}SqQueue;

void init(SqQueue &q){
    q.front=0;
    q.rear=0;
} 
//入队
bool push(SqQueue &q, ElemType e) {
    if (q.rear == MaxSize) return false;
    q.data[q.rear++] = e; 
}

//出队
bool pop(SqQueue &q, ElemType &data) {
    if (q.rear == q.front && q.front == 0) return false; //队空
    data = q.data[q.front++];
}

int main() {
    SqQueue q;
    init(q);
    push(q, 10);
    int data = 0;
    pop(q, data);
    cout<< data << endl;
}
(2)、循环队列
  • 初始时: q.front=q.rear=0
  • 队首指针进1:q.front=(q.front+1)%MaxSize
  • 队尾指针进1:q.rear=(q.rear+1)%MaxSize
  • 队列长度: (q.rear + MaxSize-q.front)%MaxSize

区分队空和队满的三种处理方式

  • 牺牲一个单元来区分队空和队满

    • 队满条件: (q.rear+1)%MaxSize==q.front
    • 队空条件: q.front==q.rear
    • 队列中元素的个数:(q.rear-q.front+MaxSize) % MaxSize
  • 类型中增设表示元素个数的数据成员

    • 队空为: q.size == 0
    • 队满条件: q.size == MaxSize
    • 队列中元素个数:q.size
  • 类型中增设tag数据元素来区分队满还是队空

    • tag=0时若因删除导致的q.front=q.rear,则队空
    • tag=1,若因插入导致的q.front=q.rear,则队满
最后修改:2020 年 08 月 10 日
如果觉得我的文章对你有用,请随意赞赏