栈与队列的实现

Miracle • 2023-04-16 • C++, 数据结构与算法 • 554 阅读

栈与队列的存储结构分顺序存储和链式存储两种。

栈

是一种先进后出的线性表。在栈中进行插入删除的一端称之为栈顶，另一端称为栈底。

栈的顺序存储

出栈

最后一个元素直接删除并返回。

template<typename ElementType>
ElementType stack_Sequence<ElementType>::Pop()
{
    if (isEmpty())
    {
        throw;
    }
    length-=1;
    ElementType *cur = array+(length);
    ElementType old=*cur;
    *cur=0;
    return old;
}

入栈

压入数组末尾。

template<typename ElementType>
void stack_Sequence<ElementType>::Push(ElementType value)
{
    if (isFull())
    {
        throw;
    }
    ElementType *cur = array+length;
    *cur=value;
    length+=1;
}

 栈的链式存储

出栈：

栈顶元素释放。更新栈顶元素为原栈顶元素的直接后续

template<typename ElementType>
ElementType stack_LinkList<ElementType>::Pop()
{
    if (isEmpty())
    {
        throw;
    }
    LinkNode* q = top->next;
    top->next=q->next;
    length-=1;
    ElementType popData=q->data;
    free(q);
    return popData;
}

入栈:

更新栈顶元素，并它的直接后续指向原栈顶元素。

//stack_LinkList<ElementType>::
template<typename ElementType>
void stack_LinkList<ElementType>::Push(ElementType value)
{
    LinkNode* newNode=(LinkNode*)malloc(sizeof(LinkNode));
    newNode->data=value;
    newNode->next=top->next;
    top->next=newNode;
    length+=1;
}

队列

队列是一种先进先出的线性表，它只允许在队尾插入元素，另一端队头删除元素。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。因为队列中元素逻辑关系与线性表的相同，所以队列可以采用与线性表相同的存储结构。采用顺序存储结构的队列称为顺序队，采用链表式存储结构的队列称为链队。

队列的顺序存储

因为队列两端都在变化，所以需要两个指针来标识队列的状态。rear总是指向队尾元素，front指向当前队中队头元素的前一位置。

若约定初始化建空队列时，令front=rear=0。每当新的元素进队，rear增1；每当元素出队，front增1；当rear=MaxSize-1时不能再进队。

因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。在纯顺序队列中，当队列出入队进行一定次数后，若尾指针指向超出队列容量就可能会出现假溢出状态。

假溢出：front不指向0,而rear指向超出队列容量。front位置之前的数组空间未被使用，但却发生溢出。

溢出：非空队列下，front与rear相同时进行入队操作发生溢出。

为了解决这个问题我们可以将其改造成循环队列。

循环队列

在队列空和队列满的情况下，循环队列的队头和队尾指针指向相同，此时没法判定队列状态。为了区别队空和队满的情况，可采用两种处理方式：

  1. 设置一个标志位，以区别相同时队列是空是满。
  2. 牺牲一个存储单元，约定队列的尾指针所指的下一个位置是队头指针是队头指针所指位置时表示队列满。而头尾指针指向相同时表示队列为空。

这里我们采用第二种方案。牺牲数组中的最后一个单元，用来区分是否队满。于是有了公式和表达式：

((rear+1)%QUEUE_MAXSIZE)==front;
长度公式：
当rear>front时，rear-front得到头尾之间有几个元素，由于尾指针指向下一个元素入队的位置。所以头尾指针之差就是队列长度。
对于循环队列，可能有rear<front，差值为负数。所以将差值加上队列容量即可得到队列长度。
对结果与队列容量求余，可得到两种情况的一个通用公式：
(QUEUE_MAXSIZE+rear-front)%QUEUE_MAXSIZE;
代码
判断空队列：
template<typename  ElementType>
bool queue_Sequence<ElementType>::isEmpty()
{
    return rear==front;
}

判断溢出

template<typename ElementType>
bool queue_Sequence<ElementType>::isFull()
{
    //循环队列 数组最后一地址空间留空 使队满状态以满足以下逻辑表达式。
    return ((rear+1)%QUEUE_MAXSIZE)==front;
}

获取长度

