栈与队列

栈

栈（stack）是一种遵循先入后出逻辑的线性数据结构

通常我们能直接使用编程语言内置的栈类（C语言未提供）

/* 初始化栈 */
stack<int> stack;

/* 元素入栈 */
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);

/* 访问栈顶元素 */
int top=stack.top();

/* 元素出栈 */
stack.pop();

/* 获取栈的长度 */
int size = stack.top();

/* 判断是否为空 */
int size=stack.empty();

栈的实现

当我们使用的语言未提供栈类时，我们可以将该语言的“数组”或“链表”当作栈来使用，并在程序逻辑上忽略与栈无关的操作。

1. 基于链表的实现
   将链表的头节点视为栈顶，尾节点视为栈底。对于入栈操作，只需将元素插入链表头部，这种节点插入方法被称为“头插法”

   /* 基于链表实现的栈 */
   typedef struct{
       ListNode*top;// 将头节点作为栈顶
       int size;// 栈的长度
   }LinkedListStack;
   
   /* 构造一个新的栈 */
   LinkedListStack *newLinkedListStack(){
       LinkedListStack *s=malloc(sizeof(LinkedListStack));
       s->top=NULL;
       s->size=0;
       return s;
   }
   
   /* 析构函数 */
   void delLinkedListStack(LinkedListStack *s){
       while(s->top){
           ListNode*n=s->top->next; // 保存当前栈顶节点
           free(s->top); // 释放当前节点内存
           s->top=n; // 将栈顶指向下一个节点
       }
       free(s);
   }
   
   /* 获取栈的长度 */
   int size(LinkedList){
       return s->size;
   }
   
   /* 判断栈是否为空 */
   bool isEmpty(LinkedListStack *s){
       return size(s)==0;
   }
   
   /* 入栈 */
   void push(LinkedListStack *s,int num){
       ListNode *node=(ListNode*)malloc(sizeof(ListNode));
       node->next=s->top; // 更新新加节点指针域
       node->val=num; // 更新新加节点数据域
       s->top=node; // 更新栈顶
       s->size++; // 更新栈大小
   }
   
   /* 访问栈顶元素 */
   int peek(LinkedListStack *s){
       if(s->size==0){
           printf("栈为空\n");
           return INT_MAX;
       }
       return s->top->val;
   }
   
   /* 出栈 */
   int pop(LinkedListStack*s){
       int val=peek(s);
       ListNode*tmp=s->top;
       s->top=s->top->next;
   }

2. 基于数组的实现
   使用数组实现栈时，可以将数组的尾部作为栈顶，入栈与出栈操作分别对应在数组尾部添加元素与删除元素。

   /* 基于数组实现的栈 */
   typedef struct{
       int *data;
       int size;
   }ArrayStack;
   
   /* 构造函数 */
   ArrayStack *newArrayStack(){
       ArrayStack *stack=malloc(sizeof(ArrayStack));
       stack->data=malloc(sizeof(int)*MAX_SIZE);
       stack->size=0;
       return stack;
   }
   
   /* 析构函数 */
   void delArrayStack(ArrayStack *stack){
       free(stack->data);
       free(stack);
   }
   
   /* 获取栈的长度 */
   int size(ArrayStack *stack){
       return stack->size;
   }
   
   /* 判断栈是否为空 */
   bool isEmpty(ArrayStack *stack){
       return stack->size;
   }
   
   /* 入栈 */
   void push(ArrayStack *stack,int num){
       if(stack->size==MAX_SIZE){
           printf("栈已满\n");
           return;
       }
       stack->data[stack->size]=num;
       stack->size++;
   }
   
   /* 访问栈顶元素 */
   void peek(ArrayStack*stack){
       if(stack->size==0){
           printf("栈为空\n");
           return INT_MAX;
       }
       return stack->data[stack->zise-1];
   }
   
   /* 出栈 */
   int pop(ArrayStack *stack){
       int val=ppk
   }

队列

队列（queue）是一种遵循先入先出规则的线性数据结构。队列模拟了排队现象，即新来的人不断加入队列尾部，而位于队列头部的人逐个离开。

通常我们可以直接使用编程语言中现成的队列类（C语言未提供）

queue<int> queue;

queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);

int front=queue.front();
queue.pop();
int size=queue.size();
bool empty=queue.empty();

队列的实现

