数据结构-栈和队列的多种实现方法
程序员文章站
2022-07-14 14:25:04
...
循环队列
typedef struct {
int *base;
int capacity;
int front;
int rear;
} MyCircularQueue;
/** Initialize your data structure here. Set the size of the queue to be k. */
/** Checks whether the circular queue is empty or not. */
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return (obj->rear)==(obj->front)?true:false;
}
/** Checks whether the circular queue is full or not. */
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear+1)%(obj->capacity)==(obj->front)?true:false;
}
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue *obj=(MyCircularQueue *)malloc(sizeof(MyCircularQueue));
obj->capacity=k+1;
obj->front=obj->rear=0;
obj->base=(int *)malloc(sizeof(int)*obj->capacity);
return obj;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
if(myCircularQueueIsFull(obj))
return false;
else
{
obj->base[obj->rear]=value;
obj->rear=(obj->rear+1)%obj->capacity;
return true;
}
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
else
{
obj->front=(obj->front+1)%obj->capacity;
return true;
}
}
/** Get the front item from the queue. */
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
else
{
return obj->base[obj->front];
}
}
/** Get the last item from the queue. */
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
if(myCircularQueueIsEmpty(obj))
return -1;
else
return obj->base[((obj->rear)-1+(obj->capacity))%obj->capacity];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->base);
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);
*/
链式队列
typedef struct LinkQueueNode
{
ElemType data;
struct LinkQueueNode *link;
}LinkQueueNode;
typedef struct LinkQueue
{
LinkQueueNode *head; // 队头指针
LinkQueueNode *tail; // 队尾指针
}LinkQueue;
```c
void LinkQueueInit(LinkQueue *pq)
{
assert(pq != NULL);
pq->head = pq->tail = NULL;
}
void LinkQueueEn(LinkQueue *pq, ElemType x)
{
assert(pq != NULL);
LinkQueueNode *node = (LinkQueueNode*)malloc(sizeof(LinkQueueNode));
assert(node != NULL);
node->data = x;
node->link = NULL;
if(pq->head == NULL)
pq->head = pq->tail = node;
else
{
pq->tail->link = node;
pq->tail = node;
}
}
void LinkQueueDe(LinkQueue *pq)
{
assert(pq != NULL);
if(pq->head != NULL)
{
LinkQueueNode *p = pq->head;
if(pq->head == pq->tail)
pq->head = pq->tail = NULL;
else
pq->head = p->link;
free(p);
}
}
ElemType LinkQueueFront(LinkQueue *pq)
{
assert(pq != NULL);
assert(pq->head != NULL);
return pq->head->data; //return pq->tail->data
}
int LinkQueueSize(LinkQueue *pq)
{
assert(pq != NULL);
int size = 0;
LinkQueueNode *p = pq->head;
while(p != NULL)
{
size++;
p = p->link;
}
return size;
}
bool LinkQueueEmpty(LinkQueue *pq)
{
assert(pq != NULL);
return pq->head == NULL;
}
void LinkQueueShow(LinkQueue *pq)
{
assert(pq != NULL);
LinkQueueNode *p = pq->head;
while(p != NULL)
{
printf("%d ", p->data);
p = p->link;
}
printf("\n");
}
void LinkQueueDestroy(LinkQueue *pq)
{
assert(pq != NULL);
LinkQueueNode *p = pq->head;
while(p != NULL)
{
pq->head = p->link;
free(p);
p = pq->head;
}
}
顺序队列
typedef struct SeqQueue
{
ElemType *base;
int capacity;
int front;
int rear;
}SeqQueue;
void SeqQueueInit(SeqQueue *psq, int sz)
{
assert(psq != NULL);
psq->capacity = sz > QUEUE_DEFAULT_SIZE ? sz : QUEUE_DEFAULT_SIZE;
psq->base = (ElemType*)malloc(sizeof(ElemType) * psq->capacity);
psq->front = psq->rear = 0;
}
void SeqQueueEn(SeqQueue *psq, ElemType x)
{
assert(psq != NULL);
if(psq->rear >= psq->capacity)
{
printf("队列已满,%d 不能入队.\n", x);
return;
}
psq->base[psq->rear++] = x;
}
void SeqQueueDe(SeqQueue *psq)
{
assert(psq != NULL);
if(SeqQueueEmpty(psq))
{
printf("队列已空, 不能出队.\n");
return;
}
psq->front++;
}
ElemType SeqQueueFront(SeqQueue *psq)
{
assert(psq != NULL);
assert(!SeqQueueEmpty(psq));
return psq->base[psq->front];
}
int SeqQueueSize(SeqQueue *psq)
{
assert(psq != NULL);
return (psq->rear - psq->front);
}
bool SeqQueueEmpty(SeqQueue *psq)
{
assert(psq != NULL);
return psq->front == psq->rear;
}
void SeqQueueShow(SeqQueue *psq)
{
assert(psq != NULL);
for(int i=psq->front; i<psq->rear; ++i)
printf("%d ",psq->base[i]);
printf("\n");
}
void SeqQueueDestroy(SeqQueue *psq)
{
assert(psq != NULL);
free(psq->base);
psq->base = NULL;
psq->capacity = psq->front = psq->rear = 0;
}
顺序栈
typedef struct SeqStack
{
ElemType *base; //栈空间
size_t capacity;
int top; //栈顶指针
}SeqStack;
bool SeqStackIsFull(SeqStack *pst)
{
assert(pst != NULL);
return pst->top >= pst->capacity;
}
bool SeqStackIsEmpty(SeqStack *pst)
{
assert(pst != NULL);
return pst->top == 0;
}
void SeqStackInit(SeqStack *pst, int sz)
{
assert(pst != NULL);
pst->capacity = sz > STACK_DEFAULT_SIZE ? sz : STACK_DEFAULT_SIZE;
pst->base = (ElemType*)malloc(sizeof(ElemType) * pst->capacity);
pst->top = 0;
}
void SeqStackPush(SeqStack *pst, ElemType x)
{
assert(pst != NULL);
if(SeqStackIsFull(pst))
{
printf("栈已满,%d 不能入栈.\n", x);
return;
}
pst->base[pst->top++] = x;
}
void SeqStackPop(SeqStack *pst)
{
assert(pst != NULL);
if(SeqStackIsEmpty(pst))
{
printf("栈已空, 不能出栈.\n");
return;
}
pst->top--;
}
ElemType SeqStackTop(SeqStack *pst)
{
assert(pst != NULL);
assert(!SeqStackIsEmpty(pst));
return pst->base[pst->top-1];
}
void SeqStackTop(SeqStack *pst, ElemType *top_val)//入参 //出参
{
assert(pst != NULL);
if(SeqStackIsEmpty(pst))
{
printf("栈已空, 不能取栈顶元素.\n");
return;
}
*top_val = pst->base[pst->top-1];
}
void SeqStackShow(SeqStack *pst)
{
assert(pst != NULL);
for(int i=pst->top-1; i >=0; --i)
printf("| %d |\n", pst->base[i]);
printf(" -- \n");
}
void SeqStackDestroy(SeqStack *pst)
{
assert(pst != NULL);
free(pst->base);
pst->base = NULL;
pst->capacity = pst->top = 0;
}
int SeqStackSize(SeqStack *pst)
{
assert(pst != NULL);
return pst->top;
}
链式栈
typedef struct LinkStackNode
{
ElemType data;
struct LinkStackNode *link;
}LinkStackNode;
void LinkStackInit(LinkStack *pst)
{
assert(pst != NULL);
*pst = NULL;
}
void LinkStackPush(LinkStack *pst, ElemType x)
{
assert(pst != NULL);
LinkStackNode *node = (LinkStackNode*)malloc(sizeof(LinkStackNode));
assert(node != NULL);
node->data = x;
node->link = *pst;
*pst = node;
}
void LinkStackPop(LinkStack *pst)
{
assert(pst != NULL);
if(*pst != NULL)
{
LinkStackNode *p = *pst;
*pst = p->link;
free(p);
}
}
ElemType LinkStackTop(LinkStack *pst)
{
assert(pst != NULL && *pst != NULL);
return (*pst)->data;
}
void LinkStackShow(LinkStack *pst)
{
assert(pst != NULL);
LinkStackNode *p = *pst;
while(p != NULL)
{
printf("| %d |\n", p->data);
p = p->link;
}
printf(" -- \n");
}
int LinkStackSize(LinkStack *pst)
{
assert(pst != NULL);
int size = 0;
LinkStackNode *p = *pst;
while(p != NULL)
{
size++;
p = p->link;
}
return size;
}
void LinkStackDestroy(LinkStack *pst)
{
assert(pst != NULL);
LinkStackNode *p = *pst;
while(p != NULL)
{
*pst = p->link;
free(p);
p = *pst;
}
}