栈和队列

栈和队列本质也是线性表。特殊在于它们的操作受到一些限制。

1. 栈

1.1 栈的定义

栈只允许在栈顶进行插入和删除。另一端被称为栈底。栈的元素遵循后进先出的原则。

后进先出，先进后出，即LIFO原则（Last In First Out）。

压栈：栈的插入操作被称为压栈，也可以叫做进栈、入栈。
出栈：栈的插入操作被称为出栈，或称弹栈。

数据出入都在栈顶，类似于子弹上膛和发射。元素像子弹一样被压入弹夹，再一个个地打出去，这个过程便是压栈和出栈。

栈的结构定义

栈可以使用数组和链表实现。数组栈比链式栈的结构优势更大一点。

数组进行尾插尾删的效率高，其次缓存命中率高。缺点是动态增容有一定的内存消耗。

typedef struct stack
{
	int* _a;
	size_t _top;
	size_t _cap;
}stack;

1.2 栈的实现

初始化销毁

void stack_init(stack* s)
{
	assert(s);
	s->_a = NULL;
	s->_top = s->_cap = 0;
}

void stack_destroy(stack* s)
{
	free(s->_a);
	s->_a = NULL;
	s->_top = s->_cap = 0;
}

top一般初始化为0。top总是下一个插入位置的下标，也代表栈元素个数。

压入弹出

void stack_push(stack* s, int n)
{
	assert(s);

	if (s->_top == s->_cap || s->_cap == 0)
	{
		size_t nc = s->_cap == 0 ? 4 : s->_cap * 2;

		int* p = (int*)malloc(nc * sizeof(int));
		if (p != NULL)
		{
			memcpy(p, s->_a, s->_top * sizeof(int));
			free(s->_a);

			s->_a = p;
			s->_cap = nc;
		}
	}
	s->_a[s->_top++] = n;
}

void stack_pop(stack* s)
{
	assert(s && s->_top > 0);
	s->_top--;
}

获取栈顶

int stack_top(stack* s)
{
	assert(s && s->_top > 0);
	return s->_a[s->_top - 1];
}

top-1为当前栈顶的下标。同样要保证栈非空。加上该测试函数，可以实现循环打印栈元素的功能。

元素个数和判空

size_t stack_size(stack* s)
{
	assert(s);
	return s->_top;
}

int stack_empty(stack* s)
{
	return !stack_size(s);
}

2. 队列

2.1 队列的定义

队列只允许在队尾进行插入，在队头进行删除。队列的元素遵循先进先出的原则。先进先出，后进后出，即FIFO原则。

队列的结构定义

typedef struct _queue_node
{
	int _data;
	struct _queue_node* _next;
} qnode;

typedef struct _queue
{
	qnode* _head;
	qnode* _tail;
	int _size;
}queue;

队列的底层结构采用链表，方便头删元素。
队列用两个指针标识队头队尾，方便访问队头和队尾元素。

2.2 队列的实现

初始化销毁

void queue_init(queue* q)
{
	q->_size = 0;
	q->_head = q->_tail = NULL;
}

void queue_destroy(queue* q)
{
	qnode* cur = q->_head;
	while (cur)
	{
		qnode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_size = 0;
	q->_head = q->_tail = NULL;
}

入队出队

void queue_push(queue* q, int n)
{
	qnode* p = (qnode*)malloc(sizeof(qnode));
	if (p)
	{
		p->_data = n;
		p->_next = NULL;
	}

	if (!q->_tail)
	{
		q->_head = q->_tail = p;
	}
	else
	{
		q->_tail->_next = p;
		q->_tail = p;
	}
	q->_size++;
}

void queue_pop(queue* q)
{
	q->_head = q->_head->_next;
	q->_size--;
}

tail队尾后再链上新结点，再将tail指针指向新结点。出队是将head指针指向下一个结点并将头节点释放掉即可。

获取头尾

int queue_front(queue* q)
{
	return q->_head->_data;
}

int queue_back(queue* q)
{
	return q->_tail->_data;
}

元素个数和判空

int queue_size(queue* q)
{
	return q->_size;
}
int queue_empty(queue* q)
{
	return q->_size == 0;
}

3. OJ题

1 判断有效括号

给定一个只包括 (,),{,},[,] 的字符串 s ，判断字符串是否有效。

bool isValid(char* s) {
    ST st;
    StackInit(&st);
    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            StackPush(&st, *s);
        }
        else {
            //栈无元素，无法与右括号匹配
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }
            STDataType ret = StackTop(&st);
            if ((ret == '(' && *s != ')') ||
                (ret == '[' && *s != ']') ||
                (ret == '{' && *s != '}'))
            {
                StackDestroy(&st);
                return false;
            }
            else {
                StackPop(&st);
            }
        }
        s++;
    }
    if (StackEmpty(&st)) {
        StackDestroy(&st);
        return true;
    }
    else {
        StackDestroy(&st);
        return false;
    }
}

