数据结构——栈和队列

发布于：2025-03-20 ⋅ 阅读:(35) ⋅ 点赞:(0)

栈和队列

1. 栈

1.1 栈的基本概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011423807.png

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011424964.png

1.2 栈的实现

栈的基本操作如下：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011424549.png

1.2.1 顺序栈

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011428893.png

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011429368.png

class SeqStack{
public:
    SeqStack():a(nullptr),_size(0),capacity(InitSize)
    {
        a=(T*)malloc(sizeof(T)*InitSize);
    }
    void push(T  x)
    {
        if(_size==capacity)
        {
            T *temp=(T*)realloc(a,sizeof(T)*capacity*2);
            if(temp==nullptr)
            {
                perror("malloc fail");
                return ;
            }
            a=temp;
            capacity*=2;
        }
        a[_size++]=x;
    }
    void pop()
    {
        assert(_size!=0);
        _size--;
    }
    T top()
    {
        assert(_size!=0);
        return a[_size-1];
    }

    bool empty()
    {
        return _size==0;
    }
    int size()
    {
        return _size;
    }
    ~SeqStack(){}
private:
    T *a;
    int _size;
    int capacity;
};

1.2.2 链栈

链栈的实现就是头插法。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011427270.png

#include <iostream>
#include <cassert>

template <class T>

struct SNode
{
    T data;
    SNode *next;
    SNode(T a) : data(a), next(nullptr) {}
};

template <class T>

class LinkStack
{
    typedef SNode<T> SNode;

public:
    LinkStack() : _size(0), head(nullptr) {}
    void push(T x)
    {
        SNode *node = new SNode(x);
        if (head == nullptr)
        {
            head = node;
        }
        else
        {
            node->next = head;
            head = node;
        }
        _size++;
    }
    void pop()
    {
        assert(_size != 0);
        if (head->next == nullptr)
        {
            delete head;
            head = nullptr;
        }
        else
        {
            SNode *temp = head->next;
            delete head;
            head = temp;
        }
        _size--;
    }
    int size()
    {
        return _size;
    }
    T top()
    {
        assert(_size != 0);
        return head->data;
    }
    bool empty()
    {
        return _size == 0;
    }

    ~LinkStack() {}

private:
    int _size;
    SNode *head;
};

2. 队列

2.1 队列的基本概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011609008.gif

2.2 队列的实现

队列的基本操作如下：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011611196.png

队列可以使用顺序、链式等结构存储，通常链式存储更为方便。

2.2.1 顺序队列

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针:队头指针 front 指向队头元素,队尾指针rear指向队尾元素的下一个位置(不同教材对front 和rear的定义可能不同)。这一点很重要，一定要看清楚rear和front具体指哪个元素。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011619205.png

初始：rear=front=0

判断队列为空：rear=front

入队操作：q[rear++]=x

出队操作：x=q[front++]

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011624012.png

当front=0,rear=M时，再有元素入队发生溢出——真溢出
当front≠0,rear=M时，再有元素入队发生溢出——假溢出
解决方法：

当rear = MAXSIZE 时，即超过队列末端时，
令rear = 0；从而使队列的首尾相连接。  
用表达式描述:       
if （rear == MAXSIZE ）           
		rear = 0 ;       
else            
		rear = rear + 1 ;

2.2.2 循环队列

上面指出了顺序队列“假溢出”的问题，这里引出循环队列的概念。将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。当队首指针 Q.front=Maxsize-1后，再前进一个位置就自动到0，这可以利用除法取余运算%来实现。

初始：rear=front=0

入队操作：q[rear]=x; rear=(rear+1)%Maxsize

出队操作：x=q[front]; front=(front+1)%Maxsize

判断队空队满的方法：

队满：(rear+1)%M==front

队空：rear==front

队列元素个数：(rear-front+M)%M

入队与出队操作一般是不变的，无论rear和front指哪个元素，但是队满、队空、初始条件会不一样。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011637153.png

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011633678.png

循环队列的实现：

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011640090.png

2.2.3 链式队列

队列的链式表示称为链队列,它实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

https://cdn.jsdelivr.net/gh/junmoxiao6661/pigo_image@main/202412011643682.png

#include <iostream>
#include <cassert>
#include <cstdlib>

template <class T>

struct QNode
{
    T data;
    QNode *next;
    QNode(T a) : data(a), next(nullptr) {}
};
// 使用链式存储实现队列，便于实现其操作
template <class T>

class LinkQueue
{
    typedef QNode<T> QNode;

public:
    LinkQueue() : head(nullptr), tail(nullptr), _size(0) {}
    void push(T x)//尾插法
    {
        QNode *node = new QNode(x);
        if (head == nullptr)
        {
            head = tail = node;
        }
        else
        {
            tail->next = node;
            tail = node;
        }
        _size++;
    }
    void pop()
    {
        assert(_size != 0);

        if (head->next == nullptr)
        {
            free(head);
            head = nullptr;
        }
        else
        {
            QNode *temp = head->next;
            delete head;
            head = temp;
        }

        _size--;
    }

    bool empty()
    {
        return _size == 0;
    }
    size_t size()
    {
        return _size;
    }
    T front()
    {
        assert(_size != 0);
        return head->data;
    }
    T back()
    {
        assert(_size != 0);
        return tail->data;
    }
    ~LinkQueue()
    {
        QNode *cur = head;
        while (cur)
        {
            QNode *temp = cur->next;
            free(cur);
            cur = temp;
        }
        head = tail = nullptr;
        _size = 0;
    }

private:
    QNode *head;
    QNode *tail;
    int _size;
};

