线性结构—栈和队列

简介

某种程度上来说，栈和队列也是线性表，只是它们是操作受限制的线性表。

栈

栈是一种只能在表尾进行插入或者删除的线性表，通常称为表尾端为栈顶，表头端为栈底。它是一种先进后出的线性表，既只能在表尾端插入和删除元素，分别称为入栈和出栈。如下图：

栈.png

栈也有顺序存储结构和链式存储结构两种表示方法，这两种表示方法实现类似，我们这里讲解一下顺序存储结构的代码实现：

#include <iostream>
#include <cstdlib>
using namespace std;

//栈的顺序存储实现
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define INIT_SIZE 20
#define INCREMENT_SIZE 5

typedef int SElemType;
typedef int Status;

//存储结构
typedef struct {
    SElemType *base;
    SElemType *top;
    int size;
}SqStack;

//初始化栈
Status initStack(SqStack &S) {
    S.base = (SElemType *)malloc(INIT_SIZE* sizeof(SElemType));
    if(!S.base) {
        exit(OVERFLOW);
    }
    S.top = S.base;
    S.size = INIT_SIZE;
    return OK;
}

//销毁栈
Status destroyStack(SqStack &S) {
    free(S.base);
    S.base = NULL;
    S.top = NULL;
    S.size = 0;
    return OK;
}

//清空栈
Status clearStack(SqStack &S) {
    S.top = S.base;
    return OK;
}

//判断栈是否为空
Status isEmpty(SqStack S) {
    if(S.top == S.base) {
        return TRUE;
    } else {
        return FALSE;
    }
}

//获取栈的长度
int getStackLength(SqStack S) {
    return S.top - S.base;
}

//获取栈顶元素
Status getTopElement(SqStack S, SElemType &e) {
    if(S.top > S.base) {
        //栈中存在元素
        e = *(S.top - 1);
        return OK;
    } else {
        return ERROR;
    }
}

//元素入栈
Status push(SqStack &S, SElemType e) {
    if((S.top - S.base) / sizeof(SElemType) >= S.size) {
        //申请新的存储空间
        S.base = (SElemType *)realloc(S.base,(S.size + INCREMENT_SIZE)* sizeof(SElemType));
        if(!S.base) {
            exit(OVERFLOW);
        }
        S.top = S.base + S.size;
        S.size += INCREMENT_SIZE;
    }
    *S.top = e;
    S.top++;
    return OK;
}

//元素出栈
Status pop(SqStack &S, SElemType &e) {
    if(S.base == S.top) {
        return ERROR;
    }
    S.top --;
    e = *S.top;
    return OK;
}

//访问元素
void visit(SElemType e) {
    cout << e << " ";
}

//遍历栈
Status traveseStack(SqStack S,void (*visit)(SElemType)) {
    SElemType *base = S.base;
    while (S.top > base) {
        visit(*base);
        base ++;
    }
    return OK;
}

栈可以解决很多问题，例如数值转换、括号匹配、迷宫求解、表达式求值和汉诺塔等等问题。

队列

队列刚好和栈相反，它是一种先进先出的线性表，只能在一端插入元素，在另一端删除元素，如下图所示，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。

队列.png

队列的链式存储结构如下：

#include <iostream>
#include <cstdlib>
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int QElemType;
typedef int Status;

//存储结构
typedef struct QNode{
    //队列中的每个节点
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
    //指向队列头
    QueuePtr front;

    //指向队列尾
    QueuePtr rear;
}LinkQueue;


//初始化队列
Status initQueue(LinkQueue &q) {
    //申请一个节点的空间
    q.front = q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!q.front) {
        //申请失败
        exit(OVERFLOW);
    }
    q.front->next = NULL;
    return OK;
}

//销毁队列
Status destroyQueue(LinkQueue &q) {
    while (q.front) {
        q.rear = q.front->next;
        free(q.front);
        q.front = q.rear;
    }
    return OK;
}

//清空队列
Status clearQueue(LinkQueue &q) {
    destroyQueue(q);
    initQueue(q);
    return OK;
}

//判断队列是否为空
Status isEmpty(LinkQueue q) {
    if(q.front->next == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

//获取队列长度
int getLength(LinkQueue q) {
    int i = 0;
    QueuePtr p = q.front;
    while (p != q.rear) {
        i++;
        p = p->next;
    }
    return i;
}

//获取队头元素
Status getHead(LinkQueue q,QElemType &e) {
    QueuePtr p;
    if(q.front == q.rear) {
        return ERROR;
    }
    p = q.front->next;
    e = p->data;
    return OK;
}

//入队
Status enQueue(LinkQueue &q, QElemType e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    q.rear->next = p;
    q.rear = p;
    return OK;
}

//出队
Status deQueue(LinkQueue &q, QElemType &e) {
    QueuePtr p;
    if(q.front == q.rear) {
        return ERROR;
    }
    p = q.front->next;
    e = p->data;
    q.front->next = p->next;
    if(q.rear == p) {
        q.rear = q.front;
    }
    free(p);
    return OK;
}

//访问元素
void visit(QElemType e) {
    cout << e << " ";
}

//遍历队列
Status treaverseQueue(LinkQueue q, void(*visit)(QElemType)) {
    QueuePtr p = q.front->next;
    while (p) {
        visit(p->data);
        p = p->next;
    }
    return OK;
}

上面实现的是链式存储结构，使用顺序存储结构可以实现循环队列。

应用

1、把一个十进制的数转换为一个二进制的数，例如9转换为二进制是1001，可以使用栈来实现。
进制转换可以采用栈来实现，将余数入栈，然后统一出栈即可。

int main() {
    SqStack stack;
    int number;
    cin >> number;
    if (initStack(stack))
    {
        while (number > 0) {
            push(stack,number%2);
            number /= 2;
        }
        //出栈
        while (!isEmpty(stack)) {
            int e;
            pop(stack,e);
            cout << e << " ";
        }
    }
    return 0;
}

2、用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
队列的push和pop操作是先入先出，元素入队时将元素压入栈1，出队时先将栈1中的元素依次压入栈2，再进行出栈。

int main() {
    SqStack stack1,stack2;
    int number;
    cin>>number;
    if (initStack(stack1)&&initStack(stack2))
    {
        int e, count = number;
        while (count > 0) {
            cin>>e;
            push(stack1, e);
            count --;
        }
        count = number;
        while (count > 0) {
            pop(stack1,e);
            push(stack2,e);
            count--;
        }

        //出栈
        while (!isEmpty(stack2)) {
            pop(stack2,e);
            cout << e << " ";
        }
    }
    return 0;
}