数据结构简单入门/复习（三）-栈与队列（C语言）(2021/3/30更新)

这里的栈用的是顺序栈（数组），队列用的是链表队列（链表）。

2021/3/25: 加了共享顺序栈。我以前有够懒的噢，不过我现在也有够懒的，所以其他存储结构后面再补。
2021/3/30: 加了完全利用空间的循环顺序队列，加了入队退队时间复杂度为O(1)且不浪费出队结点空间的循环链式队列。
2022/1/23：更新为 Markdown 格式。

栈

定义与结构

栈是一种限定在表尾进行插入/删除的线性表，表尾，被称作栈顶，表头，被称作栈底，薯片桶就是一种栈。

栈是一种后进先出的线性表。举个例子，有三个元素1、2、3，其中，1是第一个进的，2是第二个进的，3是第三个进的，那么在栈底的元素是1，栈顶的元素是3，若进行删除操作，出来的是栈顶的3。

#define SElemType int    //设置栈中元素的类型为int
typedef struct{
    SElemType *base;     //栈底
    SElemType *top;      //栈顶
    int stacksize;       //注意，这里的栈的大小是指总大小，而不是指用了几个，只在重新分配空间时会变化。
}SqStack;

顺序栈的使用

SqStack S;

//初始化栈
S.base = (SElemType*)malloc(100*sizeof(SElemType));  //为栈分配空间，大小为100.
S.top = S.base;      //栈顶位置设置，因为此时栈是空栈。
S.stacksize = 100;   //将栈的大小设置为100，及最开始分配空间的大小。

//插入
if(S.top-S.base >= S.stacksize){    //这部分的判断是为了解决栈空间不足。
    S.base = (SElemType*)realloc(S.base, S.stacksize+10)*sizeof(SElemType));  //realloc是一个重新分配内存空间的函数，这里用来给栈增加10个空间。
    S.top = S.base + S.stacksize;  //栈底的地址因为realloc函数改变了，因此栈顶要重新设置。
    S.stacksize += 10;             //将栈的大小记录值增加。
}
*S.top++ = 123;

//删除
if(S.top == S.base) print(已空);  //栈顶和栈底指针相同，意味着是空栈。
else --S.top;                       //栈直接退后即可，不用释放内存。

//获得栈顶数据
printf(%d, *(S.top-1));           //top位置是用来存储新数据的，栈顶位置是在top-1的地方。

顺序共享栈

#include <stdio.h>
#include <stdlib.h>

#define STACK_LENGTH 5

typedef struct shareStack {
    int* data;
    int maxSize;
    int leftTop;
    int rightTop;
}shareStack;

shareStack* initializeStack();
void enlargeStack(shareStack* s);
void pushLeftStack(shareStack* s, int value);
int popLeftStack(shareStack* s);
int stackLeftEmpty(shareStack* s);
void pushRightStack(shareStack* s, int value);
int popRightStack(shareStack* s);
int stackRightEmpty(shareStack* s);

int main(){
    shareStack* s = initializeStack();
    int value;
    int pos;
    puts(left stack test: push element more than stack size);
    for (pos = 0; pos < STACK_LENGTH ; pos++) {
        pushLeftStack(s, pos);
    }
    while (stackLeftEmpty(s) != 1) {
        value = popLeftStack(s);
        printf(%d , value);
    }
    puts(\n\nright stack test: push element more than stack size);
    for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
        pushRightStack(s, pos);
    }
    while (stackRightEmpty(s) != 1) {
        value = popRightStack(s);
        printf(%d , value);
    }
    puts(\n\nmix stack test: push leftStack and RightStack then pop all);
    for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
        pushLeftStack(s, pos);
        pushRightStack(s, pos);
    }
    for (pos = 0; pos < STACK_LENGTH * 2; pos++) {
        value = popLeftStack(s);
        printf(%d , value);
        value = popRightStack(s);
        printf(%d , value);
    }

    system(PAUSE);
    return 0;
}

shareStack* initializeStack() { //栈初始化
    shareStack* s;
    s = malloc(sizeof(shareStack));
    s->maxSize = STACK_LENGTH;
    s->data = malloc(sizeof(int) * s->maxSize);
    s->leftTop = 0;
    s->rightTop = s->maxSize - 1;
    return s;
}

