欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-栈和队列的多种实现方法

程序员文章站 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;
	}
}
相关标签: 数据结构