数据结构--栈和队列_假设栈的空间足够,head和tail

1.栈

1.1栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈内元素遵从先进后出的规则。压栈就是插入数据的操作，出栈就是删除数据的操作，都在栈顶实现。

1.2栈的实现

栈的实现可以由链表和数组分别实现，不过考虑到栈的特性，还是选择用数组来实现栈，因为数组在删除和添加尾部数据时消耗较少。

//栈的实现类似顺序表的实现
 
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int capacity;
	int top;
}ST;
 
void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//插入数据
void StackPop(ST* ps);//删除数据
bool StackEmpty(ST* ps);//判断栈是否为空
STDataType StackTop(ST* ps);//得到栈顶数据
int StackSize(ST* ps);//得到栈中元素个数

初始化函数

void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->top = 0;
}

销毁函数

void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

插入函数

void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    
    if(ps->capacity == ps->top)//判断是否满了，满了扩容
    {
        int newcapacity = ps->capacity==0 ? 4 : ps->capacity * 2;//防止栈原来为空
        ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
        ps->capacity = newcapacity;
    }
    
    ps->a[ps->top] = x;
    ps->top++;
}

删除数据

void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
//注意top得大于0，否则会越界访问

判断栈是否为空

bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
//判断是否为空，与删除数据密切相关，top不可能小于零，所以
//等于0时就为空返回true，不等于0时就返回false。

得到栈顶数据

STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top != 0);
    return ps->a[ps->top-1];
}
//注意top不能为0，如果为0则说明为空，不能返回值。

得到栈中元素个数

int StackSize(ST* PS)
{
    assert(ps);
    return ps->top;
}

1.3关于栈的习题

这道题用栈就很方便，创建出两个栈，将字符依次压栈，当遇到右符号时，停止压栈。记录栈顶符号，然后出栈。再与右符号进行对比，如果相同，字符串继续向下走直到字符为空；如果不同，直接返回false。

//要将栈的实现部分代码拷贝到这里，在这里不再拷贝
//copy code
//.......
 
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' ||    //压栈
        *s == '{' ||
        *s == '[')
        {
            StackPush(&st,*s);
            s++;
        }
 
        else                //比较
        {
            char top = StackTop(&st);
            StackPop(&st);
            if((*s==')' && top!='(') ||
            (*s == '}' && top!='{') ||
            (*s == ']' && top!='['))
            {
                StackDestory(&st);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
    StackDestory(&st);
    return true;
}

 如果这样就提交是会报错的！！有特殊情况没有考虑到！当字符串只有右字符或者左字符时，或者左右字符个数并不相等时，这样的写法是不对的！

//要将栈的实现部分代码拷贝到这里，在这里不再拷贝
//copy code
//.......
 
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' ||
        *s == '{' ||
        *s == '[')
        {
            StackPush(&st,*s);
            s++;
        }
 
        else
        {
           //当全为右括号，或者右括号数大于左括号时，应返回false，如果不加这一步，则会返回true
            if(StackEmpty(&st))
                return false;
 
            char top = StackTop(&st);
            StackPop(&st);
            if((*s==')' && top!='(') ||
            (*s == '}' && top!='{') ||
            (*s == ']' && top!='['))
            {
                StackDestory(&st);
                return false;
            }
            else
            {
                s++;
            }
        }
    }
//当全为左括号，或者左括号数大于右括号时，应返回false，而且正常进行到这一步时
//栈就应该为空。应该是true。
    bool ret = StackEmpty(&st);
 
    StackDestory(&st);
    return ret;
}

2.队列

2.1队列的概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，具有先进先出的规则。进行插入操作的一端称为队尾，进行删除操作的一端称为对头。

2.2队列的实现

//队列的实现就是用单链表实现的，
//在此创建了两个结构体，一个是用来放结点的内容
//另一个是用来放队列的头结点和尾结点，创建尾结点便于后面的插入数据的操作
 
 
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
 
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq,QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

初始化函数

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

销毁函数

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

插入函数

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
 
	//建立新结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
 
	newnode->val = x;
	newnode->next = NULL;
 
    //防止head和tail为空
	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->tail = pq->head = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

删除函数

void QueuePop(Queue* pq)
{
	assert(pq);//放头尾指针的结构体不能为空
    QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
}

 这样写对不对？这样写只考虑到了队列里不为空的情况，如果head和tail均为空，那么久使用空指针了，就会发生错误；还有一种情况就是当队列中只有一个元素时，删完元素后，next为空，这时head是赋了NULL不错，但tai还指向被释放的空间，那他l是不是就变成野指针了？所以要避免野指针的情况发生！

 

void QueuePop(Queue* pq)
{
	assert(pq);//放头尾指针的结构体不能为空
	assert(pq->head && pq->tail);//队列不能为空
 
	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;
	}
}

判断队列是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->tail == NULL;
}
//在这里用head.tail判断是否为NULL都可以，
//只要有一个为NULL，就为空。

获得队列元素个数

size_t QueueSize(Queue* pq)
{
	assert(pq);
 
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

得到队头元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
 
	return pq->head->val;
}

得到队尾元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);
 
	return pq->tail->val;
}

2.3关于队列的习题

2.3.1 用栈实现队列

 

 思路：用两个栈来实现队列。首先要清楚栈和队列的特点，栈的特点是先进后出，队列的特点是先进先出。一个栈用来“入队”，另一个栈用来“出队”。入队的时候就将全部数据装到pushQ中；出栈的时候将pushQ中的数据全部放到popQ中，然后用stack的出栈即可。需要注意的是，出队的时候不是每次都要将pushQ中的数据放到popQ中，而是当popQ中没有数据时才将数据放入popQ中的。

