Directory
1. Stack
1.1 The concept of stack
1.2 Interface implementation of the stack
Two, the queue
2.1 The concept of queue
2.2 Interface Implementation of Queue
2.3 Difference between stack and queue
3. Stack and queue LeetCode exercises
3.1 Lituo_232. Realize queue with stack
3.2 Lituo_225. Using queues to implement stacks
3.3 Leetour_622. Design Circular Queue
3.4 Leetcode_20. Valid parentheses
one, stack
Friends who are learning data structures for the first time should not think that the stack is difficult, it is actually quite simple. Just make it clear: “Last in, first out, first in, last out” and it’s OK!
1.1 The concept of stack
For the data whose logical relationship is “one-to-one”, in addition to using sequential tables and linked lists, it can also be stored in a stack structure.
The stack is a “special” linear storage structure, and its special features are reflected in the following two places:
1. The operation of pushing elements into and out of the stack can only be done from one end, and the other end is closed, as shown in the following figure:
Usually, we refer to the process of pushing elements into the stack as “push”, “push” or “push” for short; the process of popping elements out of the stack is simply called “pop” or “pop”.
2. Regardless of storing or fetching data in the stack, the principle of “first in, last out” must be followed, that is, the element that is pushed into the stack first is popped out first. Take the stack in the above figure as an example, it is easy to see that element 1 is pushed onto the stack first, and then elements 2, 3, and 4 are pushed onto the stack in turn. On this basis, if you want to take out element 1, according to the principle of “first in, last out”, you must first pop elements 4, 3, and 2 out of the stack in turn, and then it is the turn of element 1 to pop out of the stack.
We are used to calling the open end of the stack the top of the stack, and the closed end the bottom of the stack.
From this, we can define the stack storage structure: a stack is a linear storage structure that “elements can only be accessed from one end, and the access process must follow the principle of ‘first in, last out'”.
1.2 Stack interface implementation
//Stack.h file
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int DataType;
typedef struct Stack
{
DataType* data;
int top;
int capacity;
}st;
//Initialize the stack
void STInit(ST* pst);
//Push into the stack
void STPush(ST* pst, DataType x);
// pop out
void STPop(ST* pst);
// stack destruction
void STDestory(ST* pst);
//get the top element of the stack
DataType STGetTop(ST* pst);
// Check if the stack is empty
bool STEmpty(ST* pst);
//The size of the stack - the number of elements
int STSize(ST* pst);
//Stack.c file
#include "Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->data = NULL;
pst->top = 0;
pst->capacity = 0;
}
void STPush(ST* pst, DataType x)
{
assert(pst);
//Expansion
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
DataType* tmp = (DataType*)realloc(pst->data, sizeof(DataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail!\
");
return;
}
pst->data = tmp;
pst->capacity = newCapacity;
}
//Push into the stack
pst->data[pst->top] = x;
pst->top++;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
void STDestory(ST* pst)
{
assert(pst);
free(pst->data);
pst->data = NULL;
pst->top = 0;
pst->capacity = 0;
}
DataType STGetTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->data[pst->top - 1];
}
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
two, queue
2.1 The concept of queue
The queue is used to store data with a logical relationship of “one-to-one”, and is a “special” linear storage structure. Compared with sequential lists and linked lists, the particularity of queues is reflected in the following two aspects:
1. Elements can only enter from one end of the queue and exit from the other end, as shown in the following figure:
Usually, we call the end where elements enter the queue as “queue tail”, and the process of entering the queue is called “enqueue”; the end that takes elements out of the queue is called is “queue head”, and the process of dequeuing is called “dequeuing”.
2. The entry and exit of each element in the queue must follow the principle of “First in, first out”, that is, the element that enters the queue first must leave the queue first.
Take the queue shown in the above figure as an example. It is not difficult to judge from the storage status of each element in the queue. Element 1 enters the queue first, then element 2 enters the queue, and finally element 3 enters the queue. If you want to dequeue element 3 at this time, according to the “first in, first out” principle, elements 1 and 2 must be dequeued first, and then element 3 can be dequeued at last.
2.2 Queue interface implementation
//Queue.h file
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType;
typedef struct QNode
{
DataType data;
struct QNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
} Queue;
//Initialize the queue
void QueueInit(Queue* pq);
//destroy the queue
void QueueDestory(Queue* pq);
//enqueue
void QueuePush(Queue* pq, DataType x);
//dequeue
void QueuePop(Queue* pq);
//queue head element
DataType QueueFront(Queue* pq);
// tail element
DataType QueueBack(Queue* pq);
//The size of the queue
int QueueSize(Queue* pq);
// Check if the queue is empty
bool QueueEmpty(Queue* pq);
//Queue.c file
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, DataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail!\
");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
assert(pq->ptail == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size + + ;
}
void QueuePop(Queue* pq)
{
assert(pq);
// no node
assert(!QueueEmpty(pq));
// only one node
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = NULL;
pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
DataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->data;
}
DataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL & amp; & amp; pq->ptail == NULL;
}
2.3 Difference between stack and queue
Do not confuse the stack with the queue. The stack is open at one end and closed at the other end. Elements are pushed into and out of the stack following the principle of “first in, last out”; the queue is open at both ends, but elements can only enter from one end , exit from the other end, and the entry and exit queues follow the principle of “first in, first out”.
3. Stack and queue LeetCode exercises
3.1 Leek_232. Implementing queues with stacks
typedef struct {
ST Push ST;
ST PopST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit( & obj->PushST);
STInit( & obj->PopST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush( & obj->PushST, x);
}
int myQueuePop(MyQueue* obj) {
int ret = myQueuePeek(obj);
STPop( & obj->PopST);
return ret;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty( &obj->PopST))
{
while(!STEmpty( &obj->PushST))
{
STPush( &obj->PopST, STGetTop( &obj->PushST));
STPop( & obj->PushST);
}
}
return STGetTop( & amp; obj->PopST);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty( & amp;obj->PushST) & amp; & amp; STEmpty( & amp;obj->PopST);
}
void myQueueFree(MyQueue* obj) {
STDestory( & obj->PushST);
STDestory( & obj->PopST);
free(obj);
}
3.2 Likou_225. Implement stack with queue
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( & amp; obj->q1, x);
}
else {
QueuePush( & amp; obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* EmptyQ = &obj->q1;
Queue* NoEmptyQ = &obj->q2;
if(!QueueEmpty( &obj->q1))
{
EmptyQ = &obj->q2;
NoEmptyQ = & obj->q1;
}
while(QueueSize(NoEmptyQ) > 1)
{
QueuePush(EmptyQ, QueueFront(NoEmptyQ));
QueuePop(NoEmptyQ);
}
int top = QueueFront(NoEmptyQ);
QueuePop(NoEmptyQ);
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty( &obj->q1))
{
return QueueBack( & amp; obj->q1);
}
else
{
return QueueBack( & amp; obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty( & amp; obj->q1) & amp; & amp; QueueEmpty( & amp; obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestory( & obj->q1);
QueueDestory( & obj->q2);
free(obj);
}
3.3 Rikou_622. Design Circular Queue
typedef struct {
int front;
int rear;
int k;
int* a;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k + 1));
if(obj == NULL)
{
perror("malloc fail!\
");
return NULL;
}
obj->front = obj->rear = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->rear] = value;
obj->rear ++ ;
obj->rear %= (obj->k + 1);
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front + + ;
obj->front %= (obj->k + 1);
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(!myCircularQueueIsEmpty(obj))
return obj->a[obj->front];
else
return -1;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(!myCircularQueueIsEmpty(obj))
return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
else
return -1;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}
3.4 Ritual_20. Valid brackets
bool isValid(char * s)
{
ST st;
STInit( &st);
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{')
{
STPush( &st, *s);
}
else
{
if(STEmpty( &st))
{
STDestory( &st);
return false;
}
char top = STGetTop( &st);
STPop( & st);
if(*s == ')' & amp; & amp; top != '('
|| *s == ']' & amp; & amp; top != '['
|| *s == '}' & amp; & amp; top != '{')
{
STDestory( &st);
return false;
}
}
s++;
}
bool ret = STEmpty( &st);
STDestory( &st);
return ret;
}