void enlargeStack(shareStack* s) {  //栈扩容
    printf(enlargeing...\n);
    s->maxSize += STACK_LENGTH;
    s->data = realloc(s->data, sizeof(int) * s->maxSize);
    int pos;
    for (pos = s->maxSize - STACK_LENGTH - 1; pos > s->rightTop; pos--) {
        s->data[pos + STACK_LENGTH] = s->data[pos];
    }
    s->rightTop += STACK_LENGTH;
}

void pushLeftStack(shareStack* s, int value) {  //左栈进栈
    if (s->rightTop == s->leftTop) {
        enlargeStack(s);
    }
    s->data[s->leftTop] = value;
    s->leftTop += 1;
}

int popLeftStack(shareStack* s) {   //左栈退栈一次，返回退栈的值
    s->leftTop -= 1;
    return s->data[s->leftTop];
}

int stackLeftEmpty(shareStack* s) { //左栈为空时，返回1，否则为0
    return s->leftTop == 0 ? 1 : 0;
}

void pushRightStack(shareStack* s, int value) { //右栈进栈
    if (s->rightTop == s->leftTop)
        enlargeStack(s);
    s->data[s->rightTop] = value;
    s->rightTop -= 1;
}

int popRightStack(shareStack* s) {  //右栈退栈一次，返回退栈的值
    s->rightTop += 1;
    return s->data[s->rightTop];
}

int stackRightEmpty(shareStack* s) {    //右栈为空时，返回1，否则为0
    return s->rightTop == s->maxSize - 1 ? 1 : 0;
}

队列

定义与结构

队列是一种先进先出的线性表，元素从表头插入，从表尾退出。

队列的形式与日常的排队相似，但是没有插队这个说法。

//队列元素：
#define QElemType int
typedef struct QNode{
    QElemType data;      //元素数据
    struct QNode *next;  //后排元素
}QNode;
//队列存储：
typedef struct{
    QNode *front;    //队头指针
    QNode *rear;     //队尾指针
}LinkQueue;

链式队列的使用

//创建
LinkQueue Q;
Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));   //队头不放元素，仅作指示

//插入
QNode *p = (QNode*)malloc(sizeof(QNode)); //分配新元素内存空间
p->data = 123;       //设置新元素值
p->next = NULL;      //新元素后没有元素
Q.rear->next = p;    //将队尾的下一个元素设置成新元素
Q.rear = p;          //将新元素设置为新的队尾

//删除
if(Q.front == Q.rear) print(队列已空);
else {
    QNode *temp = Q.front->next;           //创建临时指针指向队头
    Q.front->next = temp->next;            //将队头设置成第二位的元素
    if(Q.rear == temp) Q.rear = Q.front;   //如果队头是最后一个元素，将队尾的指针调整为队头指针，此时为空队列
    free(temp);                            //释放退出的队头
}

//获得队头值
if(Q.front == Q.rear) printf(队列已空);
else print(%d, Q.front->next->data);

循环顺序队列-完全利用空间

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_LENGTH 5

typedef struct cycleQueue {
    int* data;
    int front;
    int rear;
    int isEmpty;
}cycleQueue;

cycleQueue* initializeCycleQueue();
int enqueue(cycleQueue* q, int ele);
int dequeue(cycleQueue* q, int* ele);

int main(){
    cycleQueue* q = initializeCycleQueue();
    int value;
    int pos;
    int pass;

    puts(队列大小为5，进7个，退7个：);
    for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
        pass = enqueue(q, pos);
        if(pass) printf(%d enqueue, front: %d, rear: %d\n, pos, q->front, q->rear);
    }
    for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
        pass = dequeue(q, &value);
        if(pass)printf(%d dequeue, front: %d, rear: %d\n, value, q->front, q->rear);
    }

    puts(\n队列大小为5，进7个，退2个，进7个，并输出队列情况：);
    for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
        pass = enqueue(q, pos);
        if (pass) printf(%d enqueue, front: %d, rear: %d\n, pos, q->front, q->rear);
    }
    for (pos = 0; pos < 2; pos++) {
        pass = dequeue(q, &value);
        if (pass)printf(%d dequeue, front: %d, rear: %d\n, value, q->front, q->rear);
    }
    for (pos = 10; pos < QUEUE_LENGTH + 12; pos++) {
        pass = enqueue(q, pos);
        if (pass) printf(%d enqueue, front: %d, rear: %d\n, pos, q->front, q->rear);
    }
    for (pos = 0; pos < QUEUE_LENGTH; pos++) {
        printf(%d , q->data[pos]);
    }

    system(PAUSE);
    return 0;
}