利用栈的先进后出，后进先出的特点。

将字符串s从前向后遍历将其中所有左括号依次入栈，
等待遇到右括号时再利用后进先出的特点就可将最近的左括号与右括号对比。
若匹配成功则出栈一次，下一次就可以找到前一个左括号与之后的右括号进行匹配。

2 队列实现栈

使用两个队列实现一个后入先出的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）

如用数组用链表实现，换成用队列实现栈。即利用队列的结构和接口函数，也就是队列的特点实现出一个结构，该结构具有栈的特点。

typedef struct {
	Queue q1;
	Queue q2;
} MyStack;

MyStack* myStackCreate() {
	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	if (st == NULL)
		exit(-1);

	QueueInit(&st->q1);
	QueueInit(&st->q2);
	return st;
}
//调用函数创建堆区结构体并返回

void myStackPush(MyStack* obj, int x) {
	assert(obj);
	//向非空队列Push
	if (!QueueEmpty(&obj->q1))
		QueuePush(&obj->q1, x);
	else
		QueuePush(&obj->q2, x);
}

int myStackPop(MyStack* obj) {
	assert(obj);
    // 定义空与非空队列
	Queue* emptyQ = &obj->q1;
	Queue* nonEmptyQ = &obj->q2;
	if (!QueueEmpty(&obj->q1)) {
		nonEmptyQ = &obj->q1;
		emptyQ = &obj->q2;
	}

	//将非空队列前n-1个元素Push到空队列
	while (QueueSize(nonEmptyQ) > 1) {
		QueuePush(emptyQ, QueueFront(nonEmptyQ));
		QueuePop(nonEmptyQ);
	}

	//Pop最后一个元素并返回
	int top = QueueFront(nonEmptyQ);
	QueuePop(nonEmptyQ);
	return top;
}

int myStackTop(MyStack* obj) {
	assert(obj);
    //返回非空队列队尾元素
	if (!QueueEmpty(&obj->q1))
		return QueueBack(&obj->q1);
	else
		return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) {
	assert(obj);
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); //二者皆空才为空
}

void myStackFree(MyStack* obj) {
	assert(obj);
	QueueDestroy(&obj->q1); //释放队列结点
	QueueDestroy(&obj->q2); //释放结构体

    free(obj);
}

Push，由于栈和队列都是从固定的一端入，故模拟入栈直接向非空队列入即可。

Pop，模拟出栈时，就要考虑到二者的不同，先删除队列中的前$n-1$个元素并将其入到另一个空队列中。直至第$n$个元素再将其删除。

队头出数据，队尾入数据，正好能将非空队列前$n$个元素按照原顺序插入到空队列中。非空队列仅剩最后一个元素再删除掉。将所插队列视为出栈后的栈，便实现模拟出栈的过程。

Top，直接调用队列读取队尾元素的接口函数即可。

完成任意操作后都会产生一个空队列和一个非空队列。通过加以判断可以将非空队列视为待操作对象。也就是每次操作都是操作非空队列。

3 栈实现队列

使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

/**
 * 结构体定义
 **/
typedef int STDataType;
typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;
typedef struct {
    ST pushST;
    ST popST;
} MyQueue;

/**
 * 接口函数定义
 **/
MyQueue* myQueueCreate() {
    MyQueue* pq= (MyQueue*)malloc(sizeof(MyQueue));
    if (pq == NULL) {
        exit(-1);
    }
    StackInit(&pq->pushST);
    StackInit(&pq->popST);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST, x);
}

