算法导论简单顺序栈-白红宇

算法导论简单顺序栈

阅读量：4088 次

发布时间：2019-05-25

本文共 3474 字，大约阅读时间需要 11 分钟。

简单顺序栈

1.什么是栈？什么是顺序栈？

栈是一种基本的数据结构，栈这种数据结构实现的是一种对元素进行后进先出（last-in, first-out,LIFO）的策略。栈的顺序存储结构称为顺序栈。顺序栈可以用一个一维数组和一个记录栈顶位置的整形变量来实现，数组用于顺序存储栈中所有的数据元素，栈顶指针用于存储栈顶元素的位置。

2.顺序栈的基本操作（伪代码）

STACK-EMPTY(S)

if S.top == 0      return TRUEelse return FALSE

PUSH(S, x) //这里未考虑上溢

S.top = S.top + 1S[S.top] = x

POP(S)

if STACK-EMPTY(S)        error "underflow"else S.top = S.top - 1        return S[S.top + 1]

3.C++实现顺序栈的基本操作

//SequeStack.h#pragma once#include 
   
    template
    
     class SequeStack{public:    SequeStack(unsigned int size);    bool Push(ElemType elem);    bool Pop(ElemType* retElem);    bool Empty() const;    bool Visit(ElemType* elem, unsigned int pos) const;private:    ElemType* m_array;    unsigned int m_top;    unsigned int m_size;};template
     
      bool SequeStack
      
       ::Visit(ElemType* elem, unsigned int pos) const{    if (pos >= m_size || pos < 0)    {        assert(false && "Error: Visit Pos is out range of array!");        return false;    }    *elem = m_array[pos];    return true;}template
       
        bool SequeStack
        
         ::Empty() const{ if (m_top) { return false; } else { return true; }}template
         
          bool SequeStack
          
           ::Pop(ElemType* retElem){ if (Empty()) { assert(false && "Error: SequeStack is underflow!"); return false; } else { *retElem = m_array[--m_top]; return true; }}template
           
            bool SequeStack
            
             ::Push(ElemType pushElem){ if (m_top == m_size) { assert(false && "Error: SequeStack is overflow!"); return false; } else { m_array[m_top++] = pushElem; return true; }}template
             
              SequeStack
              
               ::SequeStack(unsigned int size) : m_array(new ElemType[size]),m_top(0),m_size(size){ memset(m_array,0,sizeof(ElemType)*size);}

//Util.h#pragma oncenamespace Util{    template
   
        void PrintMemory(T& dateStruct, unsigned int size)    {        cout << "PrintMemory: ";        for (int i = 0; i != size; i++)        {            ElemType tempElem;            dateStruct.Visit(&tempElem,i);            printf("%d ",tempElem);        }        printf("\n");    }}

//main.cpp#include "SequeStack.h"#include "Util.h"#include 
   
    using namespace std;typedef int ElemType;int main(){    const int STACK_SIZE = 10;    SequeStack
    
      testSequeStack(STACK_SIZE);    Util::PrintMemory(testSequeStack,STACK_SIZE);    cout << (testSequeStack.Empty() ? "Empty SequeStack." : "Not Empty SequeStack.") << endl;    for (int i = 1; i != 5; i++)    {        testSequeStack.Push(i);        cout << "\nPush:" << i << endl;        Util::PrintMemory(testSequeStack,STACK_SIZE);        cout << (testSequeStack.Empty() ? "Empty SequeStack." : "Not Empty SequeStack.") << endl;    }    for(int i = 1; i!= 5; i++)    {        int temp;        testSequeStack.Pop(&temp);        cout << "\nPop:" << temp << endl;        Util::PrintMemory(testSequeStack,STACK_SIZE);        cout << (testSequeStack.Empty() ? "Empty SequeStack." : "Not Empty SequeStack.") << endl;    }    return 0;}

4.运行结果

PrintMemory: 0 0 0 0 0 0 0 0 0 0
Empty SequeStack.

Push:1
PrintMemory: 1 0 0 0 0 0 0 0 0 0
Not Empty SequeStack.

Push:2
PrintMemory: 1 2 0 0 0 0 0 0 0 0
Not Empty SequeStack.

Push:3
PrintMemory: 1 2 3 0 0 0 0 0 0 0
Not Empty SequeStack.

Push:4
PrintMemory: 1 2 3 4 0 0 0 0 0 0
Not Empty SequeStack.

Pop:4
PrintMemory: 1 2 3 4 0 0 0 0 0 0
Not Empty SequeStack.

Pop:3
PrintMemory: 1 2 3 4 0 0 0 0 0 0
Not Empty SequeStack.

Pop:2
PrintMemory: 1 2 3 4 0 0 0 0 0 0
Not Empty SequeStack.

Pop:1
PrintMemory: 1 2 3 4 0 0 0 0 0 0
Empty SequeStack.