数据结构 | 栈与队列

栈:

栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶(TOP)，另一端为栈底(BOTTOM)。 当表中没有元素时称为栈空。 栈顶元素总是后被插入(入栈)的元素，从而也是最先被移除(出栈)的元素；栈底元素总是最先被插入的元素，从而也是最后才能被移除的元素。所以栈是个 后进先出(LIFO) 的数据结构

栈的基本运算有三种：入栈、出栈与读栈顶，时间复杂度都是O(1)

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

#define MaxSize 20

typedef struct _Stack
{
	char * top; // 栈首指针
	char * end; // 栈尾指针
}Stack , *pStack;

// ====================顺序栈的功能封装=====================================
void InitStack (pStack *p);          // 初始化指针        
void PushStack (pStack , char ch); // 压栈
void PopStack (pStack p , char *ch);//出栈
int LenStack (pStack p );           // 栈的长度
void TraStack (pStack p);           // 遍历栈区
void DestroyStack (pStack p);       // 释放栈区

int main ()
{
	pStack one = (pStack) malloc (sizeof(Stack));
	InitStack (one);


	DestroyStack (one);
	return 0;
}


void InitStack (pStack *p )
{
	(*p)->top = (char *)malloc(sizeof(char)*MaxSize);
	(*p)->end = (*p)->top;
}



void PushStack (pStack p , char ch)
{
	*(p->end) = ch;
	p->end++;
}

void PopStack (pStack p , char *ch)
{
	p->end--;
	(*ch)=*(p->end);
}



int LenStack (pStack p )
{
	int i=0 ;
	char * pl=p->top;
	while (pl!=p->end)
	{
		pl++;
		i++;
	}

	return i;
}

void TraStack (pStack p)
{
	char * str;
	str = p->top;

	while (str != p->end)
	{
		printf ("%c -> " , *str);
		str++;
	}
	printf ("End\n");
}

void DestroyStack (pStack p)
{
	free (p->top);
}

队列：

队列是只允许在一端删除，在另一端插入的顺序表，允许删除的一端叫做队头，用对头指针 frontfront 指向对头元素的下一个元素。 允许插入的一端叫做队尾，用队尾指针 rearrear 指向队列中的队尾元素。 因此，从排头指针 frontfront 指向的下一个位置直到队尾指针 rearrear 指向的位置之间所有的元素均为队列中的元素。

传统形式的队列机制使用链表更加合适，使得内存得到合理的利用和释放。

#ifndef queue_Header_h
#define queue_Header_h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//队列的结点结构
typedef struct Node{
    int data;
    struct Node *next;
} Node, *Queue;

//队列的结构，嵌套
typedef struct{
    Queue front;
    Queue rear;
} LinkQueue;

//初始化
//开始必然是空队列，队尾指针和队头指针都指向头结点
void initQueue(LinkQueue *queue)
{
    //初始化头结点
    queue->front = queue->rear = (Queue)malloc(sizeof(Node));

    if (NULL == queue->front) {
        exit(0);
    }

    queue->front->next = NULL;
}

//判空
bool isEmpty(LinkQueue queue)
{
    return queue.rear == queue.front ? true : false;
}

//入队,只在一端入队，另一端出队，同样入队不需要判满
void insertQueue(LinkQueue *queue, int temp)
{
    Queue q = (Queue)malloc(sizeof(Node));

    if (NULL == q) {
        exit(0);
    }
    //插入数据
    q->data = temp;
    q->next = NULL;
    //rear 总是指向队尾元素
    queue->rear->next = q;
    queue->rear = q;
}

//出队，需要判空
void deleteQueue(LinkQueue *queue)
{
    Queue q = NULL;

    if (!isEmpty(*queue)) {
        q = queue->front->next;
        queue->front->next = q->next;
        //这句很关键，不能丢
        if (queue->rear == q) {
            queue->rear = queue->front;
        }

        free(q);
    }
}

//遍历
void traversal(LinkQueue queue)
{
    int i = 1;
    Queue q = queue.front->next;

    while (q != NULL) {
        printf("队列第%d个元素是：%d\n", i, q->data);
        q = q->next;
        i++;
    }
}

//销毁
void destoryQueue(LinkQueue *queue)
{
    while (queue->front != NULL) {
        queue->rear = queue->front->next;
        free(queue->front);
        queue->front = queue->rear;
    }

    puts("销毁成功！");
}

#endif

循环队列:

普通的队列只能使用链表的形式来实现，如果是使用数组来实现，过程中由于在单方向自曾问题将导致最终栈溢出。

如果想要通过数组来实现队列，则可以考虑循环队列的方式。

但是循环队列需要区分空队列还是满队列。

这是空循环队列的样子：

这是满循环队列的样子:

解决办法：

1. 另设一个布尔变量以区别队列的空和满；
2. 少用一个元素的空间，约定入队前测试尾指针在循环下加 1 后是否等于头指针，若相等则认为队满；（最常用）
3. 使用一个计数器记录队列中元素的总数。

#ifndef ___queue_Header_h
#define ___queue_Header_h
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5

typedef struct{
    int *base;
    int rear;//如果队列不空，指向队尾元素的下一个位置
    int front;//初始的时候指向表头
} CirularQueue;

//初始化
void initQueue(CirularQueue *queue)
{
    queue->base = (int *)malloc(MAX_SIZE*sizeof(int));

    if (NULL == queue->base) {
        exit(0);
    }

    queue->front = queue->rear = 0;
}

//求长度
int getLength(CirularQueue queue)
{
    //这样把所以的情况都考虑到了
    return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE;
}

//入队，先判满
void insertQueue(CirularQueue *queue, int e)
{
    if ((queue->rear + 1) % MAX_SIZE == queue->front) {
        puts("循环队列是满的！");
    }
    else
    {
        queue->base[queue->rear] = e;
        queue->rear = (queue->rear + 1) % MAX_SIZE;
    }
}

//出队
void deleteQueue(CirularQueue *queue)
{
    if (queue->front == queue->rear) {
        puts("队列是空的！");
    }
    else
    {
        queue->front = (queue->front + 1) % MAX_SIZE;
    }
}

//遍历
void traversal(CirularQueue queue)
{
    int q = queue.front;

    for (int i = 0; i < getLength(queue); i++) {
        printf("循环队列的第%d个元素为%d\n", i + 1, queue.base[q]);
        q++;
    }
}

#endif