从零开始数据结构的生活（三）

Wangxs

2020 年 08 月 10 日

590 次浏览

暂无评论

3052字数

杂七杂八

# 从零开始数据结构的生活（三）

## 栈和队列

### 一、栈

#### 1.什么是栈

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

#### 2. 简单栈的实现

##### (1) 顺序栈的实现

```c++
/**
 * 顺序栈的实现
 * @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) 栈的链式存储结构的实现

```c++
#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)、简单的栈的顺序实现

```c++
#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,则队满

从零开始数据结构的生活（三）