526互联

数据结构-队列和栈

发布时间 2023-11-06 23:20:37作者: LX2020

栈和队列是两种不同的数据形式，区别就是栈是先进后出，但是队列先进先出，可以用数据结构模拟这两种形式。

1、队列

完整代码如下：


#include <stdio.h>
#include <stdlib.h>

#if 0 /*顺序队列*/
int enQueue(int *a, int rear, int data)
{
    a[rear] = data;
    rear++;
    return rear;
}

void deQueue(int *a, int front, int rear)
{
    while (front != rear)
    {
        printf("出队元素 %d\n", a[front]);
        front++;
    }
}

int main()
{
    int a[100];
    int front, rear;
    front = rear = 0;

    rear = enQueue(a, rear, 1);
    rear = enQueue(a, rear, 2);
    rear = enQueue(a, rear, 3);
    rear = enQueue(a, rear, 4);

    deQueue(a, front, rear);
    exit(0);
}
#else
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode;

QNode *initQueue()
{
    QNode *queue = (QNode*)malloc(sizeof(QNode));
    queue->next = NULL;
    return queue;
}

QNode *enQueue(QNode *rear, int data)
{
    QNode *enElme = (QNode*)malloc(sizeof(QNode));
    enElme->data = data;
    enElme->next = NULL;
    rear->next = enElme;
    rear = enElme;
    return rear;
}

QNode *DeQueue(QNode *top, QNode *rear)
{
    if(top->next == NULL)
    {
        printf("队列为空 \n");
        return rear;
    }

    QNode *p = top->next;
    printf("%d ", p->data);
    top->next = p->next;
    if(rear == p)
    {
        rear = top;
    }
    free(p);
    return rear;
}

int main()
{
    QNode *queue, *top, *rear;
    queue = top = rear = initQueue();

    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入队完成，所有数据元素开始出队列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);    
}

#endif

2、栈

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

#if 0 /*顺序栈*/
int push(int *a, int top, int elem)
{
    a[++top] = elem;
    return top;
}

int pop(int *a, int top)
{
    if(top == -1)
    {
        printf("空栈\n");
        return -1;
    }

    printf("弹栈元素：%d\n", a[top]);
    top--;
    return top;
}

int main()
{
    int a[100];
    int top=-1;
    top=push(a, top, 1);
    top=push(a, top, 2);
    top=push(a, top, 3);
    top=push(a, top, 4);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);

    exit(0);
}
#else /*链栈*/
typedef struct lineStack
{
    int data;
    struct lineStack *next;
}lineStack;

lineStack *push(lineStack *stack, int a)
{
    lineStack *line = (lineStack *)malloc(sizeof(lineStack));
    line->data = a;

    line->next = stack;
    stack = line;

    return stack;
}

lineStack *pop(lineStack *stack)
{
    if(stack)
    {
        lineStack *p = stack;
        stack = stack->next;
        printf("出栈元素 %d ", p->data);
        if(stack)
        {
            printf("新栈顶元素 %d\n", stack->data);
        }
        else
        {
            printf("栈空 \n");
        }
        free(p);
    }
    else{
        printf("栈已空 \n");
        return stack;
    }
    return stack;
}

int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}

#endif