cycleQueue* initializeCycleQueue() {
    cycleQueue* q = malloc(sizeof(cycleQueue));
    q->front = 0;    //头指针指向队头的下一个位置
    q->rear = 0; //尾指针指向队尾的下一个位置
    q->data = malloc(sizeof(int) * QUEUE_LENGTH);
    q->isEmpty = 1;  //1表示队列空
    return q;
}

int enqueue(cycleQueue* q, int ele) {
    if (q->front == q->rear && q->isEmpty == 0) {
        printf(Queue full, error enqueue operation.\n);
        return 0;
    }
    q->isEmpty = 0;
    q->data[q->rear] = ele;
    q->rear = (q->rear + 1) % QUEUE_LENGTH;
    return 1;
}

int dequeue(cycleQueue* q, int* ele) {
    if (q->front == q->rear && q->isEmpty == 1) {
        printf(Queue empty, error dequeue operation.\n);
        return 0;
    }
    q->front = (q->front + 1) % QUEUE_LENGTH;
    if (q->front == q->rear) q->isEmpty = 1;
    *ele = q->data[(q->front - 2 + (QUEUE_LENGTH + 1)) % QUEUE_LENGTH];
    return 1;

}

循环链式队列-不浪费退队空间，且入队退队时间复杂度O(1)。

#include <stdio.h>
#include <stdlib.h>

#define QUEUE_LENGTH 2

typedef struct queueNode {
    struct queueNode* next;
    int data;
}queueNode;

typedef struct queue {
    queueNode* front;
    queueNode* rear;
}queue;

queue* initializeQueue();
void enqueueBin(queue* qBin, queueNode* node);
queueNode* dequeueBin(queue* qBin);
int dequeue(queue* q, queue* qBin);
void enqueue(queue* q, queue* qBin, int val);
void printQueue(queue* q);

int main(){
    queue* q = initializeQueue();
    queue* qBin = initializeQueue();
    int value;
    int pos;
    int pass;

    puts(进4个，退4个：);
    for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
        enqueue(q, qBin, pos);
        printf(%d enqueue\n, pos);
    }
    for (pos = 0; pos < QUEUE_LENGTH + 2; pos++) {
        value = dequeue(q, qBin); 
        printf(%d  dequeue\n, value);
    }
    printQueue(q);

    puts(\n，进4个，退2个，进4个：);
    for (pos = 10; pos < QUEUE_LENGTH + 12; pos++) {
        enqueue(q, qBin, pos);
        printf(%d enqueue\n, pos);
    }
    for (pos = 0; pos < 2; pos++) {
        value = dequeue(q, qBin);
        printf(%d   dequeue\n, value);
    }
    for (pos = 20; pos < QUEUE_LENGTH + 22; pos++) {
        enqueue(q, qBin, pos);
        printf(%d enqueue\n, pos);
    }
    printQueue(q);

    system(PAUSE);
    return 0;
}

queue* initializeQueue() {
    queue* q = malloc(sizeof(queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueueBin(queue* qBin, queueNode* node) {
    if (qBin->front == NULL) {
        qBin->front = qBin->rear = node;
    }
    else {
        qBin->rear->next = node;
        qBin->rear = node;
        node->next = NULL;
    }
}

queueNode* dequeueBin(queue* qBin) {
    if (qBin->front == NULL) {
        return malloc(sizeof(queueNode));
    }
    else {
        queueNode *res = qBin->front;
        qBin->front = qBin->front->next;
        return res;
    }
}

int dequeue(queue* q, queue* qBin) {
    if (q->rear == NULL) {
        printf(queue empty, error.\n);
        return 0;
    }
    queueNode* node = q->front;
    if (q->front == q->rear) {
        q->front = q->rear = NULL;
    }
    else {
        q->rear->next = q->front->next;
        q->front = q->front->next;
    }
    enqueueBin(qBin, node);
    return node->data;
}

void enqueue(queue* q, queue* qBin, int val) {
    queueNode *node = dequeueBin(qBin);
    node->data = val;
    if (q->front == NULL) {
        node->next = node;
        q->front = q->rear = node;
    }
    else {
        node->next = q->front;
        q->rear->next = node;
        q->rear = node;
    }
}

void printQueue(queue* q) {
    queueNode* node = q->front;
    if (node) do {
        printf(%d , node->data);
        node = node->next;
    } while (node != q->front);
    puts();
}