数据结构——栈、队列
栈
栈的基本概念
1.栈的定义
栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top)。允许插入和删除的一端。入数据，出数据都在栈顶。
栈底(Bottom)。固定的，不允许插入和删除的一端。
空栈。不含任何元素的空表。
栈的操作特性可以明显概括为后进先出。
栈的插入操作，叫做进栈，也叫压栈，入栈。栈的删除操作，叫做出栈，有点叫做弹栈。
栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的 代价比较小。
栈的结构体可以描述为
typedef int stackData;
typedef struct stack
{
stackData* val;
int size;
int cakacity;
}stack;
栈的基本算法
*初始化
void SKinit(stack* head) {
head->val = (stackData*)malloc(sizeof(stackData) * 4);
assert(head->val);
head->size = 4;//栈存储空间的大小
head->top = 0;//top是栈顶元素的下一个位置
}
*判空
bool SKEmpty(stack* pHead) {
return pHead->top == 0;
}
*获取栈顶元素
stackData StackTop(stack* ps) {
assert(ps);
return ps->val[ps->top - 1];
}
进栈和出栈
*进栈
void SKpush(stack* pHead, stackData x) {
assert(pHead);
stack* head = pHead;
if (head->top == head->size) {//判断是否需要扩容
stackData* p1 = (stackData*)realloc(head->val,sizeof(stackData) * head->size * 2);
assert(p1);
head->val = p1;
head->size *= 2;
}
head->val[head->top] = x;
head->top++;
}
*出栈
stackData SKPop(stack* pHead) {
assert(pHead);
stack* head = pHead;
stackData date = head->val[head->top - 1];
head->top--;
return date;
}
*获取栈中有效元素个数
int SKsize(stack* pHead)
{
return pHead->top;
}
*销毁栈
void SKdestory(stack* pHead)
{
while (pHead->top)
{
SKPop(pHead);
}
}
队列
队列的基本概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)。
队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
队列实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的结构体可以描述为
typedef char QDatatype;
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;
typedef struct Queue
{
QNode* head; //头节点
QNode* tail; //尾节点
int size;
}Queue;
*初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}*队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}*队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}*获取队列队头元素
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}*获取队列队尾元素
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}*判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}*获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
*销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}循环队列
我们把队列的这种头尾相接的顺序存储结构称为循环队列。用来解决队列的假溢出问题。环形队列可以使用数组实现，也可以使用循环链表实现。
以数组为数据存储模型比链表实现方便的多。所以本篇以数组为例。
front：只需要保存队头元素在数组中的下标即可。
rear：保存队尾元素的下一个下标，这样可以保证队列位空时rear和front的下标相同，队列满时front是rear的下一位。
为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”。
队满条件： (Q->rear + 1)%Maxsize == Q->front
队空条件仍： Q->front == Q->rear
队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为 Q->size == O ；队满的条件为 Q->size == Maxsize 。这两种情况都有 Q->front == Q->rear
（3）类型中增设tag 数据成员，以区分是队满还是队空。tag 等于0时，若因删除导致 Q->front == Q->rear ，则为队空；tag 等于 1 时，若因插入导致 Q ->front == Q->rear ，则为队满。
这里我们重点讨论第一种方法
实现
typedef int ElemType;
#define MAXSIZE 50
/*循环队列的顺序存储结构*/
typedef struct{
ElemType data[MAXSIZE];
int front; //头指针
int rear; //尾指针,若队列不空，指向队列尾元素的下一个位置
}SqQueue;
*初始化
/*初始化一个空队列Q*/
void InitQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0;
return;
}
*判空
bool isEmpty(SqQueue Q)
{
if(Q.rear == Q.front)
return true;
return false;
}
*求长度
int QueueLength(SqQueue Q)
{
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
*入队列
/*若队列未满，则插入元素e为Q新的队尾元素*/
bool InQueue(SqQueue *Q, ElemType e){
if((Q->rear + 1) % MAXSIZE == Q->front){
return false; //队满
}
Q->data[Q->rear] = e; //将元素e赋值给队尾
Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转到数组头部
return true;
}
*出队列
/*若队列不空，则删除Q中队头元素，用e返回其值*/
bool OutQueue(SqQueue *Q, ElemType *e)
{
if(isEmpty(Q)){
return false; //队列空的判断
}
*e = Q->data[Q->front]; //将队头元素赋值给e
Q->front = (Q->front + 1) % MAXSIZE; //front指针向后移一位置，若到最后则转到数组头部
return true;
}
栈和队列间相互转换
栈模拟实现队列
可以利用两栈后入先出的特性，先用栈1把入队列的值存起来，在存起来后，就把栈1的值出栈到栈2中进行保存，这样就完成栈中底部的值变为顶部的值了。
代码示例
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int stackData;
typedef struct stack
{
stackData* val;
int size;
int top;
}stack;//栈的结构体
typedef struct {
stack* stack1;//接收数据
stack* stack2;//出数据
} MyQueue;//栈模拟的队列
//栈函数的实现
void SKinit(stack** head) {
*head = (stack*)malloc(sizeof(stack));
assert(*head);
(*head)->val = (stackData*)malloc(sizeof(stackData) * 4);
assert((*head)->val);
(*head)->size = 4;
(*head)->top = 0;
}
//入栈
void SKpush(stack* pHead, stackData x) {
assert(pHead);
stack* head = pHead;
if (head->top == head->size) {
stackData* p1 = (stackData*)realloc(head->val,sizeof(stackData) * head->size * 2);
assert(p1);
head->val = p1;
head->size *= 2;
}
head->val[head->top] = x;
head->top++;
}
//出栈
stackData SKPop(stack* pHead) {
assert(pHead);
stack* head = pHead;
stackData date = head->val[head->top - 1];
head->top--;
return date;
}
//销毁
void SKdestory(stack* pHead) {
while (pHead->top) {
SKPop(pHead);
}
}
//大小
int SKsize(stack* pHead) {
return pHead->top;
}
//判断为空
int SKEmpty(stack* pHead) {
return pHead->top == 0;
}
stackData StackTop(stack* ps) {
assert(ps);
return ps->val[ps->top - 1];
}
//队列函数的实现
// 创建一个队列
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); // 为队列分配内存
SKinit(&obj->stack1); // 初始化栈1，用于接收数据
SKinit(&obj->stack2); // 初始化栈2，用于出数据
return obj; // 返回队列对象
}
// 入队操作，将元素x压入栈1
void myQueuePush(MyQueue* obj, int x) {
SKpush(obj->stack1, x); // 直接将元素压入栈1
}
// 出队操作，从栈2中弹出元素
int myQueuePop(MyQueue* obj) {
// 如果栈2为空，将栈1中的元素移动到栈2
if (obj->stack2->top == 0) {
// 从栈1依次弹出元素并压入栈2
while (!SKEmpty(obj->stack1)) {
stackData n = SKPop(obj->stack1);
SKpush(obj->stack2, n);
}
}
// 从栈2中弹出元素
return SKPop(obj->stack2);
}
// 查看队列头部元素
int myQueuePeek(MyQueue* obj) {
// 如果栈2为空，将栈1中的元素移动到栈2
if (obj->stack2->top == 0) {
while (!SKEmpty(obj->stack1)) {
stackData n = SKPop(obj->stack1);
SKpush(obj->stack2, n);
}
}
// 返回栈2的栈顶元素
return StackTop(obj->stack2);
}
// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
return (obj->stack2->top == 0) && (obj->stack1->top == 0); // 栈1和栈2都为空时，队列为空
}
// 销毁队列，释放所有资源
void myQueueFree(MyQueue* obj) {
// 一直出队直到队列为空
while (!myQueueEmpty(obj)) {
myQueuePop(obj);
}
// 释放栈1和栈2的内存
free(obj->stack1->val);
free(obj->stack2->val);
free(obj->stack1);
free(obj->stack2);
// 释放队列对象
free(obj);
}
队列模拟实现栈
可以利用两个队列进行互相入队，把队列中的最后一个元素进行返回，这样就完成栈的先入先出的原则了。
代码示例
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 定义栈中存储的数据类型
typedef int stackData;
// 栈的结构体定义
typedef struct stack {
stackData* val; // 动态数组，用来存储栈的元素
int size; // 栈的容量
int top; // 栈顶元素的索引
} stack;
// 初始化栈函数
void SKinit(stack** head) {
*head = (stack*)malloc(sizeof(stack));
assert(*head); // 确保内存分配成功
(*head)->val = (stackData*)malloc(sizeof(stackData) * 4);
assert((*head)->val); // 确保内存分配成功
(*head)->size = 4;
(*head)->top = 0;
}
// 入栈操作
void SKpush(stack* pHead, stackData x) {
assert(pHead); // 确保栈指针有效
stack* head = pHead;
// 如果栈满，进行扩容
if (head->top == head->size) {
// 重新分配内存，栈容量加倍
stackData* p1 = (stackData*)realloc(head->val, sizeof(stackData) * head->size * 2);
assert(p1);
head->val = p1;
head->size *= 2;
}
head->val[head->top] = x;
head->top++;
}
// 出栈操作
stackData SKPop(stack* pHead) {
assert(pHead); // 确保栈指针有效
stack* head = pHead;
stackData date = head->val[head->top - 1];
head->top--;
return date;
}
// 销毁栈，释放栈中所有数据
void SKdestory(stack* pHead) {
while (pHead->top) {
SKPop(pHead); // 依次出栈，直到栈为空
}
}
// 获取栈的大小（栈中的元素个数）
int SKsize(stack* pHead) {
return pHead->top; // 栈顶指针即为栈的大小
}
// 判断栈是否为空
int SKEmpty(stack* pHead) {
return pHead->top == 0; // 如果栈顶指针为0，则栈为空
}
// 获取栈顶元素
stackData StackTop(stack* ps) {
assert(ps); // 确保栈指针有效
return ps->val[ps->top - 1]; // 返回栈顶元素
}
// 队列结构体定义
typedef struct {
stack* stack1; // 用于接收数据（入队）
stack* stack2; // 用于出数据（出队）
} MyQueue;
// 创建队列
MyQueue* myQueueCreate() {
// 为队列分配内存
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
// 初始化两个栈
SKinit(&obj->stack1); // 用于接收数据
SKinit(&obj->stack2); // 用于出数据
return obj; // 返回队列对象
}
// 入队操作，将元素x压入栈1
void myQueuePush(MyQueue* obj, int x) {
SKpush(obj->stack1, x); // 将数据压入栈1
}
// 出队操作，从栈2弹出元素
int myQueuePop(MyQueue* obj) {
// 如果栈2为空，将栈1中的元素转移到栈2
if (obj->stack2->top == 0) {
// 将栈1中的元素依次弹出并压入栈2
while (!SKEmpty(obj->stack1)) {
stackData n = SKPop(obj->stack1);
SKpush(obj->stack2, n);
}
}
// 从栈2中弹出元素并返回
return SKPop(obj->stack2);
}
// 查看队列头部元素
int myQueuePeek(MyQueue* obj) {
// 如果栈2为空，将栈1中的元素转移到栈2
if (obj->stack2->top == 0) {
while (!SKEmpty(obj->stack1)) {
stackData n = SKPop(obj->stack1);
SKpush(obj->stack2, n);
}
}
// 返回栈2的栈顶元素
return StackTop(obj->stack2);
}
// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
return (obj->stack2->top == 0) && (obj->stack1->top == 0); // 栈1和栈2都为空时，队列为空
}
// 销毁队列，释放所有资源
void myQueueFree(MyQueue* obj) {
// 一直出队直到队列为空
while (!myQueueEmpty(obj)) {
myQueuePop(obj);
}
// 释放栈1和栈2的内存
free(obj->stack1->val);
free(obj->stack2->val);
free(obj->stack1);
free(obj->stack2);
// 释放队列对象
free(obj);
}