数据结构之栈和队列

在讨论栈之前，我们要知道：函数栈帧与数据结构的栈并不是同一个概念。
首先，函数栈帧的栈指的是操作系统层面的内存区域划分，而数据结构的栈是指数据结构中一种数据出入的形式。

1. 栈

1.1 概念与结构

栈是一种特殊的线性表，其数据出入的形式为后进先出(LIFO Last In First Out)或者说先进后出，只允许在固定一端进行插入和删除元素，进行数据插入删除的一段称为栈顶，而另一端则称为栈底。

压栈：栈的插入操作称为压栈/入栈/进栈，在栈顶操作；
出栈：栈的删除操作称为出栈，也在栈顶操作。

我们可以把这两个过程类比为从羽毛球桶内取羽毛球。
在这里插入图片描述

1.2 栈的实现

栈的实现可以通过链表或数组实现，但我们一般都用数组实现，因为在找尾的实现上，数组更优于链表。

在这里插入图片描述

我们实现栈时，一般用动态栈(动态内存分配)，而不用定长的静态栈(规定了栈的长度)。

栈的结构体中有三个元素，分别是数组指针，栈顶下标，栈的容量，如下所示：

typedef char st_data_type;
typedef struct stack
{st_data_type* a;int top;int capacity;
}stack;

一般我们做出一个栈都要有以下几个功能

栈初始化；
入栈；
出栈；
获取栈顶元素；
获取栈顶元素有效个数；
检测栈是否为空；
销毁栈。

具体代码如下：

void stack_init(stack* ps) //初始化
{assert(ps);ps->a = (st_data_type*)malloc(sizeof(st_data_type) * 2);if (ps->a == NULL){perror("stack_init::malloc fail.");return;}ps->a[0] = '0';ps->capacity = 2;//ps->top的初始位置很重要，关系到之后的各函数操作ps->top = 0; //栈顶元素的下一个位置；//ps->top = -1; //刚好是栈顶元素的位置。
}void stack_destroy(stack* ps) //销毁栈
{assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;
}static void inc_capacity(stack* ps) //增容函数，当栈顶的下一个位置的下标等于栈的容量时，就要增容。
{assert(ps);if (ps->capacity == ps->top){st_data_type* temp = (st_data_type*)realloc(ps->a, sizeof(st_data_type) * (ps->capacity + N));if (temp == NULL){perror("inc_capacity::realloc fail.");return;}ps->a = temp;ps->capacity += N;}
}void stack_push(stack* ps, st_data_type x) //压栈
{assert(ps);inc_capacity(ps);ps->a[ps->top] = x;ps->top++;
}void stack_pop(stack* ps) //出栈
{assert(ps);if (ps->top == 0)return;ps->top--;
}int stack_size(stack* ps) //栈内的元素个数
{assert(ps);return ps->top;
}bool stack_empty(stack* ps) //判断栈是否为空
{assert(ps);return (ps->top == 0);
}st_data_type stack_top(stack* ps) //返回栈顶元素
{assert(ps);assert(!stack_empty(ps)); //如果top本来就是0，意味着此栈为空栈，top减一后变成-1，那么就会heap overflow，所以要加警告return ps->a[ps->top - 1];
}

2. 队列

2.1 队列的概念及结构

队列是只允许在一端加入数据，另一端删除数据的特殊线性表，即先进先出或后进后出(FIFO First In First Out)。

入队列：进行插入操作的一端为队尾；
出队列：进行删除操作的一段为队头；

队列的实现使用链表或数组都可以，但使用链表更优，因为在出队列时，若使用数组则效率更低(出头数据后还要把后面一个个数据往前挪)。
在这里插入图片描述

2.2 队列的实现

队列的定义如下：

typedef int que_data_type;typedef struct que_node //这是一个链表节点结构体，用来表示队列
{que_data_type a;struct que_node* next;
}que_node;typedef struct queue //为了迅速找到链表头尾，我们定义一个结构体用于存放链表的头尾指针及链表节点数量
{que_node* head;que_node* tail;int size;
}queue;

同样的，做出一个队列要有以下几个基本功能：

初始化队列；
销毁队列；
入队列；
出队列；
获取队头元素；
获取队尾元素；
获取队列有效元素个数；
检测队列是否为空；