//要将栈的实现部分代码拷贝到这里，在这里不再拷贝
//copy code
//.......
 
 
typedef struct {
    ST pushQ；
    ST popQ;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
    MyQueue* qp = (MyQueue*)malloc(sizeof(MyQueue));
    assert(qp);
 
    StackInit(&qp->pushQ);
    StackInit(&qp->popQ);
 
    return qp;
}
 
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushQ,x);
}
 
int myQueuePop(MyQueue* obj) {
    assert(obj);
    int top = 0;
 
    if(StackEmpty(&obj->popQ))
    {
        while(!StackEmpty(&obj->pushQ))
        {
            top = StackTop(&obj->pushQ);
            StackPop(&obj->pushQ);
            StackPush(&obj->popQ,top);
        }
        top = StackTop(&obj->popQ);
        StackPop(&obj->popQ);
    }
    else
    {
        top = StackTop(&obj->popQ);
        StackPop(&obj->popQ);        
    }
 
    return top;
}
 
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    int top = 0;
 
    if(StackEmpty(&obj->popQ))
    {
        while(!StackEmpty(&obj->pushQ))
        {
            top = StackTop(&obj->pushQ);
            StackPop(&obj->pushQ);
            StackPush(&obj->popQ,top);
        }
        top = StackTop(&obj->popQ);
    }
    else
    {
        top = StackTop(&obj->popQ);      
    }   
 
    return top;
}
 
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
 
    return StackEmpty(&obj->pushQ) && StackEmpty(&obj->popQ);
}
 
void myQueueFree(MyQueue* obj) {
    assert(obj);
 
    StackDestory(&obj->pushQ);
    StackDestory(&obj->popQ);
 
    free(obj);
}

 2.3.2 用队列实现栈

 

 思路：要用队列模拟栈，要充分利用栈和队列的特点。栈是先进后出，那在初始就将数据先放到一个空队列中。如果要出数据，就开始让数据出队，入队到另一个队列中去。当这个队列中只剩一个数据时，停止出队并将这个数据pop掉；如果要输入数据，就将数据输入到一个·不为空的队列中去。（初始随便进入）。

//要将队列的实现部分代码拷贝到这里，在这里不再拷贝
//copy code
//.......
 
 
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
 
 
MyStack* myStackCreate() {
    //得到两个队列
    MyStack* dst = (MyStack*)malloc(sizeof(MyStack));
    assert(dst);
 
    //初始化队列
    QueueInit(&dst->q1);
    QueueInit(&dst->q2);
 
    return dst;
}
 
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);
 
    //假设空队列是q1，判断，如果不是，则交换。
    Queue* EmptyQ = &obj->q1;
    Queue* NonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        EmptyQ = &obj->q2;
        NonemptyQ = &obj->q1;
    }
 
    while(QueueSize(NonemptyQ)>1)
    {
        int top = QueueFront(NonemptyQ);
        QueuePush(EmptyQ,top);
        QueuePop(NonemptyQ);
    }
    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);
 
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
 
    free(obj);
}

 2.3.3 循环队列

 循环队列无非就是在逻辑上实现队列的循环，在这里选择使用数组来实现循环队列。但循环队列的容量是有限的，只有还有多余空间时才能插入数据，如果满了就不能插入数据了。

 因此必须想出一种方法，就是在开辟空间时，多开辟一个空间，不存放数据只为了判断队列是否已经满了。条件就是back的下一个是否就为front。（要注意back在最后面，front在最前面的情况，这时他们两个相差size）。而判断队列为空的条件就是back与front相等。在写程序时要时刻注意back或者front是否走到了数组最后！！

typedef struct {
    int* a;
    int front;
    int back;
    int size;
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    assert(pst);
    pst->a = (int*)malloc(4 * (k + 1));
    assert(pst->a);
    pst->size = k;
    pst->front = pst->back = 0;
 
    return pst;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
 
    //判断队列是否满了
    if ((obj->front - obj->back) != 1 && (obj->back - obj->front) != obj->size)
    {
        obj->a[obj->back] = value;
        //判断是否到数组尾部
        if (obj->back != obj->size)
        {
            obj->back++;
        }
        else
        {
            obj->back = 0;
        }
        return true;
    }
    else
    {
        return false;
    }
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
 
    //判断队列是否为空
    if (obj->front == obj->back)
    {
        return false;
    }
    else
    {
        //判断是否到了数组尾部
        if (obj->front != obj->size)
            obj->front++;
        else
            obj->front = 0;
 
        return true;
    }
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
 
    if (obj->front != obj->back)
    {
        return obj->a[obj->front];
    }
    else
    {
        return -1;
    }
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    int back = 0;
 
 
    if (obj->front != obj->back)
    {
        
        //判断back是否在数组头部
        if (obj->back != 0)
        {
            back = obj->back - 1;
        }
        else
        {
            back = obj->size;
        }
        return obj->a[back];
    }
    else
    {
        return -1;
    }
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
 
    if (obj->front == obj->back)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
 
    if ((obj->front - obj->back) == 1 || (obj->back - obj->front) == obj->size)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
 
    free(obj->a);
    obj->front = obj->back = obj->size = 0;
    free(obj);
}

 注意，

1.back每次是指向加入的数据之后的那个位置，因此在打印尾部数据时要注意不能直接使用back指向的数据；

2.在删除数据时，不需要给数据赋值，只需要front++,但是要注意front是否在数组最后，如果是的话，就让他等于0；

3.数组内有一个位置一定是空的。