当前位置：首页 > news >正文

数据结构--(栈、队列实现及3个OJ题)

news 来源：原创 2024/5/8 12:57:37

文章目录

1：队列的实现
- 1.1：初始化
- 1.2：销毁
- 1.3：入队列
- 1.4：出队列
- 1.5：取队列的头
- 1.6：取队列的尾
- 1.7：判空
- 1.8：取队列长度
2：栈的实现
- 1：初始化
- 2：销毁
- 3：入栈
- 4：出栈
- 5：判空
- 6：取size
- 7：取栈顶元素
3：OJ题
- 3.1：用队列实现栈
- 3.2：用栈实现队列
- 3.3：设计循环队列

1：队列的实现

1.1：初始化

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

1.2：销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	pq->_size = 0;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);

	}
	pq->head = pq->tail = NULL;
}

1.3：入队列

void QueuePush(Queue* pq, QDataType x)//尾插
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;

	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->_size++;
}

1.4：出队列

void QueuePop(Queue* pq)//头删
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else 
    {
	QNode* del = pq->head;
	pq->head = pq->head->next;
	free(del);
	del = NULL;


     }
	pq->_size--;
}

1.5：取队列的头

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

1.6：取队列的尾

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

1.7：判空

bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL && pq->tail == NULL;
}

1.8：取队列长度

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->_size;
}

2：栈的实现

1：初始化

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

2：销毁

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

3：入栈

void StackPush(ST* ps, STDateType x)
{
	if(ps->top == ps->capacity)
	{ 
		int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity * 2);
		STDateType* tmp = (STDateType*)realloc(ps->a, newcapacity*sizeof(STDateType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	++ps->top;
	
}

4：出栈

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

5：判空

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

6：取size

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

top是栈顶元素的下一个位置，因此top就是size大小。

7：取栈顶元素

STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//top是栈顶元素的下一个位置
}

3：OJ题

3.1：用队列实现栈

思路：栈是后进先出，队列是先进先出，因此我们的思路是用2个队列，一个为空，一个不为空。当非空队列元素数量大于1的时候，就把非空队列的元素push到空队列里面，然后pop掉非空队列队头的数据，依次循环直到非空队列元素为1，此时pop掉这个元素。

对于谁是空队列谁是非空我们不知道，可以默认队列1为非空，如果队列1不为空那就把非空的位置给队列2。

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


MyStack* myStackCreate() {
MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&obj->q1);
QueueInit(&obj->q2);

return obj;
}

void myStackPush(MyStack* obj, int x) {
if(!(QueueEmpty(&obj->q1)))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}

int myStackPop(MyStack* obj) {
Queue* empty = &obj->q1;
Queue* Noempty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
    empty = &obj->q2;
    Noempty = &obj->q1;
}
while(QueueSize(Noempty)>1)
{
    QueuePush(empty,QueueFront(Noempty));
QueuePop(Noempty);

}
int top = QueueFront(Noempty);
QueuePop(Noempty);
return top;
}

int myStackTop(MyStack* obj) {
if(!(QueueEmpty(&obj->q1)))
{
    return QueueBack(&obj->q1);
}
else
{
    return QueueBack(&obj->q2);
}
}

bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}

3.2：用栈实现队列

栈优先出栈顶元素，而队列想要pop1，这怎么办？

思路：定义2个栈，一个栈为专门出数据，一个专门为入数据，可以看到，当入数据的这个栈为空，就把出数据的栈里的所有数据导入到入数据的栈，然后再pop，就等于队列的先进先出。

typedef struct {
ST Pushstack;
ST Popstack;

} MyQueue;


MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->Pushstack);
StackInit(&obj->Popstack);
return obj;
}
void pushtopop(MyQueue* obj)
{
    if(StackEmpty(&obj->Popstack))
    {
        while(!StackEmpty(&obj->Pushstack))
        {
          StackPush(&obj->Popstack,StackTop(&obj->Pushstack));
          StackPop(&obj->Pushstack);
        }
    }
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->Pushstack,x);
}

int myQueuePop(MyQueue* obj) {
pushtopop(obj);
int front = StackTop(&obj->Popstack);
StackPop(&obj->Popstack);
return front;
}

int myQueuePeek(MyQueue* obj) {
pushtopop(obj);
return StackTop(&obj->Popstack);

}

bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->Popstack) && StackEmpty(&obj->Pushstack);
}

void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->Popstack);
StackDestroy(&obj->Pushstack);
free(obj);

}

3.3：设计循环队列

我们首先考虑使用哪种结构？

如果使用链表，back是末端元素的下一个位置，如果back在中间，取队尾元素就比较麻烦，因为要让back指向back的上一个节点，单链表不行，因此采用数组。

如果back到了末尾，继续++则越界，如何回到下标为0的位置？可以使用%=的运算方式。

代码实现如下：

typedef struct {
int* a;
int front;
int back;
int N;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int)*(k+1));
obj->front = obj->back = 0;
obj->N = k+1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front ==  obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
return ((obj->back+1) % obj->N) == obj->front;

}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
    return false;
}
else
{
    obj->a[obj->back] = value;
    obj->back++;
    obj->back %= obj->N;
    return true;
}
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
    return false;
}
else
{
  obj->front++;
  obj->front %= obj->N;   
  return true;
}

}

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

int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
    return -1;
}
else
{
    return obj->a[(obj->back+obj->N-1)% obj->N];
}
}



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