以下是具体实现：

void queue_init(queue* que) //初始化
{assert(que);que->head = que->tail = NULL;que->size = 0;//que_node* new_node = (que_node*)malloc(sizeof(que_node));//if (new_node == NULL)//{//	perror("queue_init::malloc");//	return;//}//new_node->a = 0;//new_node->next = NULL;//que->head= que->tail = new_node;
}void queue_destroy(queue* que) //队列销毁
{assert(que);que_node* cur = que->head;while (cur != que->tail){que_node* temp = cur->next;free(cur);cur = temp;}free(cur); //最后释放掉队尾节点
}static que_node* buy_contain(que_data_type x) //队列增容
{que_node* new_node = (que_node*)malloc(sizeof(que_node));if (new_node == NULL){perror("buy_contail::malloc");return;}new_node->a = x;new_node->next = NULL;return new_node;
}void queue_push(queue* que, que_data_type x) //入队列
{assert(que);que_node* new_node = buy_contain(x);if (que->head == NULL){assert(que->tail == NULL);que->head = que->tail = new_node;}else{que->tail->next = new_node;que->tail = new_node;}que->size++;
}void queue_pop(queue* que) //出队列
{assert(que);if (que->tail == que->head){if (que->head == NULL){assert(!queue_empty(que));printf("Already empty!\n");return;}free(que->head);que->tail = que->head = NULL;}else{que_node* temp = que->head;que->head = que->head->next;free(temp);}que->size--;
}int queue_size(queue* que) //队列元素个数
{assert(que);return que->size;
}bool queue_empty(queue* que) //判断队列是否为空
{assert(que);if (que->head == NULL && que->tail == NULL)return true;elsereturn false;
}que_data_type queue_front(queue* que) //返回队头元素
{assert(que);assert(!queue_empty(que));return que->head->a;
}que_data_type queue_rear(queue* que) //返回队尾元素
{assert(que);assert(!queue_empty(que));return que->tail->a;
}

3. 栈和队列的练习

括号匹配问题

思路：使用栈实现，如果是左括号入就将括号进栈，若遇到右括号，则跟处于栈顶的左括号进行匹配，匹配成功就下一个，不成功就直接返回false。所有括号匹配完成的标志是栈内元素为0。

typedef char st_data_type;
typedef struct stack
{st_data_type* a;int top;int capacity;
}stack;void stack_init(stack* ps)
{assert(ps);ps->a = (st_data_type*)malloc(sizeof(st_data_type) * 2);if (ps->a == NULL){perror("stack_init::malloc fail.");return;}ps->a[0] = '0';ps->capacity = 2;ps->top = 0; //栈顶元素的下一个位置；//ps->top = -1; //刚好是栈顶元素的位置。
}void stack_destroy(stack* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;
}static void inc_capacity(stack* ps)
{assert(ps);if (ps->capacity == ps->top){st_data_type* temp = (st_data_type*)realloc(ps->a, sizeof(st_data_type) * (ps->capacity + N));if (temp == NULL){perror("inc_capacity::realloc fail.");return;}ps->a = temp;ps->capacity += N;}
}void stack_push(stack* ps, st_data_type x)
{assert(ps);inc_capacity(ps);ps->a[ps->top] = x;ps->top++;
}void stack_pop(stack* ps)
{assert(ps);if (ps->top == 0)return;ps->top--;
}int stack_size(stack* ps)
{assert(ps);return ps->top;
}bool stack_empty(stack* ps)
{assert(ps);return (ps->top == 0);
}st_data_type stack_top(stack* ps)
{assert(ps);return ps->a[ps->top - 1];
}bool isValid(char* s)
{if (s == NULL)return false;int j = 0;int size = 0;while (s[j] != 0){size++;j++;}if (size % 2 != 0)return false;stack st;stack_init(&st);int i = 0;while (i != size){if (st.top == 0){stack_push(&st, s[i]);i++;}if ((int)(s[i] - stack_top(&st) == 1) || ((int)(s[i] - stack_top(&st)) == 2)){stack_pop(&st);i++;}else{stack_push(&st, s[i]);i++;}}if (st.top != 0)return false;elsereturn true;
}

