数据结构之栈和队列-EW帮帮网

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

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;
	else
		return 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;
    else
        return 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;
	else
		return 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;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(((obj->rear+1)%(obj->k+1)) == obj->front)
        return true;
    else
        return 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];
        else
            return 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);
*/

4. 简要总结

栈是先入后出，队列是先入先出；
用数组实现栈，用链表实现队列。

数据结构之栈和队列

1. 栈

1.1 概念与结构

1.2 栈的实现

2. 队列

2.1 队列的概念及结构

2.2 队列的实现

3. 栈和队列的练习

4. 简要总结

网站公告

今日签到

热门文章

最新发布