数据结构——线性结构之栈和队列

2024-02-26 13:07:28

一、栈

（一）定义

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。对于栈的修改要按照先进后出的原则进行，因此，栈又被称为后进先出（LIFO）的线性表。

（二）基本运算

初始化：创建一个空栈。
判断栈是否为空：如果栈为空，返回“真”，否则返回“假”。
入栈：将元素x加入栈顶，并更新栈顶指针。
出栈：将栈顶元素删除，并更新栈顶指针。可以返回栈顶元素。
读取栈顶元素：返回栈顶元素，但不修改栈顶指针。

（三）存储结构

顺序存储：用一组地址连续的存储单元存储自栈顶到栈底的数据元素。采用这种存储结构的栈，称为顺序栈。
链式存储：用链表作为存储结构的栈，称为链栈。链表的头指针就是栈顶指针。

（四）应用

表达式求值
括号匹配
将递归过程转变为非递归过程

（五）顺序栈代码

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define NULL -2
typedef int bool;
typedef int ElementType;

Stack CreateStack();
bool IsFull(Stack S);
bool IsEmpty(Stack S);
bool Push(Stack S, ElementType X);
ElementType Pop(Stack S);

typedef int Position;
struct SNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Top;      /* 栈顶指针 */
    int MaxSize;       /* 堆栈最大容量 */
};
typedef struct SNode *Stack;

Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}
 
bool IsFull( Stack S )
{
    return (S->Top == S->MaxSize-1);
}
 
int Push( Stack S, ElementType X )
{
    if ( IsFull(S) ) {
        printf("堆栈满");
        return FALSE;
    }
    else {
        S->Data[++(S->Top)] = X;
        return TRUE;
    }
}
 
bool IsEmpty( Stack S )
{
    return (S->Top == -1);
}
 
ElementType Pop( Stack S )
{
    if ( IsEmpty(S) ) {
        printf("堆栈空");
        return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
    }
    else 
        return ( S->Data[(S->Top)--] );
}

（六）链栈代码

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define NULL -2
typedef int bool;
typedef int ElementType;

Stack CreateStack();
bool IsEmpty(Stack S);
bool Push(Stack S, ElementType X);
ElementType Pop(Stack S);

typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;
 
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
 
bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}
 
bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;
 
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return TRUE;
}
 
ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;
 
    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

二、队列

（一）定义

队列是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。对于队列的修改要按照先进先出的原则进行，因此，队列又被称为先进先出（FIFO）的线性表。

（二）基本运算

初始化：创建一个空的队列。
判断队列是否为空：如果队列为空，则返回”真“，否则返回”假“。
入队：将元素x加入到队列的队尾，并更新队尾指针。
出队：将队头元素从队列中删除，并更新队头指针。
读取队头元素：返回对头元素的值，但不更新队头指针。

（三）存储结构

顺序存储：队列的顺序结构又称为顺序队。

链式存储：队列的链式存储又称为链队。

（四）应用

排队买 XXX
医院的挂号系统

（五）顺序队代码

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define NULL -2
typedef int bool;
typedef int ElementType;
typedef int Position;

Queue CreateQueue(int MaxSize);
bool IsFull(Queue Q);
bool IsEmpty(Queue Q);
bool AddQ(Queue Q, ElementType X);
ElementType DeleteQ(Queue Q);

struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}
 
bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);
}
 
bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return FALSE;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return TRUE;
    }
}
 
bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}
 
ElementType DeleteQ( Queue Q )
{
    if ( IsEmpty(Q) ) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];
    }
}

（六）链队代码

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define NULL -2
typedef int bool;
typedef int ElementType;
typedef struct Node *PtrToNode;

Queue CreateQueue(int MaxSize);
bool IsFull(Queue Q);
bool IsEmpty(Queue Q);
bool AddQ(Queue Q, ElementType X);
ElementType DeleteQ(Queue Q);

struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
 
struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;
 
bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}
 
ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
     
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;
 
        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}

码农公寓

一、栈

（一）定义

（二）基本运算

（三）存储结构

（四）应用

（五）顺序栈代码

（六）链栈代码

二、队列

（一）定义

（二）基本运算

（三）存储结构

（四）应用

（五）顺序队代码

（六）链队代码

相关文章