算法导论使用单链表实现栈-白红宇

算法导论使用单链表实现栈

阅读量：4089 次

发布时间：2019-05-25

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

使用单链表实现栈

1. 算法导论原题

10.2-2
Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.
译：使用一个单链表实现一个栈。PUSH和POP操作仍然需要保持O(1)时间复杂度。

2. 如何使用单链表实现栈？

栈的主要原理就是后进先出，又因为原题需要保持PUSH和POP的时间复杂度是1，因此不可能把后进的元素放在链表尾，故每次PUSH的时候都需要把元素放在头节点的后面。所以PUSH和POP操作并不需要遍历整个链表，因而时间复杂度可以做到O(1)。

3. 使用单链表实现栈（C++代码）

//StackBySinglyLink.h#pragma once#include "SinglyLinkList.h"template
   
    class StackBySinglyLink{public:    StackBySinglyLink();    bool Push(ElemType elem);    bool Pop(ElemType* elem);    bool Empty();    unsigned int GetLength() const;    bool Visit(ElemType* elem, const unsigned int& pos) const;private:    SinglyLinkList
    
     * m_pSinglyLink;};template
     
      bool StackBySinglyLink
      
       ::Empty(){    return m_pSinglyLink->Empty();}template
       
        unsigned int StackBySinglyLink
        
         ::GetLength() const{ return m_pSinglyLink->GetLength();}template
         
          bool StackBySinglyLink
          
           ::Pop(ElemType* elem){ return m_pSinglyLink->Delete(0,elem);}template
           
            bool StackBySinglyLink
            
             ::Push(ElemType elem){ if (m_pSinglyLink->Insert(elem,0)) { return true; } else { assert(false && "Error: StackBySinglyLink Push failed for allocate node"); return false; }}template
             
              StackBySinglyLink
              
               ::StackBySinglyLink() : m_pSinglyLink(new SinglyLinkList
               
                ()){}template
                
                 bool StackBySinglyLink
                 
                  ::Visit(ElemType* elem, const unsigned int& pos) const{ return m_pSinglyLink->Visit(elem,pos);}

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

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

4. 程序运行结果

PrintMemory:
Empty StackBySinglyLink.

Push:1
PrintMemory: 1
Not Empty StackBySinglyLink.

Push:2
PrintMemory: 2 1
Not Empty StackBySinglyLink.

Push:3
PrintMemory: 3 2 1
Not Empty StackBySinglyLink.

Push:4
PrintMemory: 4 3 2 1
Not Empty StackBySinglyLink.

Pop:4
PrintMemory: 3 2 1
Not Empty StackBySinglyLink.

Pop:3
PrintMemory: 2 1
Not Empty StackBySinglyLink.

Pop:2
PrintMemory: 1
Not Empty StackBySinglyLink.

Pop:1
PrintMemory:
Empty StackBySinglyLink.