int myQueuePop(MyQueue* obj) {
    //出栈为空，将入栈所有元素移到出栈
    if (StackEmpty(&obj->popST)) {
        while (!StackEmpty(&obj->pushST)) {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //删除栈顶即队头元素
    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    //出栈为空，将入栈所有元素移到出栈
    if (StackEmpty(&obj->popST)) {
        while (!StackEmpty(&obj->pushST)) {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //返回栈顶即队头元素
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
	free(&obj->pushST);
    free(&obj->popST);
    free(obj);
}

由于栈的特点后进先出，将栈中元素移入另一个栈中会造成“逆置”的现象。此时将元素插入到非空栈中会导致顺序发生错误。故指定两个栈分别为入栈pushST和出栈popST，分别负责入栈和出栈。

Push，将直接将元素插入到负责入栈的pushST中。

Pop，popST为空，就将pushST的元素移到popST。再从popST栈顶出栈就等于删除pushST的栈底元素。

将元素从“入栈”移到“出栈”，等于将元素逆置，逆置后的栈出栈操作而言已然和队列的出队一样。相当于将栈底的元素从栈底出栈，也就是从先进后出变成先进先出，模拟实现了出队。

入栈pushST和出栈popST互不影响，分别完成入队的出队的任务。只要popST为空，就将pushST中元素移入即可。

4 实现循环队列

循环队列可由数组和链表两种方式实现，数组则是通过下标循环，链表是循环链表。

循环队列同样是队列，满足队列的所有性质，
循环队列空间大小固定且可重复利用，
需要多开辟一个元素的空间以用于判满。

由图可得tail->next==head即队列满，tail==head即队列空。数组利用下标控制即可。利多开一块的空间来判满。

数组实现

/**
 * 结构体定义
 **/
typedef struct {
    int* a;
    int front;
    int tail;
    int k;
} MyCircularQueue;
/**
 * 接口函数定义
 **/
MyCircularQueue* myCircularQueueCreate(int k) {
    //为结构体开辟空间
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //开辟数组
	cq->a = (int*)malloc((k + 1) * sizeof(int));
    cq->k = k;
    cq->front = cq->tail = 0;
    return cq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    //插入判断非满
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->a[obj->tail] = value;
    obj->tail++;
    //回到数组中对应位置
    obj->tail %= obj->k + 1;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    //删除判断非空
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
    obj->front++;
    obj->front %= obj->k + 1;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    /*
    if (obj->tail == 0)
        return obj->a[obj->k];
    else
    	return obj->a[obj->tail - 1];
    */
    int i = (obj->tail + obj->k) % (obj->k + 1);
    return obj->a[i];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    /*
    if (obj->tail == obj->k)
        return obj->front == 0;
    else
        return obj->tail + 1 == obj->front;
    */
    return obj->tail % (obj->k + 1) == obj->front;
    //tail % (K + 1) + 1 == front
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    free(obj->a);
    free(obj);
}

数组实现，必须要考虑下标溢出的问题。当下标在数组内时，模等上数组长度其值不受影响，当下标溢出时，模等上数组长度就回到数组内对应位置。

下标溢出几个单位，模等数组长度后就会回到数组内第几位。

链表实现

typedef int SLTDataType;

typedef struct SLTNode {
	SLTDataType data;
	struct SLTNode* next;
}SLTNode;

typedef struct {
	SLTNode* head;
	SLTNode* tail;
	int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	if (pq == NULL)
		exit(-1);
 	pq->k = k;
	//开辟链表
	pq->head = SListNewNode();
	pq->tail = pq->head;
	while (k--) {
		pq->tail->next = SListNewNode();
		pq->tail = pq->tail->next;
	}
	//头尾相连
	pq->tail->next = pq->head;
	//初始化指针
	pq->tail = pq->head;

	return pq;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	assert(obj);
	if (myCircularQueueIsFull(obj)) {
		return false;
	}
	SListInsert(obj->tail, value);
	obj->tail = obj->tail->next;
	return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	assert(obj);
	if (myCircularQueueIsEmpty(obj)) {
		return false;
	}
	obj->head = obj->head->next;
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
	assert(obj);
	if (myCircularQueueIsEmpty(obj)) {
		return -1;
	}
	return obj->head->data;
}

int myCircularQueueRear(MyCircularQueue* obj) {
	assert(obj);
	if (myCircularQueueIsEmpty(obj)) {
		return -1;
	}
	SLTNode* cur = obj->head;
	while (cur->next != obj->tail) {
		cur = cur->next;
	}
	return cur->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	assert(obj);
	return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	assert(obj);
	return obj->tail->next == obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
	assert(obj);
	SLTNode* cur = obj->head;
	while (cur->next != obj->head) {
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
	free(obj);
}

栈和队列 ​

1. 栈 ​

1.1 栈的定义 ​

栈的结构定义 ​

1.2 栈的实现 ​

初始化销毁 ​

压入弹出 ​

获取栈顶 ​

元素个数和判空 ​

2. 队列 ​

2.1 队列的定义 ​

队列的结构定义 ​

2.2 队列的实现 ​

初始化销毁 ​

入队出队 ​

获取头尾 ​

元素个数和判空 ​

3. OJ题 ​

1 判断有效括号 ​

2 队列实现栈 ​

3 栈实现队列 ​

4 实现循环队列 ​

数组实现 ​

链表实现 ​

栈和队列

1. 栈

1.1 栈的定义

栈的结构定义

1.2 栈的实现

初始化销毁

压入弹出

获取栈顶

元素个数和判空

2. 队列

2.1 队列的定义

队列的结构定义

2.2 队列的实现

初始化销毁

入队出队

获取头尾

元素个数和判空

3. OJ题

1 判断有效括号

2 队列实现栈

3 栈实现队列

4 实现循环队列

数组实现

链表实现