用队列实现栈
思路：创建两个队列，其中一个称为非空队列，另一个称为空队列。入栈时，我们将这个元素入到空队列中；出栈时，我们将空队列中的元素一个个出队列，并将这些元素保存到非空队列中，直到空队列剩下最后一个元素，将这个元素用临时变量保存(此时空队列已经为空)，最后，函数返回这个临时变量。若空队列中没有元素了(即连续出栈操作)，就将非空队列进行出队列操作即可。

typedef int que_data_type;typedef struct que_node
{que_data_type a;struct que_node* next;
}que_node;typedef struct queue //存放头尾指针及节点数量
{que_node* head;que_node* tail;int size;
}queue;void queue_init(queue* que)
{assert(que);que->head = que->tail = NULL;que->size = 0;//que_node* new_node = (que_node*)malloc(sizeof(que_node));//if (new_node == NULL)//{//	perror("queue_init::malloc");//	return;//}//new_node->a = 0;//new_node->next = NULL;//que->head= que->tail = new_node;
}bool queue_empty(queue* que)
{assert(que);if (que->head == NULL && que->tail == NULL)return true;elsereturn false;
}void queue_destroy(queue* que)
{assert(que);que_node* cur = que->head;while (cur != que->tail){que_node* temp = cur->next;free(cur);cur = temp;}free(cur); //最后释放掉队尾节点
}que_node* buy_contain(que_data_type x)
{que_node* new_node = (que_node*)malloc(sizeof(que_node));if (new_node == NULL){perror("buy_contail::malloc");return NULL;}new_node->a = x;new_node->next = NULL;return new_node;
}void queue_push(queue* que, que_data_type x)
{assert(que);que_node* new_node = buy_contain(x);if (que->head == NULL){assert(que->tail == NULL);que->head = que->tail = new_node;}else{que->tail->next = new_node;que->tail = new_node;}que->size++;
}void queue_pop(queue* que)
{assert(que);if (que->tail == que->head){if (que->head == NULL){assert(!queue_empty(que));printf("Already empty!\n");return;}free(que->head);que->tail = que->head = NULL;}else{que_node* temp = que->head;que->head = que->head->next;free(temp);}que->size--;
}int queue_size(queue* que)
{assert(que);return que->size;
}que_data_type queue_front(queue* que)
{assert(que);assert(!queue_empty(que));return que->head->a;
}que_data_type queue_rear(queue* que)
{assert(que);assert(!queue_empty(que));return que->tail->a;
}typedef struct {queue q1;queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* forge_stack = (MyStack*)malloc(sizeof(MyStack));queue_init(&forge_stack->q1);queue_init(&forge_stack->q2);return forge_stack;
}void myStackPush(MyStack* obj, int x) {queue* empty_one = &obj->q1;queue* none_empty_one = &obj->q2;if(!queue_empty(empty_one)){empty_one = &obj->q2;none_empty_one = &obj->q1;}queue_push(none_empty_one, x);}int myStackPop(MyStack* obj) {queue* empty_one = &obj->q1;queue* none_empty_one = &obj->q2;if(!queue_empty(empty_one)){empty_one = &obj->q2;none_empty_one = &obj->q1;}while(queue_size(none_empty_one) > 1){que_data_type x = queue_front(none_empty_one);queue_pop(none_empty_one);queue_push(empty_one, x);}que_data_type temp = queue_front(none_empty_one);queue_pop(none_empty_one);return temp;
}int myStackTop(MyStack* obj) {queue* empty_one = &obj->q1;queue* none_empty_one = &obj->q2;if(!queue_empty(empty_one)){empty_one = &obj->q2;none_empty_one = &obj->q1;}return queue_rear(none_empty_one);
}bool myStackEmpty(MyStack* obj) {return (queue_empty(&obj->q1) && queue_empty(&obj->q2));
}void myStackFree(MyStack* obj) {queue_destroy(&obj->q1);queue_destroy(&obj->q2);free(obj);
}/**1. Your MyStack struct will be instantiated and called as such:2. MyStack* obj = myStackCreate();3. myStackPush(obj, x);4. int param_2 = myStackPop(obj);5. int param_3 = myStackTop(obj);6. bool param_4 = myStackEmpty(obj);7. myStackFree(obj);
*/