1. 基于链表的实现
   将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加节点，队首仅可删除节点

   typedef struct{
       ListNode *front,*near;
       int queSize;
   }LinkedListQueue;
   
   LinkListQueue *newLinkedListQueue(){
       LinkedListQueue *queue=(LinkedListQueue*)malloc(sizeof(LinkedListQueue));
       queue->front=NULL;
       queue->rear=NULL;
       queue->queSize=0;
       return queue;
   }
   
   void delLinkedListQueue(LinkedListQueue *queue){
       while(queue->front!=NULL){
           ListNode *tmp=queue->front;
           queue->front=queue->front->next;
           free(temp);
       }
       free(queue);
   }
   
   int size(LinkedListNode *queue){
       return queue->queSize;
   }
   
   bool empty(LinkedListNode *queue){
       return (size(queue)==0);
   }
   
   void push(LinkedListNode *queue,int num){
       ListNode *node=newListNode(num);
       if(queue->front==NULL){ // 如果队列为空，则令头、尾节点都指向该节点
           queue->front=node;
           queue->rear=node;
       }
       else    // 如果队列不为空，则将该节点添加到尾节点后
       {
           queue->rear->next=node;
           queue->rear=node;
       }
       queue->queSize++;
   }
   int peek(LinkedListQueue*queue){
       assert(size(queue)&&queue->front);
       return queue->front->val;
   }
   int pop(LinkedListQueue *queue){
       int num=peek(queue);
       ListNode *tmp=queue->front;
       queue->front=queue->front->next;
       free(tmp);
       queue->queSize--;
       return num;
   }
   
   void printLinkedListQueue(LinkedListQueue*queue){
       int *arr=malloc(sizeof(int)*queue->queSize);
       int i;
       ListNode *node;
       for(i=0,node=queue->front;i<queue->queSize;i++){
           arr[i]=node->val;
           node=node->next;
       }
       printArray(arr,queue->queSize);
       free(arr)
   }

2. 通过数组的实现
   数组实现的队列仍然具有局限性：其长度不可变。

在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。在不断进行入队和出队的过程中，front 和 rear 都在向右移动，当它们到达数组尾部时就无法继续移动了。为了解决此问题，我们可以将数组视为首尾相接的“环形数组”。

typedef struct{
    int *nums;
    int front;
    int queSize;
    int queCapacity;
}ArrayQueue;

ArrayQueue *newArray(int capacity){
    ArrayQueue *queue=(ArrayQueue*)malloc(sizeof(ArrayQueue));
    queue->queCapacity=capacity;
    queue->nums=(int*)malloc(sizeof(int)*queue->queCapacity);
    queue->front=queue->queSize=0;
    return queue;
}

void delArrayQueue(ArrayQueue *queue){
    free(queue->nums);
    free(queue);
}

int capacity(ArrayQueue *queue){
    return queue->Capacity;
}

int empty(ArrayQueue *queue){
    return queue->queSize;
}

bool empty(ArrayQueue *queue){
    return queue->queSize==0;
}

int peek(ArrayQueue *queue){
    assert(size(queue)!=0);
    return queue->nums[queue->front];
}

void push(ArrayQueue *queue,int num){
    if(size(queue)==capacity(queue)){
        printf("队列已满\r\n");
        return;
    }
    int rear =(queue->front+queue->queSize)%queue->queCapacity;
    queue->nums[rear]=num;
    queue->queSize++;
}

int pop(ArrayQueue *queue){
    int num=peek(queue);
    queue->front=(queue->front+1)%queue->quCapacity;
    queue->queSize--;
    return num;
}

int *toArray(ArrauQueue *queae){
    *queSize=queue->queSize;
    int*res=(int*)calloc(queue->queSize,sizeof(int));
    int j=queue->front;
    for(int i=0;i<queue->queSize;i++){
        res[i]=queue->nums[j%queue->queCapacit];
        j++;
    }
    return res;
}

双向队列

可以直接使用编程语言中已实现的双向队列类（C语言没有）：

/* 初始化双向队列 */
deque<int> deque;

/* 元素入队 */
deque.push_back(2);   // 添加至队尾
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);  // 添加至队首
deque.push_front(1);

/* 访问元素 */
int front = deque.front(); // 队首元素
int back = deque.back();   // 队尾元素

/* 元素出队 */
deque.pop_front();  // 队首元素出队
deque.pop_back();   // 队尾元素出队

/* 获取双向队列的长度 */
int size = deque.size();

/* 判断双向队列是否为空 */
bool empty = deque.empty();

双向队列的实现

1. 基于双向链表的实现