3. 栈与队列的应用

3.1 括号匹配问题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

https://leetcode.cn/problems/valid-parentheses/description/

// 顺序栈实现
typedef struct Stack {
    char data[10010];
    int top;
} Stack;
void InitStack(Stack* s) { s->top = 0; }

void StackPush(Stack* s, char x) {
    s->data[s->top] = x;
    s->top++;
}
void StackPop(Stack* s) { s->top--; }

char StackTop(Stack* s) { return s->data[s->top - 1]; }

bool StackEmpty(Stack* s) { return s->top == 0; }

bool isValid(char* s) {
    Stack st;
    InitStack(&st);
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if(s[i]=='('||s[i]=='{'||s[i]=='[') 
            StackPush(&st,s[i]);
        else
        {
            if(StackEmpty(&st))
                return false;
            else if(s[i]==')'&&StackTop(&st)!='(')  //只考虑错误情况
                return false;
            else if(s[i]=='}'&&StackTop(&st)!='{')
                return false;
            else if(s[i]==']'&&StackTop(&st)!='[')
                return false;
            StackPop(&st);
        }
    }
    return StackEmpty(&st);
}

/需要注意的是如果不返回结点，那么就要使用二级指针来写，链表章节注意的问题。

// 链栈实现
typedef struct SNode{
    struct SNode *next;
    char val;
}SNode;
void InitStack(SNode* s) 
{ 
    s->next=NULL;
}
// 需要注意的是如果不返回结点，那么就要使用二级指针来写
void StackPush(SNode** s, char x) {
    SNode *temp = (SNode*)malloc(sizeof(SNode));
    temp->val = x;
    temp->next = *s;
    *s = temp;
}

void StackPop(SNode** s) {
    if (*s != NULL) {
        SNode *temp = *s;
        *s = (*s)->next;
        free(temp);
    }
}

char StackTop(SNode* s) { return s->val; }

bool StackEmpty(SNode* s) { return s->next == NULL; }

bool isValid(char* s) {
    SNode *st=(SNode*)malloc(sizeof(SNode));
    InitStack(st);
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if(s[i]=='('||s[i]=='{'||s[i]=='[')
            StackPush(&st,s[i]);
        else
        {
            if(StackEmpty(st))
                return false;
            else if(s[i]==')'&&StackTop(st)!='(')
                return false;
            else if(s[i]=='}'&&StackTop(st)!='{')
                return false;
            else if(s[i]==']'&&StackTop(st)!='[')
                return false;
            StackPop(&st);
        }
    }
    return StackEmpty(st);
}



typedef struct SNode {
    struct SNode* next;
    char val;
} SNode;
void InitStack(SNode* s) { s->next = NULL; }

SNode* StackPush(SNode* s, char x) {
    SNode* temp = (SNode*)malloc(sizeof(SNode));
    temp->val = x;
    temp->next = s;
    return temp;
}
SNode* StackPop(SNode* s) {
    SNode* temp = s->next;
    free(s);
    return temp;
}

char StackTop(SNode* s) { return s->val; }

bool StackEmpty(SNode* s) { return s->next == NULL; }

bool isValid(char* s) {
    SNode* st = (SNode*)malloc(sizeof(SNode));
    InitStack(st);
    int n = strlen(s);
    for (int i = 0; i < n; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            st = StackPush(st, s[i]);
        else {
            if (StackEmpty(st))
                return false;
            else if (s[i] == ')' && StackTop(st) != '(')
                return false;
            else if (s[i] == '}' && StackTop(st) != '{')
                return false;
            else if (s[i] == ']' && StackTop(st) != '[')
                return false;
            st = StackPop(st);
        }
    }
    return StackEmpty(st);
}

3.2 表达式问题

前、中、后缀表达式

3.3 栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

https://leetcode.cn/problems/implement-queue-using-stacks/description/

一个栈用来存数据，一个用来出数据，出数据的栈为空时，将如数据栈的元素存入出数据栈。

class MyQueue {
public:
    MyQueue() {}

    void push(int x) { s1.push(x); }

    int pop() {
        int res = peek();
        s2.pop();
        return res;
    }

    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int res = s2.top();
        return res;
    }
        bool empty() { return s1.empty() && s2.empty(); }

    private:
        stack<int> s1;
        stack<int> s2;
    };

typedef struct {
    int st1[100];
    int st2[100];
    int top1;
    int top2;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue *q = (MyQueue*)malloc(sizeof(MyQueue));
    q->top1=0;
    q->top2=0;
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    obj->st1[obj->top1++]=x;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->top2==0)
    {
        for(int i=obj->top1-1;i>=0;i--)
        {
            obj->st2[obj->top2++]=obj->st1[i];
        }
        obj->top1=0;
    }
    int res=obj->st2[obj->top2-1];
    return res;
}

int myQueuePop(MyQueue* obj) {
    int res=myQueuePeek(obj);
    obj->top2--;
    return res;
}

bool myQueueEmpty(MyQueue* obj) {
    return obj->top1==0&&obj->top2==0;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
    obj=NULL;
}

3.4 队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

https://leetcode.cn/problems/implement-stack-using-queues/description/

class MyStack {
public:
    MyStack() {}

    void push(int x) {
        int n = q1.size();
        q1.push(x);
        for (int i = 0; i < n; i++) {  // 将元素重新push
            q1.push(q1.front());
            q1.pop();
        }
    }

    int pop() {
        int res = top();
        q1.pop();
        return res;
    }

    int top() { return q1.front(); }

    bool empty() { return q1.empty(); }

private:
    queue<int> q1;
};

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布