template<typename  ElementType>
int queue_Sequence<ElementType>::getLength()
{
    //循环队列 数组最后一地址空间留空 使得长度以满足以下运算表达式。
    return (rear-front+QUEUE_MAXSIZE)%QUEUE_MAXSIZE;
}

入队

template<typename  ElementType>
void queue_Sequence<ElementType>::Enqueue(ElementType value)
{
    if (isFull())
    {
        throw "队列已满";
    }
    //Fake Full
    
    //Standard
    ElementType* cur=array+rear;
    *cur=value;
    rear=(rear+1)%QUEUE_MAXSIZE;
}

出队

template<typename  ElementType>
ElementType queue_Sequence<ElementType>::Dequeue()
{
    if (isEmpty())
    {
        throw "队列为空，不能进行出队操作";
    }
    ElementType* delElePointer=array+front;
    ElementType  delEleValue=*delElePointer;
    front=(front+1)%QUEUE_MAXSIZE;
    return delEleValue;
}

template<typename  ElementType>
ElementType queue_Sequence<ElementType>::Peek()
{
    ElementType* cur=array+front;
    return *cur;
}

主程序入口测试：

/*
 * @Author       : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @Date         : 2023-04-07 16:01:54
 * @LastEditors  : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
 * @LastEditTime : 2023-04-08 23:18:14
 * @FilePath     : \DS3\source\Program.cpp
 * @Description  : 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */ 
using namespace std;
#include <stdlib.h>
#include <iostream>
#include "stack_LinkList.h"
#include "stack_Sequence.h"
#include "queue_Sequence.h"
template<class ElementType>
void Test03_Stack(istack<ElementType> *stack);
void Test01_StackLINKLIST();
void Test02_StackSEQUENCE();

void Test04_QUEUE_SEQUENCE();
template<class ElementType>
void Test04_QUEUE(IQueue<ElementType> *queue);


int main()
{
    try
    {
        Test04_QUEUE_SEQUENCE();
    }
    catch( const char* s)
    {
        cout<<s<<endl;
    }
    
    system("pause");
    return 1;
}

void Test01_StackLINKLIST()
{
    stack_LinkList<int> stack;
    Test03_Stack(&stack);
}
void Test02_StackSEQUENCE()
{
    stack_Sequence<int> stack;
    Test03_Stack(&stack);
    
}

template<class ElementType>
void Test03_Stack(istack<ElementType> *stack)
{
    
    stack->Push(1);
    stack->Push(2);
    stack->Push(3);
    cout<<"Top："<<endl;
    cout<<stack->Top()<<endl;
    int len=stack->getLength();
    cout<<"List："<<endl;
    for (int i = 0; i < len; i++)
    {
        cout<<stack->Pop()<<endl;
    }
    stack->Push(3);
    cout<<"Top："<<endl;
    cout<<stack->Top()<<endl;
}


void Test04_QUEUE_SEQUENCE()
{
    queue_Sequence<int> queue;
    Test04_QUEUE(&queue);
}

template<class ElementType>
void Test04_QUEUE(IQueue<ElementType> *queue)
{
    
    queue->Enqueue(1);
    queue->Enqueue(2);
    queue->Enqueue(3);
    cout<<"Peek："<<endl;
    cout<<queue->Peek()<<endl;
    int len=queue->getLength();
    cout<<"List："<<endl;
    for (int i = 0; i <= len; i++)
    {
        cout<<queue->Dequeue()<<endl;
    }
    queue->Enqueue(3);
    cout<<"Peek："<<endl;
    cout<<queue->Peek()<<endl;
}

 队列的链式存储

队列的链式存储与栈的链式存储类似，这里就不赘述了。

示例下载

DS3.栈和队列(线性和链).zip
来源：诚通网盘 | 提取码：unitymake
作者：Miracle
来源：麦瑞克博客
链接：https://www.playcreator.cn/archives/programming-life/datastruct/3000/
本博客所有文章除特别声明外，均采用CC BY-NC-SA 4.0许可协议，转载请注明！
THE END
分享
海报
栈与队列的实现
栈与队列的存储结构分顺序存储和链式存储两种。 栈 是一种先进后出的线性表。在栈中进行插入删除的一端称之为栈顶，另一端称为栈底。 栈的顺序存储 出栈 最后……
<<上一篇
下一篇>>
文章目录
关闭
目 录