/* 双向链表节点 */
typedef struct DoublyListNode {
    int val;                     // 节点值
    struct DoublyListNode *next; // 后继节点
    struct DoublyListNode *prev; // 前驱节点
} DoublyListNode;

/* 构造函数 */
DoublyListNode *newDoublyListNode(int num) {
    DoublyListNode *new = (DoublyListNode *)malloc(sizeof(DoublyListNode));
    new->val = num;
    new->next = NULL;
    new->prev = NULL;
    return new;
}

/* 析构函数 */
void delDoublyListNode(DoublyListNode *node) {
    free(node);
}

/* 基于双向链表实现的双向队列 */
typedef struct {
    DoublyListNode *front, *rear; // 头节点 front ，尾节点 rear
    int queSize;                  // 双向队列的长度
} LinkedListDeque;

/* 构造函数 */
LinkedListDeque *newLinkedListDeque() {
    LinkedListDeque *deque = (LinkedListDeque *)malloc(sizeof(LinkedListDeque));
    deque->front = NULL;
    deque->rear = NULL;
    deque->queSize = 0;
    return deque;
}

/* 析构函数 */
void delLinkedListdeque(LinkedListDeque *deque) {
    // 释放所有节点
    for (int i = 0; i < deque->queSize && deque->front != NULL; i++) {
        DoublyListNode *tmp = deque->front;
        deque->front = deque->front->next;
        free(tmp);
    }
    // 释放 deque 结构体
    free(deque);
}

/* 获取队列的长度 */
int size(LinkedListDeque *deque) {
    return deque->queSize;
}

/* 判断队列是否为空 */
bool empty(LinkedListDeque *deque) {
    return (size(deque) == 0);
}

/* 入队 */
void push(LinkedListDeque *deque, int num, bool isFront) {
    DoublyListNode *node = newDoublyListNode(num);
    // 若链表为空，则令 front 和 rear 都指向node
    if (empty(deque)) {
        deque->front = deque->rear = node;
    }
    // 队首入队操作
    else if (isFront) {
        // 将 node 添加至链表头部
        deque->front->prev = node;
        node->next = deque->front;
        deque->front = node; // 更新头节点
    }
    // 队尾入队操作
    else {
        // 将 node 添加至链表尾部
        deque->rear->next = node;
        node->prev = deque->rear;
        deque->rear = node;
    }
    deque->queSize++; // 更新队列长度
}

/* 队首入队 */
void pushFirst(LinkedListDeque *deque, int num) {
    push(deque, num, true);
}

/* 队尾入队 */
void pushLast(LinkedListDeque *deque, int num) {
    push(deque, num, false);
}

/* 访问队首元素 */
int peekFirst(LinkedListDeque *deque) {
    assert(size(deque) && deque->front);
    return deque->front->val;
}

/* 访问队尾元素 */
int peekLast(LinkedListDeque *deque) {
    assert(size(deque) && deque->rear);
    return deque->rear->val;
}

/* 出队 */
int pop(LinkedListDeque *deque, bool isFront) {
    if (empty(deque))
        return -1;
    int val;
    // 队首出队操作
    if (isFront) {
        val = peekFirst(deque); // 暂存头节点值
        DoublyListNode *fNext = deque->front->next;
        if (fNext) {
            fNext->prev = NULL;
            deque->front->next = NULL;
        }
        delDoublyListNode(deque->front);
        deque->front = fNext; // 更新头节点
    }
    // 队尾出队操作
    else {
        val = peekLast(deque); // 暂存尾节点值
        DoublyListNode *rPrev = deque->rear->prev;
        if (rPrev) {
            rPrev->next = NULL;
            deque->rear->prev = NULL;
        }
        delDoublyListNode(deque->rear);
        deque->rear = rPrev; // 更新尾节点
    }
    deque->queSize--; // 更新队列长度
    return val;
}

/* 队首出队 */
int popFirst(LinkedListDeque *deque) {
    return pop(deque, true);
}

/* 队尾出队 */
int popLast(LinkedListDeque *deque) {
    return pop(deque, false);
}

/* 打印队列 */
void printLinkedListDeque(LinkedListDeque *deque) {
    int *arr = malloc(sizeof(int) * deque->queSize);
    // 拷贝链表中的数据到数组
    int i;
    DoublyListNode *node;
    for (i = 0, node = deque->front; i < deque->queSize; i++) {
        arr[i] = node->val;
        node = node->next;
    }
    printArray(arr, deque->queSize);
    free(arr);
}