用栈实现队列
思路：创建两个栈，一个叫push栈，一个叫pop栈。进队列时，往push栈内入栈；出队列时，将push栈所有元素一个个出栈并保存到pop栈内，直到push栈剩下最后一个元素，将这个元素出栈并作为函数返回值进行返回，此时pop栈内的数据存放顺序已经与push栈之前的数据存放顺序相反，如果要进行出队列操作，直接出pop栈的数据即可；如果要进行进队列操作，往push栈进数据即可。若pop栈已经出完数据，则重复上述步骤。

typedef int st_data_type;
typedef struct stack
{st_data_type* a;int top;int capacity;
}stack;void stack_init(stack* ps)
{assert(ps);ps->a = (st_data_type*)malloc(sizeof(st_data_type) * N);if (ps->a == NULL){perror("stack_init::malloc fail.");return;}ps->a[0] = 0;ps->capacity = 2;ps->top = 0; //栈顶元素的下一个位置；//ps->top = -1; //刚好是栈顶元素的位置。
}void stack_destroy(stack* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->top = 0;
}static void inc_capacity(stack* ps)
{assert(ps);if (ps->capacity == ps->top){st_data_type* temp = (st_data_type*)realloc(ps->a, sizeof(st_data_type) * (ps->capacity + N));if (temp == NULL){perror("inc_capacity::realloc fail.");return;}ps->a = temp;ps->capacity += N;}
}void stack_push(stack* ps, st_data_type x)
{assert(ps);inc_capacity(ps);ps->a[ps->top] = x;ps->top++;
}void stack_pop(stack* ps)
{assert(ps);if (ps->top == 0)return;ps->top--;
}int stack_size(stack* ps)
{assert(ps);return ps->top;
}bool stack_empty(stack* ps)
{assert(ps);return (ps->top == 0);
}st_data_type stack_top(stack* ps)
{assert(ps);assert(!stack_empty(ps)); //如果top本来就是0，减一后变成-1，那么就会heap overflow，所以要加警告return ps->a[ps->top - 1];
}typedef struct {stack st_push;stack st_pop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));stack_init(&mq->st_push);stack_init(&mq->st_pop);return mq;
}void myQueuePush(MyQueue* obj, int x) {stack_push(&obj->st_push, x);}bool myQueueEmpty(MyQueue* obj) {return (stack_empty(&obj->st_push) && stack_empty(&obj->st_pop));
}int myQueuePeek(MyQueue* obj) {//if(myQueueEmpty(obj))//    return;if(stack_empty(&obj->st_pop)){while(!stack_empty(&obj->st_push)){stack_push(&obj->st_pop, stack_top(&obj->st_push));stack_pop(&obj->st_push);}}int x = stack_top(&obj->st_pop);return x;
}int myQueuePop(MyQueue* obj) {int x = myQueuePeek(obj);stack_pop(&obj->st_pop);return x;
}void myQueueFree(MyQueue* obj) {stack_destroy(&obj->st_push);stack_destroy(&obj->st_pop);free(obj);
}/**1. Your MyQueue struct will be instantiated and called as such:2. MyQueue* obj = myQueueCreate();3. myQueuePush(obj, x);4. int param_2 = myQueuePop(obj);5. int param_3 = myQueuePeek(obj);6. bool param_4 = myQueueEmpty(obj);7. myQueueFree(obj);
*/

设计循环队列
思路：创建一个结构体，其包含队头下标，队尾下标，整型指针与需创建的动态内存大小k。在创建这块动态内存时，要多分配一个单位。要实现循环，用取余操作。

typedef struct {int front;int rear;int* a;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* mcq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(mcq == NULL){perror("malloc fail");return NULL;}mcq->front = mcq->rear = 0;mcq->k = k;mcq->a = (int*)malloc(sizeof(int)*(k+1));return mcq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->rear == obj->front)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if(((obj->rear+1)%(obj->k+1)) == obj->front)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear] = value;obj->rear = (obj->rear+1)%(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->front = (obj->front+1)%(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;else{if(obj->rear != 0)return obj->a[obj->rear - 1];elsereturn obj->a[obj->k];}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/